Hipoteza Kołmogorowa, że


28

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?


4
Stronicowanie @Stasys :)
Suresh Venkat


19
Ta „domysł” Kołmogorowa to tylko plotka. Oczywiście nie zostało to nigdzie opublikowane. W byłym ZSRR matematyka „publikowanie” oznaczała coś innego: przemówienie podczas seminarium lub mówienie kolegom podczas lunchu, albo coś innego. Liczenie papierów nie było problemem. Nie mogę więc wykluczyć, że ta „hipoteza” została właśnie przekazana Levinowi przez Kołmogorowa podczas ich spaceru na seminarium w MGU (Uniwersytet Moskiewski). (Właściwie to także zaleciłem ten sposób robienia matematyki.) Więc nie bierz tego zbyt poważnie - tylko jako „pogłoski”, która (nie trzeba dodawać) nie była obalana przez lata ...
Stasys,

5
Psize(nk)PNPkkN:Σ4Psize(nk)Σ2P

2
@Stasys, powinieneś opublikować to jako odpowiedź, aby pytanie uzyskało odpowiedź (aby strona nie wysadzała go na pierwszej stronie).
Kaveh

Odpowiedzi:


24

[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 partycjixf(x)=1f(x)=0f1(1)f1(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 ...fn2nfnfnccnc

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 kodowanieNC1zachowanie 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.


Czy są jakieś nietrywialne przykłady języków, które wspierają tę hipotezę?
Igor Shinkar

@Igor: Nie wiem. Niektóre (słabe) wskazania są tutaj wymienione . Właściwie skłaniam się do odpowiedzi GMB: najprawdopodobniej hipotezę stymulowało rozwiązanie 13. problemu Hilberta, a nie rozważania kombinatoryczne.
Stasys,

8

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 .kPSIZE(nk)

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.


czy możesz podać ref dla tego thm plz
vzn

@GMB: dobrze zaobserwowane - może to być jeszcze bliższe wytłumaczenie powodu, dla którego można podnieść to przypuszczenie.
Stasys
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.