(I'm not sure if this question is better suited for MathOverflow or here. I'll try here first, and move over to MO later if it appears to be more appropriate.)

Complexity theory can be very broadly described as the finer structure of the subsets of $\mathbb{N}$, or functions $\mathbb{N}\to\mathbb{N}$, constituting the Turing degree $\mathbf{0}$ (of computable sets), where we ask ourselves “OK, this set is computable by a Turing machine, now how much resources (time, memory, etc.) does it take to actually compute it?”.

This suggests the following natural question: is there some analogous theory for the finer structures of other Turing degrees, or Turing ideals?

Of particular interest would be $\mathbf{0}'$ (sets computable with an oracle solving the halting problem) or hyperarithmetic sets. One naïve attempt at creating a kind of complexity theory for $\mathbf{0}'$ (the simplest Turing degre beyond $\mathbf{0}$) would be to count the number of calls to the oracle as “resource” taken (or somewhat relatedly, simply use standard complexity classes like $\mathbf{P}$ and so on, but relativized to the halting oracle), but maybe this is too simplistic.

Hyperarithmetic sets are another interesting possibility because there is a classical analogy (due, I think, to Kreisel) between computability and hyperarithmetical theory, and “hyperarithmetic machines” can be described as Turing machines with access to a certain kind of generalized oracle (viz., the type-2 functional $\mathsf{E}$: intuitively, a hyperarithmetic machine can ask “does this (other) hyperarithmetic machine, which always terminates, ever produce a value $>0$?”, so we could try counting the number of times it does this); also, hyperarithmetic sets come with their own hierarchy from the Turing degrees (the hyperarithmetic hierarchy, constructed by transfinitely iterating the Turing jump up to $\omega_1^{\mathrm{CK}}$, which may or may not provide a satisfactory “complexity theory”.

So, anyway, have such theories been developed? I would expect that a natural analogue of $\mathbf{PR}$ (primitive recursive functions) is easy to define for higher Turing degrees, but what about finer classes like $\mathbf{P}$?

  • 1
    $\begingroup$ Note that if you have a halting problem oracle, you can ask it to do all the computations for you. That is, I believe that if you can compute something by a Turing machine using $q(n)$ calls to a $0'$ oracle, you can also compute it in time $O(n+q(n))$ or so using $q(n)+1$ calls to a $0'$ oracle. Thus, the number of oracle calls is probably the only meaningful resource in this setting. $\endgroup$ Commented Jun 22, 2020 at 13:37
  • 1
    $\begingroup$ Are you looking for complexity relative to an oracle? $\endgroup$ Commented Jun 22, 2020 at 18:44
  • $\begingroup$ You may find this paper useful: cs.tau.ac.il/thesis/thesis/Falkovich.Evgenia-PhD.pdf $\endgroup$
    – Avi Tal
    Commented Jun 22, 2020 at 21:38
  • $\begingroup$ @EmilJeřábek This isn't obvious to me, I have to think about it. But even if you're right (which I have no reason to doubt), I assume you're taking the halting problem as $\mathbf{0}'$ oracle: there could be other oracles in the same Turing degree but which have a very different effect on complexity, couldn't there? (E.g., the graph of the Busy-Beaver function is Turing-equivalent to the halting problem, but probably doesn't kill complexity as much.) $\endgroup$
    – Gro-Tsen
    Commented Jun 23, 2020 at 0:36
  • $\begingroup$ @AndrejBauer It could be, and Emil Jeřábek's comment suggests so (but see my comment in reply to him). But assuming it is, is there any study of complexity classes, say, $\mathbf{P}$, relative to a specific NON-recursive oracle? Any interesting examples of problems falling in these complexity classes? Like, what's the complexity class of the Busy-Beaver function relative to the halting problem oracle? I wonder if such problems have been studied to any extent. $\endgroup$
    – Gro-Tsen
    Commented Jun 23, 2020 at 0:42


Your Answer

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

Browse other questions tagged or ask your own question.