<p>(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.)</p>
<p>Complexity theory can be very broadly described as the finer structure of the subsets of <span class="math-container">$\mathbb{N}$</span>, or functions <span class="math-container">$\mathbb{N}\to\mathbb{N}$</span>, constituting the Turing degree <span class="math-container">$\mathbf{0}$</span> (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?”.</p>
<p>This suggests the following natural question: is there some analogous theory for the finer structures of other Turing degrees, or Turing ideals?</p>
<p>Of particular interest would be <span class="math-container">$\mathbf{0}'$</span> (sets computable with an oracle solving the halting problem) or hyperarithmetic sets.  One naïve attempt at creating a kind of complexity theory for <span class="math-container">$\mathbf{0}'$</span> (the simplest Turing degre beyond <span class="math-container">$\mathbf{0}$</span>) would be to count the number of calls to the oracle as “resource” taken (or somewhat relatedly, simply use standard complexity classes like <span class="math-container">$\mathbf{P}$</span> and so on, but relativized to the halting oracle), but maybe this is too simplistic.</p>
<p>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 <span class="math-container">$\mathsf{E}$</span>: intuitively, a hyperarithmetic machine can ask “does this (other) hyperarithmetic machine, which always terminates, ever produce a value <span class="math-container">$&gt;0$</span>?”, 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 <span class="math-container">$\omega_1^{\mathrm{CK}}$</span>, which may or may not provide a satisfactory “complexity theory”.</p>
<p>So, anyway, have such theories been developed?  I would expect that a natural analogue of <span class="math-container">$\mathbf{PR}$</span> (primitive recursive functions) is easy to define for higher Turing degrees, but what about finer classes like <span class="math-container">$\mathbf{P}$</span>?</p>

CC BY-SA 4.0
2020-06-22T13:37:40.893Z
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.
Emil Jeřábek
CC BY-SA 4.0
2020-06-22T18:44:12.093Z
Are you looking for [complexity relative to an oracle](http://theory.stanford.edu/~trevisan/cs254-14/lecture04.pdf)?
Andrej Bauer
CC BY-SA 4.0
2020-06-22T21:38:28.840Z
You may find this paper useful:      http://www.cs.tau.ac.il/thesis/thesis/Falkovich.Evgenia-PhD.pdf
Avi Tal
CC BY-SA 4.0
2020-06-23T00:36:58.347Z
@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.)
Gro-Tsen
CC BY-SA 4.0
2020-06-23T00:42:04.010Z
@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.
Gro-Tsen
CC BY-SA 4.0
2020-06-23T05:34:37.103Z
Yes, what I wrote applies to the halting problem, but not necessarily to other oracles Turing equivalent to it.
Emil Jeřábek
<cc.complexity-theory><computability>
Has there been any development of complexity theory for other Turing degrees than 0?
Gro-Tsen
# Has there been any development of complexity theory for other Turing degrees than 0?

(Asked by: username_0 on 2020-06-22)

(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}$?

**Tags:** cc.complexity-theory, computability
> **Comments:**
> **username_1**: 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.  
> **username_2**: Are you looking for [complexity relative to an oracle](http://theory.stanford.edu/~trevisan/cs254-14/lecture04.pdf)?  
> **username_3**: You may find this paper useful:      http://www.cs.tau.ac.il/thesis/thesis/Falkovich.Evgenia-PhD.pdf  
> **username_0**: @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.)  
> **username_0**: @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.  
> **username_1**: Yes, what I wrote applies to the halting problem, but not necessarily to other oracles Turing equivalent to it.  

---

## 0 answers

