<p><span class="math-container">$\text{P}^\mathcal{H} = \text{NP}^\mathcal{H} = \text{PSPACE}^\mathcal{H}$</span> as noted in the <a href="https://cstheory.stackexchange.com/questions/39394/how-to-prove-phalt-pspacehalt">linked answer</a> (note that the query tape counts as space).  Specifically, using <span class="math-container">$n$</span> calls to the halting oracle, we can compute the first <span class="math-container">$n$</span> bits of the Chaitin's constant.  Using these bits, we can compute the oracle output for all queries of length <span class="math-container">$ &lt; ≈n$</span> and decide the space-bounded problem — in unlimited time without assistance or in <span class="math-container">$n^{O(1)}$</span> time using another call to the oracle.</p>
<p>The equality of the complexity classes stems not from the complexity of <span class="math-container">$\mathcal{H}$</span>, but its closure.  Let <span class="math-container">$U\mathcal{H}$</span> be the halting oracle, with the machine+input encoded in unary; let <span class="math-container">$U\mathcal{H}'$</span> also allow querying the <span class="math-container">$i$</span>th bit of machine output (for machines that halt) with <span class="math-container">$i$</span> in binary.  We have <span class="math-container">$\text{P}^\mathcal{H} = \text{EXP}^{U\mathcal{H}} = \text{EXP}^{U\mathcal{H'}}$</span>.  Now, for every oracle <span class="math-container">$A$</span>, <span class="math-container">$\text{P}^{\text{EXP}^A} = \text{PSPACE}^{\text{EXP}^A}$</span>. Roughly speaking, an <span class="math-container">$\text{EXP}^A$</span> oracle is sufficiently closed relative to itself; using determinacy (see <a href="https://mathoverflow.net/questions/285991/determinacy-and-polynomial-time-degrees">here</a>) it can be shown that for every Borel property <span class="math-container">$p$</span> there is <span class="math-container">$B$</span> such that whether <span class="math-container">$\text{EXP}^{B,A}$</span> satisfies <span class="math-container">$p$</span> is independent of <span class="math-container">$A$</span>.</p>
<p>To explore P vs NP for different representations of <span class="math-container">$0'$</span>, let <span class="math-container">$Ω$</span> be the Chaitin's constant, and <span class="math-container">$UΩ$</span> be the Chaitin's constant with bits queried sequentially (or bit index in unary).  The Chaitin's constant (machine halting probability) encodes the halting problem, but looks like random data.  A caveat is that <span class="math-container">$Ω$</span> and I think <span class="math-container">$\text{P}^Ω$</span>, <span class="math-container">$\text{NP}^Ω$</span>, <span class="math-container">$\text{P}^{UΩ}$</span>, and <span class="math-container">$\text{NP}^{UΩ}$</span> depend on the choice of (reasonable) encoding.</p>
<p>We have:  <br/>
<span class="math-container">$\text{P}^Ω ≠ \text{NP}^Ω$</span> (the polynomial hierarchy is infinite relative to a random oracle)<br/>
<span class="math-container">$\text{P}^{UΩ} = \text{NP}^{UΩ}$</span> iff NP = RP<br/>
<span class="math-container">$\text{P}^{U\mathcal{H}} = \text{NP}^{U\mathcal{H}}$</span> iff NP is in P/poly (<span class="math-container">$U\mathcal{H}$</span> is powerful but sparse)<br/>
<span class="math-container">$\text{P}^{U\mathcal{H}'} = \text{NP}^{U\mathcal{H}'} = \text{PSPACE}^\mathcal{U\mathcal{H}'}$</span></p>
<p>Also, the distinction between decision oracles and function oracles is relevant to fine-grained complexity but not for P vs NP as restricting to decision oracles gives at most a quadratic slowdown.</p>
<p>Despite <span class="math-container">$\text{P}^\mathcal{H} = \text{NP}^\mathcal{H}$</span>, nondeterminism can reduce the number of oracle calls:  Just two calls suffice for <span class="math-container">$\mathcal{H}$</span> — one to certify haltings and another to certify nonhaltings.  By contrast, deterministically computing the <span class="math-container">$n$</span>th binary digit of the Chaitin's constant requires (even with unbounded time) <span class="math-container">$n-O(\log n)$</span> calls to the halting oracle.  This is by the incompressibility of the Chaitin's constant and its capture of the halting problem; <span class="math-container">$O(\log n)$</span> is here because <span class="math-container">$n$</span> itself (if lucky) can give a logarithmic number of bits to jump-start the search for <span class="math-container">$Ω$</span>.  (And for unbounded time, using the function version of <span class="math-container">$\mathcal{H}$</span> does not reduce the required number of calls.)</p>

CC BY-SA 4.0
2023-09-11T12:10:01.930Z
The linked argument for $\def\H{\mathcal H}\mathrm{P^\H=PSPACE^\H}$ sounds correct. However, I do not understand the subsequent discussion. As far as I can see, $\mathrm{P^\H=P^{U\H}\ne EXP^{U\H}}$: if $U$ denotes a universal TM with machines encoded in binary, and $\ulcorner U\urcorner$ is its unary code, then $\langle e,x\rangle\mapsto\langle\ulcorner U\urcorner,\langle e,x\rangle\rangle$ is a poly-time many-one reduction of $\H$ to $U\H$.
Emil Jeřábek
CC BY-SA 4.0
2023-09-11T15:22:15.287Z
@EmilJeřábek I fixed and expanded the answer; for $U\mathcal{H}$, the input to the machine (if used) would also be encoded in unary.
Dmytro Taranovsky
CC BY-SA 4.0
2023-09-11T17:11:37.513Z
Oh, I see, that makes sense. However, I still do not see why $\mathrm{EXP}^{U\mathcal H}\subseteq\mathrm P^\mathcal H$. I can simulate an exponentially long query to $U\mathcal H$ with a polynomially long query to $\mathcal H$, but how do I simulate an exponentially long computation with exponentially many oracle queries by a polynomial-time computation?
Emil Jeřábek
CC BY-SA 4.0
2023-09-11T17:46:38.033Z
@EmilJeřábek Use can use the same Chaitin's constant argument (compute enough digits to implement $U\mathcal{H}$ up to sufficient length, and then ask $\mathcal{H}$ for the result).
Dmytro Taranovsky
CC BY-SA 4.0
2023-09-12T08:09:41.447Z
Aha, all right. I think it would be good to include more details on this in the answer.
Emil Jeřábek
CC BY-SA 4.0
2023-09-11T06:50:36.853Z
2023-09-11T17:06:56.290Z
2023-09-11T17:06:56.290Z
Dmytro Taranovsky
<p>Consider the following variant <span class="math-container">$\mathscr{H}$</span> of the halting oracle: given the code <span class="math-container">$e$</span> for an ordinary Turing machine and an input <span class="math-container">$n$</span> to it, we let <span class="math-container">$\mathscr{H}(\langle e,n\rangle) = \langle 0,0\rangle$</span> if the result <span class="math-container">$\varphi_e(n)$</span> of the execution of <span class="math-container">$e$</span> on <span class="math-container">$n$</span> is undefined (does not terminate), and <span class="math-container">$\langle 1,\varphi_e(n)\rangle$</span> if <span class="math-container">$\varphi_e(n)$</span> is defined.  (As far as computability goes, the first component is enough, of course, but since I'm going to measure complexity I think it makes more sense to include <span class="math-container">$\varphi_e(n)$</span> in the result.)</p>
<p>Now consider Turing machines having access to <span class="math-container">$\mathscr{H}$</span> as an oracle.  Even though <span class="math-container">$\mathscr{H}$</span> is not computable, we can define relativized complexity classes such as <span class="math-container">$\mathbf{P}^{\mathscr{H}}$</span>, <span class="math-container">$\mathbf{NP}^{\mathscr{H}}$</span>, <span class="math-container">$\mathbf{EXPTIME}^{\mathscr{H}}$</span>, etc., as usual.  (I hope there is no hidden difficulty in exactly how the oracle is queried.  I'm interested in time complexity, and I think my definition of <span class="math-container">$\mathscr{H}$</span> means that the only thing that really matters is the number of calls to the oracle, since any computable function is computed “for free”.)</p>
<p><strong>Question:</strong> Is <span class="math-container">$\mathbf{P}^{\mathscr{H}} = \mathbf{NP}^{\mathscr{H}}$</span>?</p>
<p>(Of course, even an informal argument explaining why the question should be just as hard to answer as the case without oracle counts as an answer!)</p>
<p><strong>Motivation:</strong> I'm aware that there are computable oracles making the relativized version of <span class="math-container">$\mathbf{P}=\mathbf{NP}$</span> true or false, and in fact quite easy either way (see Papadimitriou, <em>Computational Complexity</em> (1994), theorems 14.4 and 14.5, neither proof seems to adapt here), but I'm confused as to what happens when we relativize the theory of complexity to non-computable oracles (cross-links to <a href="https://cstheory.stackexchange.com/questions/1675/relativization-with-respect-to-non-recursive-oracles">this question</a> as well as <a href="https://cstheory.stackexchange.com/questions/47085/has-there-been-any-development-of-complexity-theory-for-other-turing-degrees-tha">this question of mine</a> which was perhaps too vague and <a href="https://cstheory.stackexchange.com/questions/47094/complexity-relative-to-the-graph-of-the-busy-beaver-function">this other one</a> concernings a purposefully “weak” oracle, might be relevant here).  The specific oracle <span class="math-container">$\mathscr{H}$</span> tries to formalize the idea that all computable functions are given “for free”, so complexity relative to it seems like a reasonable candidate for a complexity theory of <span class="math-container">$\mathbf{0'}$</span> (which I hope would turn out to be much easier than that of <span class="math-container">$\mathbf{0}$</span>).</p>

CC BY-SA 4.0
2023-09-08T11:54:38.330Z
related: https://cs.stackexchange.com/questions/126163/under-what-kind-of-oracles-are-p-and-np-equivalent
It seems to suggest that the answer depends on the particular way to enumerate Turing Machines. But with your twist that you add the result of the computation in the oracle, it might change...
Denis
CC BY-SA 4.0
2023-09-08T14:29:07.290Z
How is the time complexity measured? If it's with respect to the original input, how can a polynomial-time machine even read the result of an oracle call if it's superpolynomially long? On the other hand, if it's allowed to be polynomial in the length of the output of the oracle, then all the complexity classes likely trivially collapse as you can award yourself an arbitrary amount of extra time just by posting the right query. (IOW, there is a reason why the common definition of relativised P, NP, EXP, etc. only allows *decision* oracles rather than functions.)
Emil Jeřábek
CC BY-SA 4.0
2023-09-08T15:06:13.460Z
@EmilJeřábek Complexity is measured in the size of the input. The idea I had in mind was that the machine calls the oracle on tapes of its choice (one for $e$ and one for $n$, say), the oracle instantly replaces the input value by the output (again, on two tapes to avoid discussing encodings), and if the latter is too long to be usefully read, well, that's your problem for asking the oracle a bad question.  But if you think that's not the right problem to ask, I'm open to variations. However, yes, I think of $\mathbf{P}$ and $\mathbf{NP}$ as decision problems.
Gro-Tsen
CC BY-SA 4.0
2023-09-08T15:38:52.720Z
This is a reasonable oracle model, but I believe that it is then equivalent to an oracle for the decision halting problem, as the machine can compute polynomially many bits of the result (which is what it can use) by querying the oracle bit by bit. So perhaps it would be easier to define it using a decision oracle right away.
Emil Jeřábek
<cc.complexity-theory><computability><oracles>
Is P=NP relative to the halting oracle?
Gro-Tsen
# Is P=NP relative to the halting oracle?

(Asked by: username_0 on 2023-09-08)

Consider the following variant $\mathscr{H}$ of the halting oracle: given the code $e$ for an ordinary Turing machine and an input $n$ to it, we let $\mathscr{H}(\langle e,n\rangle) = \langle 0,0\rangle$ if the result $\varphi\_e(n)$ of the execution of $e$ on $n$ is undefined (does not terminate), and $\langle 1,\varphi\_e(n)\rangle$ if $\varphi\_e(n)$ is defined. (As far as computability goes, the first component is enough, of course, but since I'm going to measure complexity I think it makes more sense to include $\varphi\_e(n)$ in the result.)

Now consider Turing machines having access to $\mathscr{H}$ as an oracle. Even though $\mathscr{H}$ is not computable, we can define relativized complexity classes such as $\mathbf{P}^{\mathscr{H}}$, $\mathbf{NP}^{\mathscr{H}}$, $\mathbf{EXPTIME}^{\mathscr{H}}$, etc., as usual. (I hope there is no hidden difficulty in exactly how the oracle is queried. I'm interested in time complexity, and I think my definition of $\mathscr{H}$ means that the only thing that really matters is the number of calls to the oracle, since any computable function is computed “for free”.)

**Question:** Is $\mathbf{P}^{\mathscr{H}} = \mathbf{NP}^{\mathscr{H}}$?

(Of course, even an informal argument explaining why the question should be just as hard to answer as the case without oracle counts as an answer!)

**Motivation:** I'm aware that there are computable oracles making the relativized version of $\mathbf{P}=\mathbf{NP}$ true or false, and in fact quite easy either way (see Papadimitriou, *Computational Complexity* (1994), theorems 14.4 and 14.5, neither proof seems to adapt here), but I'm confused as to what happens when we relativize the theory of complexity to non-computable oracles (cross-links to [this question](https://cstheory.stackexchange.com/questions/1675/relativization-with-respect-to-non-recursive-oracles) as well as [this question of mine](https://cstheory.stackexchange.com/questions/47085/has-there-been-any-development-of-complexity-theory-for-other-turing-degrees-tha) which was perhaps too vague and [this other one](https://cstheory.stackexchange.com/questions/47094/complexity-relative-to-the-graph-of-the-busy-beaver-function) concernings a purposefully “weak” oracle, might be relevant here). The specific oracle $\mathscr{H}$ tries to formalize the idea that all computable functions are given “for free”, so complexity relative to it seems like a reasonable candidate for a complexity theory of $\mathbf{0'}$ (which I hope would turn out to be much easier than that of $\mathbf{0}$).

**Tags:** cc.complexity-theory, computability, oracles

> **Comments:**
> **username_1**: related: https://cs.stackexchange.com/questions/126163/under-what-kind-of-oracles-are-p-and-np-equivalent It seems to suggest that the answer depends on the particular way to enumerate Turing Machines. But with your twist that you add the result of the computation in the oracle, it might change...  
> **username_2**: How is the time complexity measured? If it's with respect to the original input, how can a polynomial-time machine even read the result of an oracle call if it's superpolynomially long? On the other hand, if it's allowed to be polynomial in the length of the output of the oracle, then all the complexity classes likely trivially collapse as you can award yourself an arbitrary amount of extra time just by posting the right query. (IOW, there is a reason why the common definition of relativised P, NP, EXP, etc. only allows *decision* oracles rather than functions.)  
> **username_0**: @EmilJeřábek Complexity is measured in the size of the input. The idea I had in mind was that the machine calls the oracle on tapes of its choice (one for $e$ and one for $n$, say), the oracle instantly replaces the input value by the output (again, on two tapes to avoid discussing encodings), and if the latter is too long to be usefully read, well, that's your problem for asking the oracle a bad question.  But if you think that's not the right problem to ask, I'm open to variations. However, yes, I think of $\mathbf{P}$ and $\mathbf{NP}$ as decision problems.  
> **username_2**: This is a reasonable oracle model, but I believe that it is then equivalent to an oracle for the decision halting problem, as the machine can compute polynomially many bits of the result (which is what it can use) by querying the oracle bit by bit. So perhaps it would be easier to define it using a decision oracle right away.  

---

## 1 answers

### Answer by username_3 on 2023-09-11. Score: 7 | Accepted answer

$\text{P}^\mathcal{H} = \text{NP}^\mathcal{H} = \text{PSPACE}^\mathcal{H}$ as noted in the [linked answer](https://cstheory.stackexchange.com/questions/39394/how-to-prove-phalt-pspacehalt) (note that the query tape counts as space). Specifically, using $n$ calls to the halting oracle, we can compute the first $n$ bits of the Chaitin's constant. Using these bits, we can compute the oracle output for all queries of length $ < ≈n$ and decide the space-bounded problem — in unlimited time without assistance or in $n^{O(1)}$ time using another call to the oracle.

The equality of the complexity classes stems not from the complexity of $\mathcal{H}$, but its closure. Let $U\mathcal{H}$ be the halting oracle, with the machine+input encoded in unary; let $U\mathcal{H}'$ also allow querying the $i$th bit of machine output (for machines that halt) with $i$ in binary. We have $\text{P}^\mathcal{H} = \text{EXP}^{U\mathcal{H}} = \text{EXP}^{U\mathcal{H'}}$. Now, for every oracle $A$, $\text{P}^{\text{EXP}^A} = \text{PSPACE}^{\text{EXP}^A}$. Roughly speaking, an $\text{EXP}^A$ oracle is sufficiently closed relative to itself; using determinacy (see [here](https://mathoverflow.net/questions/285991/determinacy-and-polynomial-time-degrees)) it can be shown that for every Borel property $p$ there is $B$ such that whether $\text{EXP}^{B,A}$ satisfies $p$ is independent of $A$.

To explore P vs NP for different representations of $0'$, let $Ω$ be the Chaitin's constant, and $UΩ$ be the Chaitin's constant with bits queried sequentially (or bit index in unary). The Chaitin's constant (machine halting probability) encodes the halting problem, but looks like random data. A caveat is that $Ω$ and I think $\text{P}^Ω$, $\text{NP}^Ω$, $\text{P}^{UΩ}$, and $\text{NP}^{UΩ}$ depend on the choice of (reasonable) encoding.

We have:   
$\text{P}^Ω ≠ \text{NP}^Ω$ (the polynomial hierarchy is infinite relative to a random oracle)  
$\text{P}^{UΩ} = \text{NP}^{UΩ}$ iff NP = RP  
$\text{P}^{U\mathcal{H}} = \text{NP}^{U\mathcal{H}}$ iff NP is in P/poly ($U\mathcal{H}$ is powerful but sparse)  
$\text{P}^{U\mathcal{H}'} = \text{NP}^{U\mathcal{H}'} = \text{PSPACE}^\mathcal{U\mathcal{H}'}$

Also, the distinction between decision oracles and function oracles is relevant to fine-grained complexity but not for P vs NP as restricting to decision oracles gives at most a quadratic slowdown.

Despite $\text{P}^\mathcal{H} = \text{NP}^\mathcal{H}$, nondeterminism can reduce the number of oracle calls: Just two calls suffice for $\mathcal{H}$ — one to certify haltings and another to certify nonhaltings. By contrast, deterministically computing the $n$th binary digit of the Chaitin's constant requires (even with unbounded time) $n-O(\log n)$ calls to the halting oracle. This is by the incompressibility of the Chaitin's constant and its capture of the halting problem; $O(\log n)$ is here because $n$ itself (if lucky) can give a logarithmic number of bits to jump-start the search for $Ω$. (And for unbounded time, using the function version of $\mathcal{H}$ does not reduce the required number of calls.)

> **Comments:**
> **username_2**: The linked argument for $\def\H{\mathcal H}\mathrm{P^\H=PSPACE^\H}$ sounds correct. However, I do not understand the subsequent discussion. As far as I can see, $\mathrm{P^\H=P^{U\H}\ne EXP^{U\H}}$: if $U$ denotes a universal TM with machines encoded in binary, and $\ulcorner U\urcorner$ is its unary code, then $\langle e,x\rangle\mapsto\langle\ulcorner U\urcorner,\langle e,x\rangle\rangle$ is a poly-time many-one reduction of $\H$ to $U\H$.  
> **username_3**: @EmilJeřábek I fixed and expanded the answer; for $U\mathcal{H}$, the input to the machine (if used) would also be encoded in unary.  
> **username_2**: Oh, I see, that makes sense. However, I still do not see why $\mathrm{EXP}^{U\mathcal H}\subseteq\mathrm P^\mathcal H$. I can simulate an exponentially long query to $U\mathcal H$ with a polynomially long query to $\mathcal H$, but how do I simulate an exponentially long computation with exponentially many oracle queries by a polynomial-time computation?  
> **username_3**: @EmilJeřábek Use can use the same Chaitin's constant argument (compute enough digits to implement $U\mathcal{H}$ up to sufficient length, and then ask $\mathcal{H}$ for the result).  
> **username_2**: Aha, all right. I think it would be good to include more details on this in the answer.  

---

