La complexité de Kolmogorov des tables de vérité du problème d'arrêt est-elle connue de manière asymptotique?

Soit $HALT_n$ la chaîne de longueur $2^n$ correspondant à la table de vérité du problème d'arrêt pour les entrées de longueur $n$ .

Si la séquence des complexités de Kolmogorov $K(HALT_n)$ était $O(1)$ , alors l'une des chaînes de conseil serait utilisée infiniment souvent, et une MT avec cette chaîne codée en dur serait capable de résoudre $HALT$ uniformément infiniment souvent, ce qui, nous le savons, n'est pas le cas.

Un examen plus approfondi de l'argument de la diagonalisation montre en fait que $K(HALT_n)$ est au moins $n - \omega (1)$ , donc avec la borne supérieure triviale, nous avons:

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

Cette limite inférieure est notée dans l'introduction d'un récent article de Fortnow et Santhanam `` New Non-uniform Lower Bounds for Uniform Complexity Classes '' , et ils l'attribuent au folklore. Fondamentalement, si la chaîne de conseil est plus courte que la longueur d'entrée, nous pouvons toujours diagonaliser par rapport aux machines avec au plus cette quantité de conseil.

(Edit: En fait, dans une version antérieure de l'article, ils l'attribuaient au folklore, je suppose qu'ils disent maintenant que c'est une adaptation de Hartmanis et Stearns.)

$t$

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

$K(HALT_n)$

$K(HALT_n)$

Remarque: Il existe un autre bon article sur la complexité du circuit du problème d'arrêt, qui peut être considéré comme presque maximal par un argument esquissé par Emil Jerabek ici: /mathpro/115275/non-uniform-complexity -du-problème-d'arrêt

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

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

$K(HALT_n)$

Ou, y a-t-il une meilleure limite supérieure que j'ai ratée?

$DTIME$$K(HALT_n)$, il n'y a pas de temps du tout, alors peut-être avons-nous `` la même '' quantité de temps que l'adversaire, et ne devrions pas nous attendre à ce qu'il soit au maximum incompressible. Néanmoins, la diagonalisation fonctionne également dans le cadre sans restriction - il semble que pour toute machine, il existe une machine qui fait la même chose que cette machine, puis fait autre chose, donc il y a toujours quelqu'un qui a plus de temps que vous. Alors peut-être que l'adversaire a toujours plus de temps que nous après tout ...

Hmm, il se trouve qu'il y a en fait une limite supérieure correspondante qui n'est pas trop difficile:

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

Donc, je suppose que l'argument du folklore est serré ici. On a

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

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

$n$$n$