Can one amplify P=NP beyond P=PH?

Question

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.

Answer 1

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

• Kenneth W. Regan, "Index sets and presentations of complexity classes", 1999

Answer 2

As I wrote in my answer to the other question let's make the argument constructive and uniform in the number of alternations by giving an algorithm that solves $\Sigma^P_k$ assuming that we have a polynomial-time algorithm for SAT and see what we would get if $k$ is not constant.

Let $M$ be a DTM with two inputs $x$ and $y$. Think of it as a verifier for an $\mathsf{NP}$ problem.

Let $Cook(M, \vec{n}, t)$ be an algorithm that converts an TM $M$ to a circuit of size $s(\vec{n},t) \in \mathsf{poly}$ which computes $M$ on inputs of size $\vec{n}$ for $t$ steps.

Assume that $\mathsf{P}=\mathsf{NP}$ and there is a deterministic algorithm $A$ that solves Circuit-SAT certificate extension problem in time $p\in\mathsf{poly}$.

With these ingredients we define an algorithm for TQBF that given a quantified Boolean formula, recursively removes the inner-most quantifier and replaces it with a quantifier free one. Let $s_i$ be the size of the formula at the $i$th step, then we have $s_{i+1} = s\circ p(s_i)$. If the formula have $k$ quantifiers we end up with $q(n) = (s \circ p)^k(n)$ where $n$ is the size of the TQBF formula given as input.

If $k$ is constant then $q(n) \in \mathsf{poly}$. Since circuit-value is in $\mathsf{P}$ we have a polynomial-time algorithm.

If $k \in \omega(1)$ then $q(n)$ is not polynomial time anymore, we get an algorithm which is in $n^{2^{O(k)}}$. E.g. if $k = \lg \lg n$ we get a quasipolynomial-time algorithm. For $k = \lg n$ we don't get anything nontrivial.

---

I think what we really are interested in is the largest class $C$ such that $$T \vdash \mathsf{P} = \mathsf{NP} \to \mathsf{P}=C$$ where $T$ is a strong enough theory to formalize all our current results (e.g. you can take it be $\mathsf{ZFC}$) because the main point of these results is to make it easier to prove $\mathsf{P} \neq \mathsf{NP}$.

If we take weaker theories the result might still be interesting, however it is not really an upper bound on the largest value of $C$. When Regan uses relativization to define $\mathsf{H}$ he is essentially restricting arguments to those that relativize. If we use a result which does not relativize we might get a larger class than $\mathsf{H}$ that would be equal to $\mathsf{P}$ if $\mathsf{P}=\mathsf{NP}$.

---

As a more philosophical note, I personally dislike the idea of thinking about relativization as alternative realities or worlds. Statements in "relativized worlds" by themselves do not give us any information about the statement in unrelativized setting. As a example of this take $\mathsf{BPP} = \mathsf{PP}$ which most of us do not believe to be true but the relativized version is true w.r.t. a random oracle with probability 1. As another example take $\mathsf{IP} = \mathsf{PSpace}$ which is true but becomes false w.r.t. a random oracle with probability 1.

I also find the idea that there is only one single correct way of relativizing a complexity class problematic which causing a lot of misconceptions (like thinking relativization as a functional operation on complexity classes in their extensional sense, a relativization is a modification of a computation model, not a class of functions or languages). I think viewing relativizations as modified (interactive) computation frameworks is more useful. This way there are many useful ways of relativizing a complexity classes (in its intentional sense). To get any information about the unrelativized setting from a relativized framework we need some kind of transfer principle similar to the transfer principle in non-standard analysis. Note that picking some particular method of relativization for classes which preserve the known relations between classes doesn't give us a transfer principle (this is the main criteria typically used in the literature to decide what is "the" right relativization of a class).