<p>From  Russell Impagliazzo's <a href="https://cstheory.stackexchange.com/questions/5463/can-one-amplify-p-np-beyond-p-ph#comment14597_5463">comment</a>:</p>

<blockquote>
  <p>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}$.</p>
</blockquote>

<p>And from Lance Fortnow's <a href="https://cstheory.stackexchange.com/questions/5463/can-one-amplify-p-np-beyond-p-ph#comment78141_5463">comment</a>:</p>

<blockquote>
  <p>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}$.</p>
</blockquote>

<p>For definition of $\mathsf{H}$ see definition 6.3 in</p>

<ul>
<li>Kenneth W. Regan, "<a href="http://dx.doi.org/10.1016/0304-3975(95)00146-8" rel="nofollow noreferrer">Index sets and presentations of complexity classes</a>", 1999</li>
</ul>

CC BY-SA 3.0
2017-01-13T03:01:54.787Z
@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.
Kaveh
CC BY-SA 3.0
2017-01-17T03:02:09.930Z
I'm confused about something.  Why doesn't Josh Grochow's answer to the earlier question on this topic (http://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?
Scott Aaronson
CC BY-SA 3.0
2017-01-17T03:57:20.023Z
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?
Scott Aaronson
CC BY-SA 3.0
2017-02-12T23:59:00.723Z
@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^*}$.
Joshua Grochow
CC BY-SA 3.0
2017-01-12T03:51:48.183Z
2017-01-13T02:58:13.580Z
2017-04-13T12:32:30.623Z
Kaveh
<p>As I wrote in <a href="https://cstheory.stackexchange.com/a/14549/186">my answer to the other question</a> 
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.</p>

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

<p>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.</p>

<p>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}$.</p>

<p>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.</p>

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

<p>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.</p>

<hr>

<p>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}$.</p>

<p>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}$.</p>

<hr>

<p>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 href="https://en.wikipedia.org/wiki/Random_oracle" rel="nofollow noreferrer">a random oracle</a> 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.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Transfer_principle" rel="nofollow noreferrer">transfer principle</a> similar to
the transfer principle in <a href="https://en.wikipedia.org/wiki/Non-standard_analysis" rel="nofollow noreferrer">non-standard analysis</a>.
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).</p>

CC BY-SA 3.0
2017-01-13T09:58:16.343Z
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.
Thomas Klimpel
CC BY-SA 3.0
2017-01-07T19:08:28.457Z
2017-05-18T12:42:22.563Z
2017-05-18T12:42:22.563Z
Kaveh
<p>In <em>Descriptive Complexity</em>, Immerman has</p>

<blockquote>
  <p><strong>Corollary 7.23.</strong> The following conditions are equivalent:<br>
  <strong>1.</strong> P = NP.<br>
  <strong>2.</strong> Over finite, ordered structures, FO(LFP) = SO.</p>
</blockquote>

<p>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.</p>

<p>(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.)</p>

<p>My question is:</p>

<blockquote>
  <p>How much further can P=NP be amplified in this way?</p>
</blockquote>

<p>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?</p>

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

<hr>

<p><em>Edit:</em> note the closely related question <a href="https://cstheory.stackexchange.com/questions/5399/why-doesnt-p-np-imply-p-ap-i-e-p-pspace">Why doesn&#39;t P=NP imply P=AP (i.e. P=PSPACE)?</a> 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 href="https://cstheory.stackexchange.com/questions/2032/a-decision-problem-which-is-not-known-to-be-in-ph-but-will-be-in-p-if-p-np">A decision problem which is not known to be in PH but will be in P if P=NP</a> 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, <a href="https://cstheory.stackexchange.com/questions/465/collapsing-of-exptime-and-alternation-bounded-turing-machine">Collapsing of exptime and alternation bounded turing machine</a> asks whether a local collapse at any level in an alternation hierarchy induces an upward collapse, as happens with the polynomial-time hierarchy.</p>

CC BY-SA 2.5
2011-03-15T13:11:02.703Z
@Tsuyoshi Ito: thanks for pointing this out, have edited accordingly.
András Salamon
CC BY-SA 2.5
2011-03-16T03:53:47.503Z
@András, thanks, but my answer to the other question was simply pointing out a conceptual confusion that (or at least it seemed to me) the OP had which I tried to clarify by giving a similar but much simpler problem to show that the number of alternations is not a number but a function of input size and $\forall k\in \mathbb{N}. \varphi(f_k)$ does not imply $\varphi(f)$ for other functions. On the other hand, I think Peter's superior answer is related to your question since it is dealing with why we can't prove the result (generally).
Kaveh
CC BY-SA 2.5
2011-03-13T20:21:07.597Z
Related (shameless self-promotion): [A decision problem which is not known to be in PH but will be in P if P=NP](http://cstheory.stackexchange.com/questions/2032/a-decision-problem-which-is-not-known-to-be-in-ph-but-will-be-in-p-if-p-np).
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-14T13:07:42.080Z
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.)
Russell Impagliazzo
CC BY-SA 2.5
2011-03-14T16:19:30.923Z
@Russell: thanks!  That comment sounds like an answer.
András Salamon
CC BY-SA 2.5
2011-03-15T11:55:02.270Z
Any answer L to my question can be converted to a complexity class X which satisfies “P=NP ⇒ P=X” by letting X be the class of problems polynomial-time reducible to the problem L.  An artificial problem corresponds to an artificial class, of course, but it is not true that “the answers […] don't help to suggest answers for this question.”
Tsuyoshi Ito
CC BY-SA 3.0
2013-05-08T17:09:46.820Z
Finally found a reference to Ken Regan's class $H$: see definition 6.3 of "Index Sets and Presentations of Complexity Classes", available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8927. Official version at: http://dx.doi.org/10.1016/0304-3975(95)00146-8
Joshua Grochow
CC BY-SA 3.0
2014-05-18T08:26:07.003Z
Maybe this might help. This is how it is done from the Electronics point of view, prehaps something similar can be done mathmaticaly ? In a transistor there are layers of transistor material each has its own charge tuned to a diffrent polarity. P = Positive
N = Nevitive
P = Positive The transistor switches between them. In between each layer of transister material there is a special material called a base. This could be termed N as it is Neutral. To amplify the charge a transistor can take you need to thiken the layers of transistor material relative to each other. PP = Positive
NN = Negitive
aspie
CC BY-SA 3.0
2016-03-06T14:11:15.027Z
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.
Lance Fortnow
CC BY-SA 3.0
2017-01-07T16:10:41.913Z
@LanceFortnow Per Russell Impaglazzo's comment above, H is contained in Alternations-Time(O(log log n), poly).
Emil Jeřábek
<cc.complexity-theory><reference-request><complexity-classes><conditional-results><polynomial-hierarchy>
Can one amplify P=NP beyond P=PH?
András Salamon
# Can one amplify P=NP beyond P=PH?

(Asked by: username_0 on 2011-03-13)

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)?](https://cstheory.stackexchange.com/questions/5399/why-doesnt-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 username_1 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](https://cstheory.stackexchange.com/questions/2032/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 username_2 for pointing this out). In a more general setting, [Collapsing of exptime and alternation bounded turing machine](https://cstheory.stackexchange.com/questions/465/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.

**Tags:** cc.complexity-theory, reference-request, complexity-classes, conditional-results, polynomial-hierarchy

> **Comments:**
> **username_2**: Related (shameless self-promotion): [A decision problem which is not known to be in PH but will be in P if P=NP](http://cstheory.stackexchange.com/questions/2032/a-decision-problem-which-is-not-known-to-be-in-ph-but-will-be-in-p-if-p-np).  
> **username_3**: 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.)  
> **username_0**: @Russell: thanks!  That comment sounds like an answer.  
> **username_2**: Any answer L to my question can be converted to a complexity class X which satisfies “P=NP ⇒ P=X” by letting X be the class of problems polynomial-time reducible to the problem L.  An artificial problem corresponds to an artificial class, of course, but it is not true that “the answers […] don't help to suggest answers for this question.”  
> **username_0**: @username_2: thanks for pointing this out, have edited accordingly.  
> **username_1**: @András, thanks, but my answer to the other question was simply pointing out a conceptual confusion that (or at least it seemed to me) the OP had which I tried to clarify by giving a similar but much simpler problem to show that the number of alternations is not a number but a function of input size and $\forall k\in \mathbb{N}. \varphi(f_k)$ does not imply $\varphi(f)$ for other functions. On the other hand, I think Peter's superior answer is related to your question since it is dealing with why we can't prove the result (generally).  
> **username_4**: Finally found a reference to Ken Regan's class $H$: see definition 6.3 of "Index Sets and Presentations of Complexity Classes", available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8927. Official version at: http://dx.doi.org/10.1016/0304-3975(95)00146-8  
> **username_5**: Maybe this might help. This is how it is done from the Electronics point of view, prehaps something similar can be done mathmaticaly ? In a transistor there are layers of transistor material each has its own charge tuned to a diffrent polarity. P = Positive N = Nevitive P = Positive The transistor switches between them. In between each layer of transister material there is a special material called a base. This could be termed N as it is Neutral. To amplify the charge a transistor can take you need to thiken the layers of transistor material relative to each other. PP = Positive NN = Negitive  
> **username_6**: 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.  
> **username_7**: @LanceFortnow Per Russell Impaglazzo's comment above, H is contained in Alternations-Time(O(log log n), poly).  

---

## 2 answers

### Answer by username_1 on 2017-01-12. Score: 8 | Accepted answer

From username_3's [comment](https://cstheory.stackexchange.com/questions/5463/can-one-amplify-p-np-beyond-p-ph#comment14597_5463):

> 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 username_6's [comment](https://cstheory.stackexchange.com/questions/5463/can-one-amplify-p-np-beyond-p-ph#comment78141_5463):

> 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](http://dx.doi.org/10.1016/0304-3975(95)00146-8)", 1999

> **Comments:**
> **username_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.  
> **username_8**: I'm confused about something.  Why doesn't Josh Grochow's answer to the earlier question on this topic (http://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?  
> **username_8**: 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?  
> **username_4**: @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^*}$.  

---

### Answer by username_1 on 2017-01-07. Score: 6

As I wrote in [my answer to the other question](https://cstheory.stackexchange.com/a/14549/186)
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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Transfer_principle) similar to
the transfer principle in [non-standard analysis](https://en.wikipedia.org/wiki/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).

> **Comments:**
> **username_9**: 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.  

---

