A complexidade de Kolmogorov das tabelas da verdade do problema da parada é conhecida assintoticamente?

Vamos $HALT_n$ denotar a cadeia de comprimento $2^n$ correspondente à tabela verdade do problema de parada para entradas de comprimento $n$ .

Se a sequência das complexidades de Kolmogorov $K(HALT_n)$ fosse $O(1)$ , uma das sequências de aconselhamento seria usada infinitamente com frequência, e uma TM com essa sequência codificada seria capaz de resolver $HALT$ uniformemente infinitamente, o que sabemos que não é o caso.

Uma inspeção mais detalhada do argumento da diagonalização mostra que $K(HALT_n)$ é pelo menos $n - \omega (1)$ ; portanto, junto com o limite superior trivial, temos:

$n - \omega(1) \leq K(HALT_n) \leq 2^n + O(1)$

Esse limite inferior é observado na introdução de um artigo recente de Fortnow e Santhanam `` Novos limites inferiores não uniformes para classes de complexidade uniformes '' , e eles o atribuem ao folclore. Basicamente, se a sequência de recomendações for menor que o comprimento da entrada, ainda poderemos diagonalizar as máquinas com, no máximo, essa quantidade de recomendações.

(Edit: Na verdade, em uma versão anterior do artigo que eles atribuíram ao folclore, acho que agora eles dizem que é apenas uma adaptação de Hartmanis e Stearns.)

$t$

$2^n$$2^{\epsilon n}$$2^{\epsilon n}$$2^{\epsilon n}$$P = BPP$

Em vez disso, perguntar sobre $K(HALT_n)$ não tem nenhum desses aplicativos, mas pode ser mais fácil resolvê-lo. Também é mais fácil declarar, sem qualquer dependência de um parâmetro com limite de tempo - é um problema natural que já pode ter sido estudado.

Existem limites inferiores ou superiores melhores em $K(HALT_n)$ conhecidos além do resultado do `` folclore ''? Os limites inferior ou superior estão bem apertados?

Nota: Há outro post interessante sobre a complexidade do circuito do problema de parada, que pode ser visto como quase máximo por um argumento esboçado por Emil Jerabek aqui: /mathpro/115275/non-uniform-complexity -do-problema-de-parar

$E^{NP^{NP}}$$HALT$

$K(HALT_n)$$HALT$$HALT$$HALT_{2^n}$$2^n$

$K(HALT_n)$

Ou existe um limite superior melhor que eu perdi?

$DTIME$$K(HALT_n)$, não há tempo limite, portanto, talvez tenhamos `` a mesma '' quantidade de tempo que o adversário e não devemos esperar que seja maximamente incompressível. No entanto, a diagonalização também funciona na configuração irrestrita - parece que para qualquer máquina, existe uma máquina que faz a mesma coisa que ela e depois faz outra coisa; portanto, sempre há alguém que tem mais tempo do que você. Então, talvez o adversário sempre tenha mais tempo do que nós, afinal ...

Hmm, acontece que na verdade há um limite superior correspondente que não é muito difícil:

$HALT_n$$n$$2^{n}$$n$

Então, acho que o argumento do folclore é apertado aqui. Nós temos

$n - \omega(1) \leq K(HALT_n) \leq n + O(1)$

$K(HALT_n)$$O(1)$

$n$$n$