91Ó°ÊÓ

Show that $\mathbf{NP}$ is closed under the star operation

Let ? be a 3cnf-formula. An ≠-assignment to the variables of ? is one where each clause contains two literals with unequal truth values. In other words, an ≠ -assignment satisfies ? without assigning three true literals in any clause.

a. Show that the negation of any ≠ -assignment to ? is also an ≠ -assignment.

b. Let ≠ SAT be the collection of 3cnf-formulas that have an ≠ -assignment. Show that we obtain a polynomial time reduction from 3SAT to ≠ SAT by replacing each clause ci

$\mathbf{(}{\mathbf{y}}_{\mathbf{1}}\mathbf{∨}{\mathbf{y}}_{\mathbf{2}}\mathbf{∨}{\mathbf{y}}_{\mathbf{3}}\mathbf{)}$$$

with the two clauses

$\mathbf{(}{\mathbf{y}}_{\mathbf{1}}\mathbf{∨}{\mathbf{y}}_{\mathbf{2}}\mathbf{∨}{\mathbf{z}}_{\mathbf{i}}\mathbf{)}\mathit{a}\mathit{n}\mathit{d}\mathbf{(}\stackrel{\mathbf{¯}}{{\mathbf{z}}_{\mathbf{i}}}\mathbf{∨}{\mathbf{y}}_{\mathbf{3}}\mathbf{∨}\mathbf{b}\mathbf{)}$

Where $\mathbf{zi}$is a new variable for each clause,$\mathbf{ci}$ and b is a single additional new variable.

A coloring of a graph is an assignment of colors to its nodes so that no two adjacent nodes are assigned the same color.

Show that 3COLOR is NP-complete. (Hint: Use the following three subgraphs.)

Let $\mathbf{SET}\mathbf{-}\mathbf{SPLITTING}\mathbf{}$collection of subsets of S, for some $\mathbf{k}>\mathbf{0}$, such that elements of S can be colored red or blue so that no Ci has all its elements colored with the same color}. Show that $\mathbf{SET}-\mathbf{SPLITTING}$is NP-complete.

Show that if P=NP , a polynomial time algorithm exists that takes an undirected graph as input and finds a largest clique contained in that graph. (See the note in Problem 7.38.)

In the proof of the Cook–Levin theorem, a window is a $\mathbf{2}\mathbf{×}\mathbf{3}$rectangle of cells. Show why the proof would have failed if we had used role="math" localid="1664195743361" $\mathbf{2}\mathbf{×}\mathbf{2}$windows instead.

Fill out the table described in the polynomial time algorithm for context-free language recognition from $\mathbf{Theorem}\mathbf{7}.\mathbf{16}\mathbf{for}\mathbf{string}\mathbf{w}=\mathbf{baba}\mathbf{and}\mathbf{CFG}\mathbf{G}:$

$$\begin{gathered} \mathbf{S}→\mathbf{RT} \\ \mathbf{R}\mathbf{→}\mathbf{T}\mathbf{R}\mathbf{|}\mathbf{a} \\ \mathbf{T}\mathbf{→}\mathbf{T}\mathbf{R}\mathbf{|}\mathbf{b} \end{gathered}$$

Show that$\mathit{P}$ is closed under union, concatenation, and complement.

Let $\mathbf{CONNECTED}=\{<\mathbf{G}>|\mathbf{G}\mathbf{is}\mathbf{a}\mathbf{connected}\mathbf{undirected}\mathbf{graph}\}.$Analyse the algorithm given on page 185 to show that this language is in .