Problems and topics listed here are for open discussion and practice. Feel free to work with a partner or ask the instructor questions. Towards the end of the lab period we may review some but not necessarily all answers. You are welcome to discuss solutions and strategies to these problems openly with classmates and the instructor outside of lab/class, on Piazza, and office hours.
Sample Problems
You do not need to submit any solutions to these problems. This work will not be graded.
- Show that if $\conp \neq \np$, then $\p \neq \np$.
- Consider the 3-SAT clause $C_i = ( x_i \vee y_i \vee z_i )$ and the following MAX-2-SAT reduction $w_i \wedge x_i \wedge y_i \wedge z_i \wedge (\overline{x_i} \vee \overline{y_i}) \wedge (\overline{y_i} \vee \overline{z_i}) \wedge (\overline{x_i} \vee \overline{z_i}) \wedge (\overline{w_i} \vee x_i ) \wedge (\overline{w_i} \vee y_i ) \wedge (\overline{w_i} \vee z_i ) $, where $w_i$ is a new variable.
Consider the following three cases where $C_i$ is satisfied
- $x_i=T, y_i=F, z_i=F$
- $x_i=T, y_i=T, z_i=F$
- $x_i=T, y_i=T, z_i=T$
In each case, show there is choice for $w_i$ such that 7 of the 10 2-CNF clauses are satisfied.
Finally consider the case $x_i=F, y_i=F, z_i=F$, and show no choice of $w_i$ satisfies 7 or more clauses. This construction shows we can take a 3-SAT instance with $m$ clauses and construct a MAX-2-SAT instance with $10m$ clauses and $k=7m$ such that the 3-SAT formula is satisfiable iff $7m$ clauses of the MAX-2-SAT instance are satisfiable.
-
A coloring of a graph is an assignment of
colors to its nodes so that no two adjacent nodes are assigned the
same color. Define $\textrm{3-COLOR}$ as:
$$\textrm{3-COLOR}= \left \{
\langle G \rangle \; \left | \;
G \text{ is colorable with three colors}
\right .
\right \}$$
Show that $\textrm{3-COLOR}$ is $\np$-complete.
(Hint: reduce from 3-$\textrm{SAT}$ and use the subgraphs given in
the textbook hint, page 325.)