Answer Happy

3. The SAT problem is the central problem for the complexity dass NP, concerning the satisfiability (or not) of a given formula o in conjunctive normal form (CNF) ф = Лc, [15 marks] where each clause C, is the disjunction of a number of literals over the set of logical variables {.....In). 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 clauses of formula shown below. Consider the variables in the order of increasing index, and show your workings. = (VEVE3) (1 VE V13) (V 12 V 1.) (TV 12V #) (V13 V14) (51 Vig V 14) (52 V 13 V 1:4) (12 V13 V14) (12V 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 erpected 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 o be the collection of not-yet-resolved clauses of sizes 1.2.3 and 4. Suppose 1; is the next variable to be assigned a bit value, and suppose that the set of clauses of that involve 1. consist of: • k clauses of size 1 which contain I, as the only remaining literal ki clauses of size 1 which contain f, as the only remaining literal k clauses of size 2 which contain I, k; clauses of size 2 which contain i; k clauses of size 3 which contain 1: k; clauses of size 3 which contain i ki clauses of size 4 which contain 1 ki clauses of size 4 which contain 1, [2 marks] Page 5 of 7