54
$\begingroup$

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.

$\endgroup$
  • 12
    $\begingroup$ Related (shameless self-promotion): A decision problem which is not known to be in PH but will be in P if P=NP. $\endgroup$ – Tsuyoshi Ito Mar 13 '11 at 20:21
  • 17
    $\begingroup$ As a way of formalizing what languages are in P if P=NP , Regan introduced the complexity class H. A language $L$ is in H if and only if L is in P$^O$ relative to every oracle $O$ so that P$^O$=NP$^O$. Thus, $L$ is in H if the statement P=NP $\implies L \in$ P relativizes. PH $\subseteq$ H $\subseteq$ Alternations-time $(O(\log \log n), \rm{poly})$. From Toda's theorem, and some of the lemmas in Toda's theorem, it is also true that H $\subseteq$ P$^{\rm{mod}_q \rm{P}}$ for every $q$. (Basically, any oracle satisfying P$^O$=NP$^O$ gives a new upper bound on H. It is open whether H=PH.) $\endgroup$ – Russell Impagliazzo Mar 14 '11 at 13:07
  • 4
    $\begingroup$ @Russell: thanks! That comment sounds like an answer. $\endgroup$ – András Salamon Mar 14 '11 at 16:19
  • 5
    $\begingroup$ Finally found a reference to Ken Regan's class $H$: see definition 6.3 of "Index Sets and Presentations of Complexity Classes", available at: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8927. Official version at: dx.doi.org/10.1016/0304-3975(95)00146-8 $\endgroup$ – Joshua Grochow May 8 '13 at 17:09
  • 3
    $\begingroup$ Let f(n) be any unbounded function. H is not contained in Alternations-Time(f(n),poly) and if you could prove P=NP implies P=Alternations-Time(f(n),poly) then NP is different than L. $\endgroup$ – Lance Fortnow Mar 6 '16 at 14:11
6
+25
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ @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. $\endgroup$ – Kaveh Jan 13 '17 at 3:01
  • 3
    $\begingroup$ 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? $\endgroup$ – Scott Aaronson Jan 17 '17 at 3:02
  • 3
    $\begingroup$ 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? $\endgroup$ – Scott Aaronson Jan 17 '17 at 3:57
  • 1
    $\begingroup$ @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^*}$. $\endgroup$ – Joshua Grochow Feb 12 '17 at 23:59
5
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I agree with "viewing relativizations as a interactive computation frameworks is more useful in my opinion" in a certain way. Namely the presentation of relativizations could be made more intuitive to understand by starting with the situation where the machine(s) (with interactive oracle access) is given first, and an opponent is allowed to select a language for the oracle. Then one switches to the situation where a (complex) oracle language is given first, and the machines can now be adapted to the world given by the specific oracle. $\endgroup$ – Thomas Klimpel Jan 13 '17 at 9:58

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.