Hipoteza Kołmogorowa, że

W swojej książce Boolean Function Complexity Stasys Jukna wspomina (strona 564), że Kołmogorow wierzył, że każdy język w P ma obwody o wielkości liniowej. Nie ma wzmianki o referencjach i nie mogłem znaleźć niczego online. Czy ktoś wie o tym więcej?

[Podążając za sugestią Kaveha, zamieszczam (nieco rozszerzony) komentarz jako odpowiedź]

Ta „domysł” Kołmogorowa to tylko plotka. Nigdzie nie został opublikowany. W byłym ZSRR „publikowanie” matematyki oznaczało coś innego niż to, co robi dzisiaj: wygłaszanie wykładu na seminarium lub mówienie kolegom podczas lunchu. Liczenie papierów nie było problemem. (Właściwie to także zaleciłem ten sposób robienia matematyki.) Nie mogę wykluczyć możliwości, że ta „domysł” została właśnie przekazana Levinowi przez Kołmogorowa podczas ich spaceru na seminarium na Uniwersytecie Moskiewskim. Więc nie bierz tego zbyt poważnie jako formalnego przypuszczenia; to tylko plotka, że ​​(nie trzeba dodawać) nie była obalana przez lata. Ale ponieważ gigant, taki jak Kołmogorow, poważnie pomyślał o tym problemie i nie wykluczył możliwości „mocy diabła”, przypuszczenie należy potraktować wystarczająco poważnie,

Oto (bardzo, bardzo szorstka) spekulacja na temat mojego rozumienia tego przypuszczenia. Nasza (najwyraźniej błędna) intuicja dotycząca działania obwodów polega na oglądaniu obliczeń przez program jako proces sekwencyjny, który stopniowo zbiera informacje o ciągu wejściowym. Ta intuicja zapożyczona jest z naszego poglądu na to, jak działa maszyna Turinga. Ale każdy łańcuch wejściowy określa obwód (obserwując lub ). A żeby obwód był poprawny, wystarczy, że zestawy obwodów dla i są rozłączne. To znaczy, że obwód jest zwartym „lokalnym kodowaniem” danej partycji$x$$f(x)=1$$f(x)=0$$f^{-1}(1)$$f^{-1}(0)$$n$-sześcian. Długość tego kodu jest złożonością Kołmogorowa danego ciągu binarnego o długości . Jednak algorytm wielomianowy robi więcej: daje jedno „globalne kodowanie” całego nieskończonego ciągu dla wszystkich . Teraz nieskończony ciąg pozwalający na kodowanie o rozmiarze musi być „prosty”, a jego przedrostki „powinny” pozwalać na jeszcze bardziej kompaktowe kodowanie „lokalne”. Oczywiście pozostaje tajemnicą, dlaczego Kołmogorow uważał, że „lokalne” kodowanie nawet wielkości dla niektórych może być wtedy wystarczające ...$f_n$$2^n$$f$$n$$f$$n^c$$cn$$c$

PS Przepraszam, zapomniałem dodać: Doskonałym potwierdzeniem mojej „tezy”, że obwody powinny być postrzegane raczej jako kody (statyczne) niż ( algorytmy ) , to słynne twierdzenie Davida Barringtona, że ​​cała klasa może być symulowana przez wielomian -rozmiarowe programy rozgałęziające o szerokości 5. Widok „zbieranie informacji” jest tutaj całkowicie błędny: nawet nie jest jasne, jak obliczyć funkcję większości, zachowując tylko 5 bitów informacji. Sprytnym pomysłem Davida było po prostu kodowanie$NC^1$zachowanie danej formuły przez poszczególne sekwencje 5-permutacji oraz pokazanie, że akceptowane i odrzucane ciągi otrzymają różne kody. Chodzi o to, że program rozgałęziający również nie „oblicza” --- raczej koduje ciągi wejściowe przez swoje podprogramy: gdy przychodzi wejście, niespójne zbocza znikają, a my mamy kod tego wejścia.

Nie jestem tak dobrze zaznajomiony z tym tematem jak Stasys, ale słyszałem inne uzasadnienie tej hipotezy, którą równie dobrze mogę się podzielić.

Słyszałem, że hipoteza opierała się na pozytywnym rozwiązaniu trzynastego problemu Hilberta, który został wspólnie rozwiązany przez Komolgorowa i jego ucznia Arnolda. Twierdzenie (które jest znacznie bardziej ogólne niż stwierdzony problem Hilberta) mówi:

Każda ciągła funkcja skończonej liczby zmiennych może być wyrażona jako skończony skład funkcji jednej zmiennej, a także skończona liczba zastosowań operatora binarnego .$+$

Powiedziano mi, że w oparciu o niektóre szczegóły implementacji dowodu tego twierdzenia można to postrzegać jako ciągły analog twierdzenia, że .$\exists k \, \, \, P \subset SIZE(n^k)$

Przepraszam, że nie mam kwalifikacji, by być bardziej precyzyjnym - jeśli ktokolwiek słyszał o tym pomyśle, być może mógłby mi pomóc.