CS46 — Homework 8


Due Thursday 24 April at start of class
Starting files are available from my public cs46 folder 
cd ~/cs46/
cp -r examples/homework/hw08.tex homework/
You may work with a partner and submit a common solution on this homework.
In lab practice
  1. Show that P is closed under union, complement and concatenation. What about intersection and Kleene star?
  2. Show that NP is closed under union, concatenation, and Kleene star. What about intersection and complement?
  3. Show via a reduction from SAT that MAX-SAT is NP-complete. MAX-SAT is defined as follows: given a Boolean formula $\phi$ of $F$ clauses and an integer $K$, is there a truth assignment of the variables in $\phi$ that satisfy at least $K \leq F$ clauses?
  4. (From Lewis&Papadimitriou, section 6.3) 2-SAT considers Boolean formulas that are the conjunction of $m$ clauses, where each clause is of the form $(x_i)$ or $(x_i \lor x_j)$.
    1. Consider $\phi=(x_1) \land (x_1 \lor x_2) \land ( x_3 \lor \overline{x_2}) \land ( \overline{x_1} \lor \overline{x_2}) \land (x_3 \lor x_4) \land ( \overline{x_3} \lor x_5) \land ( \overline{x_4} \lor \overline{x_5}) \land ( x_4 \lor \overline{x_3})$ Show there is a satisfying assignment for $\phi$.
    2. Show 2-SAT is in NP
  5. Note if a 2-SAT clause contains only one literal, e.g., $(x_1)$, this literal must be true. Then all other clauses containing $x_1$ must also be true, while clauses of the form $(\overline{x_1} \lor x_2)$ can be simplified to $(x_2)$, resulting in more one-clause literals that can further simplify $\phi$. Call this process of eliminating one-literal clauses a purge. If during the purge process all variables from a clause are excluded via simplification, the purge fails. If the purge does not fail, any resulting clauses have exactly two literals. Choose an arbitrary element $x_i$ in the remaining clauses and set its value to True, and execute the purge algorithm. If it succeeds, continue with the remaining clauses. Otherwise, try $x_i$ set to False. If neither purge succeeds, the formula is not satisfiable. A series of successful purges that results in no remaining clauses constructs a satisfying truth assignment in the process.
    1. For a formula with $m$ clauses, how long does the purge of a single variable take?
    2. Apply this technique to the formula in the previous problem.
    3. Show that 2-SAT is in P