# 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$$.