CSE 431: HW #5

Out: Tuesday, 6-Feb

Due: Tuesday, 13-Feb before class

Assignment

1. SAT-BUT-NOT-TOO-SAT

   Consider a 3CNF formula \(\phi = C_1 \wedge C_2 \wedge \cdots \wedge C_m\), where each \(C_i\) is a clause on three literals. Recall that \(\phi\) is satisfiable if there is a truth assignment to its variables that satisfies every clause.

   Say that \(\phi\) is sat-but-not-too-sat if there is an assignment to its variables such that some literal in every clause is true and some literal in every clause is false.

   For instance, the formula \[\phi = (x_1 \vee \bar{x}_2 \vee x_3) \wedge (x_2 \vee \bar{x}_3 \vee x_1) \wedge (\bar{x}_1 \vee \bar{x}_2 \vee \bar{x}_4)\] is sat-but-not-too-sat because of the assignment \((x_1,x_2,x_3,x_4)=(T,T,T,F)\).

   Define the language \[ \textsf{3SAT-BUT-NOT-TOO-SAT} = \left\{ \phi : \phi \textrm{ is a sat-but-not-too-sat 3CNF formula}\right\} \]

   Prove that \(\textsf{3SAT-BUT-NOT-TOO-SAT}\) is \(\mathsf{NP}\)-complete.

Extra credit

1. Consider a mapping \(\varphi : \Sigma \to \Sigma^+\) that maps characters of the alphabet to finite length strings (recall that \(\Sigma^+\) is the set of finite length strings over \(\Sigma\) with length at least one). For a word \(w = w_1 w_2 \cdots w_n \in \Sigma^*\), we define \[ \varphi(w) = \varphi(w_1) \varphi(w_2) \cdots \varphi(w_n). \]

   Consider the following two statements:

   1. \(\mathsf{P}=\mathsf{NP}\)

   2. For every language \(L \in \mathsf{P}\), the language \( \left\{ \varphi(w) : w \in L \right\} \) is also in \(\mathsf{P}\).

   • Prove that \((1) \implies (2)\)
   • Prove that \((2) \implies (1)\)