Czy złożoność Kołmogorowa w tabelach prawdy problemu zatrzymania jest znana asymptotycznie?

Pozwolić $HALT_n$ oznacz ciąg długości $2^n$ odpowiadający tabeli prawdy problemu zatrzymania dla danych wejściowych długości $n$.

Jeśli sekwencja złożoności Kołmogorowa $K(HALT_n)$ byli $O(1)$, wtedy jeden z ciągów porad byłby używany nieskończenie często, a TM z tym ciągiem zakodowanym na stałe byłby w stanie rozwiązać $HALT$ równomiernie nieskończenie często, o czym wiemy, że tak nie jest.

Dokładniejsza analiza argumentu diagonalizacji faktycznie to pokazuje $K(HALT_n)$ jest przynajmniej $n - \omega (1)$, więc wraz z trywialną górną granicą mamy:

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

Ta dolna granica została odnotowana we wstępie do najnowszej pracy Fortnow i Santhanama `` Nowe niejednorodne niższe granice dla klas jednolitej złożoności '' i przypisują ją folklorowi. Zasadniczo, jeśli ciąg porad jest krótszy niż długość wejściowa, to nadal możemy przekątnie względem maszyn z co najwyżej taką ilością porad.

(Edycja: Właściwie we wcześniejszej wersji artykułu przypisywali go folklorowi, teraz chyba mówią, że to adaptacja Hartmanisa i Stearnsa).

W rzeczywistości w tym artykule zajmują się twierdzeniami o hierarchii czasu i przedstawiają rzeczy związane z zasobami związanymi z $t$kroki czasowe, a nie nieograniczona złożoność Kołmogorowa. Ale dowód na wynik `` folkloru '' jest taki sam w przypadku nieograniczonym.

Jednym z powodów, dla których dbają o porady dotyczące dolnych granic, jest to, że wiąże się to z dolnymi granicami obwodu i derandomizacją w paradygmacie `` twardość vs. losowość ''. Na przykład, jeśli problem kanoniczny można rozwiązać na czas$2^n$ ma tabele prawdy, które wymagają porady $2^{\epsilon n}$ w celu obliczenia na czas $2^{\epsilon n}$, to te tabele prawdy nie mają obwodów wielkości $2^{\epsilon n}$ albo tak $P = BPP$ przez słynny wynik Impagliazzo i Wigderson.

Pytać o $K(HALT_n)$zamiast tego nie ma żadnych takich aplikacji, ale może być łatwiejsze do rozwiązania. Łatwiej jest także stwierdzić, nie będąc zależnym od parametru związanego z czasem - jest to raczej naturalny problem, który mógł być już zbadany.

Czy są jakieś lepsze dolne lub górne granice? $K(HALT_n)$znany oprócz wyniku `` folkloru ''? Czy któraś z dolnych lub górnych granic jest powyżej ciasnych?

Uwaga: Jest jeszcze jeden fajny post na temat złożoności obwodu problemu zatrzymania, który można uznać za prawie maksymalny dzięki argumentowi nakreślonemu przez Emila Jerabka tutaj: /mathpro/115275/non-uniform-complexity problem zatrzymania

Zasadniczo wykorzystuje sztuczkę, w której możemy obliczyć (z losowym dostępem) tablicę leksykograficzną pierwszej prawdy o złożoności obwodu (dużej) w klasie $E^{NP^{NP}}$. I możemy zredukować to obliczenie do zapytania dotyczącego problemu zatrzymania, a redukcja ta ma niską złożoność obwodu. Więc,$HALT$ musi mieć dużą złożoność obwodów - jeśli nie, to funkcja ta miałaby również niską złożoność.

Chociaż wydaje się to powiązane, nie sądzę, aby ten argument coś na to wskazywał $K(HALT_n)$. (Możliwe, że złożoność czasowa Kołmogorowa związana z czasem$HALT$jest duża, co sugeruje złożoność obwodu, ale gdy ograniczenie czasowe jest złagodzone, złożoność dramatycznie spada.) Myślę, że analogiczny argument pokazuje, że gdybyśmy mieli wyrocznię z powodu problemu zatrzymania, moglibyśmy wspierać dostęp losowy zapytania do leksykograficznie pierwszego ciągu nieściśliwego. Musimy jednak wykonać szereg adaptacyjnych zapytań, których nie można bezpośrednio zredukować$HALT$o ile mi wiadomo. Ponadto ciągi zapytań muszą być wykładniczo duże afaik, więc ostatecznie pokazuje tylko to$HALT_{2^n}$ ma co najmniej złożoność $2^n$ afaict, a to nie bije argumentu `` folklor ''.

Moje doświadczenie w złożoności Kołmogorowa jest niestety dość słabe $K(HALT_n)$już znany z innego argumentu? Być może istnieje sztuczka z wykorzystaniem Symetrii Informacji?

Czy może jest lepsza górna granica, którą przegapiłem?

Jedną rzeczą, która może wydawać się dziwna, jest powrót do $DTIME$ustawieniu, spodziewamy się uzyskania porady niższej granicy, gdy skrócimy czas poniżej naiwnego algorytmu. Kiedy masz wystarczająco dużo czasu, aby uruchomić naiwny algorytm, to oczywiście można go skompresować. W przypadku$K(HALT_n)$, nie ma w ogóle czasu, więc może mamy `` tyle samo czasu '' co przeciwnik i nie powinniśmy oczekiwać, że będzie on maksymalnie nieściśliwy. Niemniej jednak diagonalizacja działa również w nieograniczonych ustawieniach - wydaje się, że dla każdej maszyny istnieje maszyna, która robi to samo co ta maszyna, a następnie robi coś innego, więc zawsze jest ktoś, kto ma więcej czasu niż ty. Może więc przeciwnik zawsze ma więcej czasu niż my ...

Hmm, okazuje się, że w rzeczywistości pasująca górna granica nie jest zbyt trudna:

Aby stworzyć tabelę prawdy $HALT_n$ w ograniczonym czasie jedyną potrzebną informacją jest liczba maszyn o maksymalnej długości opisu $n$które zatrzymują się. Ta liczba nie jest większa niż$2^{n}$, więc można to przedstawić za pomocą około $n$bitów Następnie możemy uruchomić wszystkie takie maszyny równolegle i uruchamiać je, dopóki tak wielu z nich się nie zatrzyma, a pozostałe nie będą się zatrzymywać.

Sądzę więc, że argument folklorystyczny jest tutaj ścisły. Mamy

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

i $K(HALT_n)$ jest dobrze zdefiniowany aż do dodatku $O(1)$ tak czy inaczej, w zależności od naszego wyboru uniwersalnej maszyny Turinga.

NB: Jako urocza premia, ten dowód pokazuje, że $n$-bitowy ciąg znaków odpowiadający co najwyżej liczbie maszyn o długości opisu $n$ którego zatrzymanie jest struną nieściśliwą - gdyby była ściśliwa, wówczas górna granica tutaj byłaby ściślejsza, co byłoby sprzeczne z dolną granicą.