Answer Happy

0 Exercise H1 (The k-SAT Problem) (6+2+2+4+2 points) The k-SAT problem is defined as follows: • Given: Let F be a Boolean KNF formula where each clause contains exactly k literals. Question: Is F satisfiable? (a) Show: 3-SAT is NP-complete. Hint: Reduce SAT to 3-SAT. (b) Next, show that 2-SAT is in P. To do this, construct to a given 2-SAT instance consisting of n variables x1,..., X'n and k clauses C1, ...,Ck, a directed graph Ĝ (V, A). Let V := {x1, ..., Un, 71, ... In} and the edge set A chosen in such a way that for each clause C = (11 V 12), 11,12 € V, two directed edges 11 + 12 and 12 +11. These edges model the relation that for satisfiability in any 2-SAT clause we have: If li is false, then 12 must be true and vice versa. i. Give an example of a non-satisfiable 2-SAT formula and the corresponding auxiliary = graph G. ii. Show: If there exists a directed path from v to u in Ğ for u, v EV, then there also exists a path from ū to v. iii. Show: 2-SAT is not satisfiable if and only if there is a node v € V for which there exists both a directed path from v to ū as well as a directed path from ū to v. iv. Show by i) iii): 2-SAT EP