# Non-uniform complexity of the halting problem

This question is approximately cross-posted from Theoretical Computer Science Stack Exchange: https://cstheory.stackexchange.com/questions/14445/complexity-of-the-halting-problem

What can be said about the non-uniform circuit complexity $C(n)$ of the halting problem? Obviously it is $O(2^n)$ as any other decision problem. However I don't know any non-trivial bound.

A related measure of complexity is the time-complexity $T(n)$ with infinite advice (i.e. we allow an extra-tape in our Turing machine which carries an infinite-amount of information in the initial state). This also gives the obvious upper bound $O(2^n)$ by storing an infinite look-up table on this tape.

The two measures of complexity are related as follows. Consider $R_n$ a family of circuits solving a decision problem $S$. Then we can construct an infinite-advice program $H$ for solving $S$ by encoding $R_n$ as advice. This yields

$$T(n) = O(n C(n) \ln C(n))$$

On the other hand if we have $H$ an infinite-advice program solving $S$, we can construct the circuit $R_n$ representing the computation process of $H$ on an input of size $n$. The size of this circuit is the product of the spatial complexity by the temporal complexity so

$$C(n) = O(T(n)^2)$$

Note that if the halting problem is in $P/poly$ i.e. $C$ is polynomial, then $NP \subset P/poly$ (which implies $PH = \Sigma_2$). To see this consider $S \subset \lbrace 0,1 \rbrace^*$ a decision problem in $NP$ and $V$ a verifier program for $S$. Deciding whether $x \in S$ is equivalent to solving the halting problem for the following program $Q_x$: "Loop over all $p \in \lbrace 0,1 \rbrace^*$, halt if $V(x,p) = 1$". The size of $Q_x$ is the same as the size of $x$, up to a constant. Therefore if we can solve the halting problem for $Q_x$ in polynomial time with polynomial advice, we can decide $x \in S$ in polynomial time with polynomial advice

If the halting problem is in $coNP/poly$ then $NP \subset coNP/poly$. This is due to reasoning similar to above i.e. an existential quantifier can be replaced by a universal quantifier at the cost of requiring polynomial advice. I think this also implies some kind of collapse of the polynomial hierarchy

It is possible to construct a specific infinite-advice algorithm of optimal complexity, analogous to Levin search for $NP$ problems. As opposed to the case of $NP$, there is no way to verify correctness of solutions, on the other hand it is possible to restrict the dovetailing only to valid programs. This is done by encoding all programs which solve the halting problem together with their respective infinite advice sequences in the infinite advice of our algorithm. The penalty incurred by using this encoding is at most polynomial, hence the resulting algorithm has complexity which is optimal up to a polynomial

Every r.e. language is polynomial-time reducible to the halting problem. Since there are computable languages (indeed, in $\Delta^E_3$) having the maximum possible circuit complexity for every length $n$ (which is asymptotically $2^n/n$), the halting problem also has exponential circuit complexity. The exact complexity will depend on the particular representation of algorithms in the definition of the halting problem, and specifically, on the complexity of the reduction function which hardwires an input string into a fixed algorithm. In the most obvious representations, this function blows up the input length only linearly and can be made computable by linear-size circuits, hence we get $2^{\Theta(n)}$ as the circuit complexity of the halting problem. If the halting problem is formulated directly for algorithms accepting an input, the reduction function increases the input length by an additive constant and has essentially constant complexity, so the circuit complexity of the halting problem is $\Theta(2^n/n)$ in such a formulation.