Answer Happy

3. The SAT problem is the central problem for the complexity class NP.concerning the satisfiability (or not) of a given formula in conjunctive normal form (CNF) Φ = Λο, (15 marks) where each clause C, is the disjunction V of a number of literals over the set of logical variables {....,n}. Over the years, a huge number of approximation algorithms and heuristics have been developed to find high-quality assignments for CNF formulae, including our (derandomized) (8/7)-approximation algorithm for the special case of 3-CNF formulae (each clause has 3 literals, over 3 distinct variables). (a) Apply derandomization of conditional expectations to obtain a specific as signment to {:11, 12, 13, 14} which satisfies > 9x of the causes of formula shown below. Consider the variables in the order of increasing index, and show your workings. 0 = (1, VE, V13) (1 V 12 V 13) A (V12 V 1.) ( VF V.1) (, V13 V14) (11 Vis Vra) (12 V 13 Vra) (72V 13 Vf) (12 V 13 V 1.). (b) The algorithm for k= 3 above can be generalised to the 4-CNF case where each clause contains exactly 4 literals (over 4 distinct variables). i. What is the expected number of satisfied clauses of an initial 4-CNF formula with m clauses? ii. Consider an intermediate stage during conditional derandomization, where we have set a value for some variables and have some already satis- fied clauses, some already refuted clauses, and some unresolved clauses. Let' be the collection of not-yet-resolved clauses of sizes 1. 2.3 and 4. Suppose x; is the next variable to be assigned a bit value, and suppose that the set of clauses of that involve T, consist of: k clauses of size 1 which contain r, as the only remaining literal ki clauses of size 1 which contain i, as the only remaining literal k; clauses of size 2 which contain I k; clauses of size 2 which contain it kfclauses of size 3 which contain I k; clauses of size 3 which contain i, k clauses of size 4 which contains ki clauses of size 4 which contain [2 marks]