1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

Show that in that case $\text{NP=coNP}$ which means $\Sigma^p_1=\Pi_1^p$, so the hierarchy collapse to the first level.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.