In Chapter 5 of the Arora–Barak complexity theory textbook we are asked to prove the following statement:
If 3SAT is polynomial-time reducible to its complement then PH=NP. How do I prove this statement?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
Show that in that case $\text{NP=coNP}$ which means $\Sigma^p_1=\Pi_1^p$, so the hierarchy collapse to the first level.
$\begingroup$
$\endgroup$
Here is the sketch for proving this: Suppose that $\mathsf{3SAT}$ is closed under its complement under polynomial-time reductions. Since $\mathsf{3SAT}$ is an $\mathsf{NP}$-complete problem, this implies that $\mathsf{NP}$ is also closed under complement, i.e. $\mathsf{\Sigma_n^p}=\mathsf{\Pi_n^p}$ where $n =1$. For $n \geq 1$, and $\mathsf{\Sigma_n^p}$, define $n$ non-deterministic Turing machines $\mathcal{M_1} \ldots \mathcal{M_n}$ each of which is in one-to-one correspondence with the respective oracles of $\mathsf{\Sigma_n^p}$. Define a non-deterministic Turing machine $\mathcal{M}$, as the concatenation of $\mathcal{M_1} \ldots \mathcal{M_n}$. Finally, prove that $\mathsf{\Sigma_n^p}$ answers yes iff $\mathcal{M}$ does so.
Some insights on why this works: The power of the polynomial hierarchy comes from the fact that one can negate the answer obtained from the oracle. Of course, if $\mathsf{NP}$ is already closed under complement, then one can simply concatenate polynomially many non-deterministic Turing machines and obtain the same computational power with a single non-deterministc Turing machine, which in turn implies that the polynomial hierarchy collapses to the first level.
