Theoretical Computer Science
cc.complexity-theory reference-request complexity-classes conditional-results polynomial-hierarchy
Updated Sat, 18 Jun 2022 15:59:46 GMT

Can one amplify P=NP beyond P=PH?


In Descriptive Complexity, Immerman has

Corollary 7.23. The following conditions are equivalent:
1. P = NP.
2. Over finite, ordered structures, FO(LFP) = SO.

This can be thought of as "amplifying" P=NP to an equivalent statement over (presumably) larger complexity classes. Note that SO captures the polynomial-time hierarchy PH, and that FO(LFP) captures P, so this can be thought of as P=NP iff P=PH.

(The interesting part of this is the statement that P=NP implies P=PH; it is trivial that P=CC implies P=NP for any class CC that contains NP. Immerman simply remarks "if P=NP then PH=NP", presumably because P=NP can be used with the oracle definition of PH to show inductively that the whole hierarchy collapses.)

My question is:

How much further can P=NP be amplified in this way?

In particular, what is the largest known class CC' such that P=NP implies P=CC', and the smallest class CC such that P=NP implies CC=NP? This would allow P=NP to be replaced by the equivalent question CC=CC'. P appears to be a rather powerful class, which seems to provide little "wiggle room" for arguments trying to separate it from NP: how far can the wiggle room be amplified?

I would of course also be interested in an argument that shows that P=PH is the limit of this approach.

Edit: note the closely related question Why doesn't P=NP imply P=AP (i.e. P=PSPACE)? which focuses on the other direction, why we don't have proofs that P=PSPACE. Answers there by Kaveh and Peter Shor argue that the number of alternations being fixed is key. Another related question is A decision problem which is not known to be in PH but will be in P if P=NP which asks for a candidate problem; the answers there also can be used to construct answers for this question, although these classes are somewhat artificial (thanks to Tsuyoshi Ito for pointing this out). In a more general setting, Collapsing of exptime and alternation bounded turing machine asks whether a local collapse at any level in an alternation hierarchy induces an upward collapse, as happens with the polynomial-time hierarchy.

Solution

From Russell Impagliazzo's comment:

As a way of formalizing what languages are in $\mathsf{P}$ if $\mathsf{P}=\mathsf{NP}$, Regan introduced the complexity class $\mathsf{H}$. A language $L$ is in $\mathsf{H}$ if and only if $L$ is in $\mathsf{P}^O$ relative to every oracle $O$ so that $\mathsf{P}^O=\mathsf{NP}^O$. Thus, $L$ is in $\mathsf{H}$ if the statement $\mathsf{P}=\mathsf{NP} \implies L\in\mathsf{P}$ relativizes. $\mathsf{PH} \subseteq \mathsf{H} \subseteq \mathsf{AltTime}(O(\lg\lg n),\mathsf{poly})$. From Toda's theorem, and some of the lemmas in Toda's theorem, it is also true that $\mathsf{H} \subseteq \mathsf{P}^{\mathsf{mod}_q \mathsf{P}}$ for every $q$. Basically, any oracle satisfying $\mathsf{P}^O=\mathsf{NP}^O$ gives a new upper bound on $\mathsf{H}$. It is open whether $\mathsf{H}=\mathsf{PH}$.

And from Lance Fortnow's comment:

Let $f(n)$ be any unbounded function. $\mathsf{H}$ is not contained in $\mathsf{AltTime}(f(n),\mathsf{poly})$ and if you could prove $\mathsf{P}=\mathsf{NP}$ implies $\mathsf{P}=\mathsf{AltTime}(f(n),\mathsf{poly})$ then $\mathsf{NP}$ is different than $\mathsf{L}$.

For definition of $\mathsf{H}$ see definition 6.3 in

Comments (4)

  • +1 – @Josh, regarding Lance's comment, I feel I am missing something since $f(n) = \lg \lg n$ is unbounded and AltTime(f,poly) contains H according to Russel's comment. — Jan 13, 2017 at 03:01  
  • +3 – I'm confused about something. Why doesn't Josh Grochow's answer to the earlier question on this topic (cstheory.stackexchange.com/a/2039/1575) essentially answer Regan's question as well? I.e., why doesn't it give an example of a language L that's in P if P=NP by a relativizing argument, but that's not in PH if P!=NP? And why doesn't it therefore show that if P!=NP, then H is strictly larger than PH? — Jan 17, 2017 at 03:02  
  • +3 – Actually, a possible answer occurs to me. Is the issue that, in Grochow's construction, the very definition of the language L will depend on the oracle O? — Jan 17, 2017 at 03:57  
  • +1 – @Scott: Indeed, your possible answer is correct, as which strings are used for the diagonalization (and indeed, whether the are put into or out of L) will depend on the oracle. In more detail, if $P^O = NP^O$, the language $L$ is finite, so the different $L$ for different $O$ are only finitely different. But if we consider all $O$ such that $P^O \neq NP^O$, then the $L$ for these different $O$ cannot even be p-equivalent, since this set of oracles is a dense subset of $2^{\Sigma^*}$. — Feb 12, 2017 at 23:59  

External Links

External links referenced by this document:

Linked Articles

Local articles referenced by this article:

References