This question is approximately cross-posted from Theoretical Computer Science Stack Exchange: http://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