9
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ related: cs.stackexchange.com/questions/126163/… 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... $\endgroup$
    – Denis
    Sep 8, 2023 at 11:54
  • $\begingroup$ 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.) $\endgroup$ Sep 8, 2023 at 14:29
  • $\begingroup$ @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. $\endgroup$
    – Gro-Tsen
    Sep 8, 2023 at 15:06
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 8, 2023 at 15:38

1 Answer 1

6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$ Sep 11, 2023 at 12:10
  • $\begingroup$ @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. $\endgroup$ Sep 11, 2023 at 15:22
  • $\begingroup$ 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? $\endgroup$ Sep 11, 2023 at 17:11
  • 1
    $\begingroup$ @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). $\endgroup$ Sep 11, 2023 at 17:46
  • $\begingroup$ Aha, all right. I think it would be good to include more details on this in the answer. $\endgroup$ Sep 12, 2023 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.