<p>Ordinary time complexity definitions require the problem/function to be computable.  However, it appears there are natural notions of computational time complexity for arbitrary hyperarithmetic problems, and beyond.  I will explain below, but my questions are:</p>
<ul>
<li>Have similar notions of time complexity for uncomputable problems been studied before?</li>
<li>How far (in terms of descriptive set theory) can we define natural reasonable time complexity notions?</li>
<li>Do we get sufficient no-speed-up results, such as an arithmetic decision problem has polynomial time complexity iff it is in P ?</li>
</ul>
<p>The only recursive decision problems polynomial time computable for the below notions are those in <span class="math-container">$P$</span>, simply because the oracles are uncomputably sparse.  (However, the oracles are not low for speed, as used in the literature, because from <span class="math-container">$0'$</span> we get sufficiently pseudorandom data.)</p>
<p><span class="math-container">$Δ^0_2$</span> <i>problems</i></p>
<p>For problems computable from the halting problem, we can ask for their time complexity given an oracle for a busy beaver function <span class="math-container">$B$</span>.  This limits the speed up for recursive functions, and also roughly corresponds to when a computable process can correctly guess the answers.  The busy beaver function is affected by the choice of representation, but we get independence-of-representation by using adversarially selected <span class="math-container">$B'$</span>, with <span class="math-container">$∃c \, ∀n \, B(n) ≤ B'(n) ≤ B(n^c)$</span>.  Time complexity <span class="math-container">$B(n^{O(1)})$</span> would mean an algorithm that for every <span class="math-container">$B'$</span> works in <span class="math-container">$B(n^{O(1)}$</span>) time.  (Whether some decision problems not in P have <span class="math-container">$n^{O(1)}$</span> complexity is part of the question; note that an above <span class="math-container">$c$</span> is not disclosed.)</p>
<p>The independence of representation affects the precision with which we can state the complexity, but using compact representations, we can reduce <span class="math-container">$n^{O(1)}$</span> to <span class="math-container">$n+O(\log n)$</span> (<span class="math-container">$n$</span> is the number of bits).  For <span class="math-container">$n+O(1)$</span>, I think there are inequivalent (for our purposes) choices of busy beaver, including the regular (the usual one), prefix-free (binary alphabet), autohalt-on-input-end (binary alphabet), and (see <span class="math-container">$B_0$</span> below) Chaitin's constant based.</p>
<p><i>Hyperarithmetic problems</i></p>
<p>We will use a sequence of busy-beaver-like functions, adjusted to get representation independence; one function per Turing jump.</p>
<p>Fix an ordinal notation system for a limit ordinal.  Fix an oracle universal Turing machine <span class="math-container">$U$</span>; the choice of <span class="math-container">$U$</span> will not affect the complexity notion.  Let <span class="math-container">$B_α(n) = \min(t:P_∞ - P_t &lt; 2^{-n})$</span> where <span class="math-container">$P_t$</span> is halting probability for <span class="math-container">$t$</span> steps using <span class="math-container">$U$</span>, (the notation for) <span class="math-container">$α$</span> and <span class="math-container">$0^{(α)}$</span> (<span class="math-container">$α$</span>th Turing jump of 0) oracle, and random data.</p>
<p>An adversary gives <span class="math-container">$B'$</span> such that <span class="math-container">$∃c ∀α ∀n \, B_α(n) ≤ B'_α(n) ≤ B_α(n+B_{α+2}(c))$</span> (unless we want to give the adversary a different amount of leeway), and an algorithm must work for all adversaries.</p>
<p>The use of <span class="math-container">$B_{α+2}(c)$</span> rather than <span class="math-container">$c$</span> is to give independence from the ordinal notation system (for the same ordinal); converting <span class="math-container">$α$</span> to a different system is <span class="math-container">$Δ^0_{α+3}$</span> (but converting <span class="math-container">$0^{(α)}$</span> oracle is not otherwise a problem).  The impact of <span class="math-container">$B_{α+2}(c)$</span> rather than <span class="math-container">$c$</span> on complexity is minor, as typically either <span class="math-container">$α$</span> is constant or <span class="math-container">$α+O(1)$</span> in place of <span class="math-container">$α$</span> is good enough.  If desired (but this affects the complexity notion), it can be mitigated by using <span class="math-container">$B_{α+2}(c)$</span> for additively indecomposable ordinals, <span class="math-container">$B_{α+1}(c)$</span> for their successors, and <span class="math-container">$c$</span> for other ordinals, and we can reduce this further by imposing conditions on ordinal notation systems.</p>
<p><i>Beyond hyperarithmetic</i></p>
<p>To get all true <span class="math-container">$Π^1_1$</span> statements, we could allow all ordinal notation systems and adjust the adversary appropriately, but the simplest change is to use a recursive pseudowellordering; its choice will not affect the complexity.  <span class="math-container">$B_x$</span> will be defined for well-founded <span class="math-container">$x$</span>, while for ill-founded <span class="math-container">$x$</span>, <span class="math-container">$B'_x(n)&gt;m$</span> query will always return true (note that this does not allow confirming that <span class="math-container">$x$</span> is ill-founded).</p>
<p>For zero hyperjump (or Kleene's <span class="math-container">$\mathcal{O}$</span>), we have an analog of Chaitin's constant:  Probability that the above <span class="math-container">$U$</span> (or another suitable Turing machine; no oracles besides random data) outputs a code for a recursive well-ordering and stops.  We assign the halting time to be <span class="math-container">$B'_α(0)$</span> where <span class="math-container">$α$</span> is the ordinal whose code was output (i.e. the length of the well-ordering), and define <span class="math-container">$B$</span> and <span class="math-container">$B'$</span> accordingly.  The complexity notion is unaffected by any assignment of halting times that is between <span class="math-container">$B'_α(0)$</span> and for example <span class="math-container">$B'_{α+ω}(c+\text{actual_halting_time})$</span>, but note that we use <span class="math-container">$B'$</span> rather than <span class="math-container">$B$</span>.  To go beyond, we can iterate the construction and the hyperjump.  Note that there are oracle Turing machines that for every oracle <span class="math-container">$A$</span> implement an <span class="math-container">$A$</span>-(recursive pseudowellordering).</p>

CC BY-SA 4.0
2024-09-28T06:28:17.973Z
Correction:  The failure of low-for-speed here is analogous to Blum's speedup theorem rather than due to pseudorandomness.
Dmytro Taranovsky
CC BY-SA 4.0
2024-09-29T10:29:45.443Z
Moschovakis' notion of a computation theory might be relevant here; cf. https://www.sciencedirect.com/science/article/abs/pii/S0049237X0871231X. These is an axiomatic treatment of higher recursion theory in which (ordinal) length of a computation is a primitive notion.
Siddharth
<cc.complexity-theory><time-complexity><computability><oracles>
Time complexity beyond recursive functions
Dmytro Taranovsky
# Time complexity beyond recursive functions

(Asked by: username_0 on 2024-09-28)

Ordinary time complexity definitions require the problem/function to be computable. However, it appears there are natural notions of computational time complexity for arbitrary hyperarithmetic problems, and beyond. I will explain below, but my questions are:

* Have similar notions of time complexity for uncomputable problems been studied before?
* How far (in terms of descriptive set theory) can we define natural reasonable time complexity notions?
* Do we get sufficient no-speed-up results, such as an arithmetic decision problem has polynomial time complexity iff it is in P ?

The only recursive decision problems polynomial time computable for the below notions are those in $P$, simply because the oracles are uncomputably sparse. (However, the oracles are not low for speed, as used in the literature, because from $0'$ we get sufficiently pseudorandom data.)

$Δ^0\_2$ *problems*

For problems computable from the halting problem, we can ask for their time complexity given an oracle for a busy beaver function $B$. This limits the speed up for recursive functions, and also roughly corresponds to when a computable process can correctly guess the answers. The busy beaver function is affected by the choice of representation, but we get independence-of-representation by using adversarially selected $B'$, with $∃c \, ∀n \, B(n) ≤ B'(n) ≤ B(n^c)$. Time complexity $B(n^{O(1)})$ would mean an algorithm that for every $B'$ works in $B(n^{O(1)}$) time. (Whether some decision problems not in P have $n^{O(1)}$ complexity is part of the question; note that an above $c$ is not disclosed.)

The independence of representation affects the precision with which we can state the complexity, but using compact representations, we can reduce $n^{O(1)}$ to $n+O(\log n)$ ($n$ is the number of bits). For $n+O(1)$, I think there are inequivalent (for our purposes) choices of busy beaver, including the regular (the usual one), prefix-free (binary alphabet), autohalt-on-input-end (binary alphabet), and (see $B\_0$ below) Chaitin's constant based.

*Hyperarithmetic problems*

We will use a sequence of busy-beaver-like functions, adjusted to get representation independence; one function per Turing jump.

Fix an ordinal notation system for a limit ordinal. Fix an oracle universal Turing machine $U$; the choice of $U$ will not affect the complexity notion. Let $B\_α(n) = \min(t:P\_∞ - P\_t < 2^{-n})$ where $P\_t$ is halting probability for $t$ steps using $U$, (the notation for) $α$ and $0^{(α)}$ ($α$th Turing jump of 0) oracle, and random data.

An adversary gives $B'$ such that $∃c ∀α ∀n \, B\_α(n) ≤ B'\_α(n) ≤ B\_α(n+B\_{α+2}(c))$ (unless we want to give the adversary a different amount of leeway), and an algorithm must work for all adversaries.

The use of $B\_{α+2}(c)$ rather than $c$ is to give independence from the ordinal notation system (for the same ordinal); converting $α$ to a different system is $Δ^0\_{α+3}$ (but converting $0^{(α)}$ oracle is not otherwise a problem). The impact of $B\_{α+2}(c)$ rather than $c$ on complexity is minor, as typically either $α$ is constant or $α+O(1)$ in place of $α$ is good enough. If desired (but this affects the complexity notion), it can be mitigated by using $B\_{α+2}(c)$ for additively indecomposable ordinals, $B\_{α+1}(c)$ for their successors, and $c$ for other ordinals, and we can reduce this further by imposing conditions on ordinal notation systems.

*Beyond hyperarithmetic*

To get all true $Π^1\_1$ statements, we could allow all ordinal notation systems and adjust the adversary appropriately, but the simplest change is to use a recursive pseudowellordering; its choice will not affect the complexity. $B\_x$ will be defined for well-founded $x$, while for ill-founded $x$, $B'\_x(n)>m$ query will always return true (note that this does not allow confirming that $x$ is ill-founded).

For zero hyperjump (or Kleene's $\mathcal{O}$), we have an analog of Chaitin's constant: Probability that the above $U$ (or another suitable Turing machine; no oracles besides random data) outputs a code for a recursive well-ordering and stops. We assign the halting time to be $B'\_α(0)$ where $α$ is the ordinal whose code was output (i.e. the length of the well-ordering), and define $B$ and $B'$ accordingly. The complexity notion is unaffected by any assignment of halting times that is between $B'\_α(0)$ and for example $B'\_{α+ω}(c+\text{actual\_halting\_time})$, but note that we use $B'$ rather than $B$. To go beyond, we can iterate the construction and the hyperjump. Note that there are oracle Turing machines that for every oracle $A$ implement an $A$-(recursive pseudowellordering).

**Tags:** cc.complexity-theory, time-complexity, computability, oracles
> **Comments:**
> **username_0**: Correction:  The failure of low-for-speed here is analogous to Blum's speedup theorem rather than due to pseudorandomness.  
> **username_1**: Moschovakis' notion of a computation theory might be relevant here; cf. https://www.sciencedirect.com/science/article/abs/pii/S0049237X0871231X. These is an axiomatic treatment of higher recursion theory in which (ordinal) length of a computation is a primitive notion.  

---

## 0 answers

