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