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\).