Homework 4

Problem 1.

Consider the following problem ChromaticNumber: The input is a graph \(G\) and an integer \(k\). Decide if \(k\) is the smallest number such that \(G\) is \(k\)-colorable.

Show that the property \(A(x)\) that \(x\) is a yes-instance of ChromaticNumber can be expressed as follows:

\[ A(x) = (\exists y: B(x,y)) \land (\forall z: C(x,z)), \]
where \(y\) and \(z\) are witnesses of polynomial length and \(B, C \in P\).

Show next that there are two properties \(A_1, A_2 \in NP\) such that \(A = A_{1} \setminus A_{2}\). (That is, \(A(x)\) is true iff \(A_{1}(x)\) is true and \(A_{2}(x)\) is false.)

Let's call the class of properties that can be written in this way as the difference of two properties in NP as DP. Show

\[ DP \subseteq \Sigma_{2}P \cap \Pi_2 P. \]

Problem 2.

Show that the optimization problem of finding the largest independent set in a given graph \(G\) is in \(P^{NP}\).

Problem 3.

First, show that \(P^{NP}\) contains both \(NP\) and \(coNP\). Then, show \(NP^{NP} = \Sigma_{2} P\). Finally, show
\[ P^{NP} \subseteq \Sigma_{2} P \cap \Pi_{2} P. \]

Problem 4.

Given a function \(f: \mathbb{N} \rightarrow \mathbb{N}\), we define two properties as follows:
\begin{align*} A_{even}(x) & = SAT(x) \land (\text{$f(|x|)$ is even})\\ A_{odd}(x) & = SAT(x) \land (\text{$f(|x|)$ is odd}) \end{align*}
Show that if \(P \neq NP\), then there is a polynomial-time computable function \(f\) such that \(A_{odd}\) and \(A_{even}\) are incomparable. That is, neither can be reduced to the other.

Hint: As in the proof in the class, look at the list of all polynomial-time programs \(\Pi_{i}\). Design \(f\) so that neither problem can be reduced to the other, neither problem is in \(P\), and SAT cannot be reduced to one of them. Give a construction for \(f\) in such a way that if \(f\) gets "stuck", this means that \(P = NP\).