Is P=NP relative to the halting oracle?

Question

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 as well as this question of mine which was perhaps too vague and this other one 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}$).

Answer 1

$\text{P}^\mathcal{H} = \text{NP}^\mathcal{H} = \text{PSPACE}^\mathcal{H}$ as noted in the linked answer (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) 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.)