Argumenty za / przeciw hipotezie Kołmogorowa o złożoności obwodu P.

Według (niezweryfikowanego) rachunku historycznego Kołmogorow uważał, że każdy język w ma złożoność obwodów liniowych. (Zobacz wcześniejsze pytanie Hipoteza Kołmogorowa, że ma obwody o rozmiarach liniowych .) Zauważ, że implikuje .$\mathsf{P}$$P$$\mathsf{P}\neq \mathsf{NP}$

Jednak przypuszczenie Kołmogorowa może się nie powieść. Na przykład Ryan Williams pisze w niedawnym artykule: „Przypuszczenie byłoby zaskakujące, jeśli jest prawdziwe. W przypadku języków w wymagających czasu wydaje się mało prawdopodobne, aby złożoność takich problemów magicznie skurczyłby się do rozmiaru tylko dlatego, że dla każdej długości wejściowej można zaprojektować inny obwód. ”$\mathsf{P}$$n^{100^{100}}$$O(n)$

Z drugiej strony Andrey Kołmogorow (1903–1987) jest powszechnie uznawany za jednego z czołowych matematyków XX wieku. Trudno sobie wyobrazić, że zaproponowałby całkowicie absurdalną hipotezę. Dlatego, aby lepiej to zrozumieć, próbowałem znaleźć argumenty, które mogłyby w rzeczywistości poprzeć jego zaskakujące przypuszczenia. Oto, co mogłem wymyślić:

Załóżmy, że . Następnie możemy wybrać język L \ w \ mathsf {P} , taki że L ma złożoność superliniową zarówno w modelu jednolitym, jak i niejednorodnym. Istnieją zatem dwie możliwości:$\mathsf{P}\not\subseteq \mathsf{SIZE}(lin)$$L\in \mathsf{P}$$L$

1. Znany jest wyraźnie algorytm (maszyna Turinga), która przyjmuje $L$ . Na tej podstawie możemy skonstruować wyraźną rodzinę funkcji, która musi mieć złożoność obwodów superliniowych. Może się to jednak wydawać mało prawdopodobne, ponieważ nikt nie był w stanie znaleźć takiego przykładu przez ponad 60 lat intensywnych badań nad obwodami.

2. Tam nie jest znana wyraźny algorytm $L$ . Na przykład jego istnienie zostało udowodnione za pomocą niekonstruktywnych środków, takich jak Axiom of Choice. Lub nawet jeśli istnieje wyraźny algorytm, nikt nie był w stanie go znaleźć. Biorąc jednak pod uwagę, że istnieje nieskończenie wiele języków, które mogą odgrywać rolę $L$ , jest mało prawdopodobne, aby wszystkie zachowywały się w ten nieprzyjazny sposób.

Ale jeśli odrzucimy obie opcje jako mało prawdopodobne, jedyną pozostałą możliwością jest to, że taki $L$ nie istnieje. Oznacza to $\mathsf{P}\subseteq \mathsf{SIZE}(lin)$ , co jest dokładnie hipotezą Kołmogorowa.

Pytanie: Czy możesz wymyślić jakiś dodatkowy argument za / przeciw hipotezie Kołmogorowa?

Przytoczony przeze mnie przypis odnosi się do heurystycznego „argumentu”, a przynajmniej do tego, co naszym zdaniem było intuicją Kołmogorowa - pozytywnym rozwiązaniem trzynastego problemu Hilberta.

http://en.wikipedia.org/wiki/Hilbert's_thirteenth_problem

W szczególności Kolmogorov i Arnold udowodnili, że dowolną funkcję ciągłą na zmiennych można wyrazić jako kompozycję „prostych” funkcji : dodanie dwóch zmiennych i funkcji ciągłych na jednej zmiennej. Stąd, na podstawie „podstawy funkcji ciągłych jednej zmiennej i dodawania dwóch zmiennych, każda funkcja ciągła na zmiennych ma„ złożoność obwodu ” .O ( n 2 ) n O ( n 2$n$$O(n^2)$$n$$O(n^2)$

Wydaje się, że Kołmogorow uważał, że istnieje dyskretny analog, w którym „ciągły w zmiennych ” staje się „logiczny w zmiennych i obliczalny w czasie ”, a „podstawa” podana powyżej staje się dwiema zmiennymi funkcjami logicznymi.n ( n $n$$n$$(n)$

Odpowiedź Stasysa na poprzednie pytanie zawiera pewną intuicję potencjalnie na korzyść: /cstheory//a/22048/8243 . Spróbuję odtworzyć tutaj, jak rozumiem. Kluczową intuicją jest postrzeganie obwodu jako nie algorytmu, ale kodowania zestawu (zestawu, który akceptuje). Możemy dostać górny związany na algorytmie kodowania rozmiaru przez czas pracy (czyli tłumaczyć czasowemu TM w size- obwodu), ale nie jest jasne, co powinno istnieć zależność odwrotna. Jeśli język znajduje się w , być może oznacza to, że członkostwo jest na tyle „lokalne”, że można je zakodować bardzo zwięźle.t $t$$t$$\mathsf{P}$

Oznacza to, że członkostwo w jest stwierdzeniem o czasie działania algorytmu, podczas gdy obwody liniowe są (być może) stwierdzeniem o kodowaniu rozmiaru zestawów słów o stałej długości. Oba są stwierdzeniami o prostocie języka, ale żyją w być może zupełnie innych światach.$\mathsf{P}$

Inna intuicja, o której wspomina Stasys, pochodzi z „łańcucha wskaźnika” języka, który sformalizujemy jako ciąg nieskończony, w którym bit wynosi jeśli ty łańcuch leksykograficzny jest w języku, a w przeciwnym razie . (Polytime) TM dla języka to (szybka) wyrocznia dla łańcucha --- biorąc pod uwagę w formacie binarnym, należy wygenerować ty bit. Obwód (liniowy) dla wejść o długości jest (zwięzłą) wyrocznią dla prefiksu długości łańcucha. Przypuszczenie staje się „dowolnym nieskończonym ciągiem, który ma„ szybką ”wyrocznię z„ zwięzłą ”przedrostkiem-wyrocznią”.1 j 0 j j n 2 $j$$1$$j$$0$$j$$j$$n$$2^n$

Żadne z powyższych nie wyjaśnia, dlaczego i„ liniowy ”mogą być odpowiednimi odpowiednimi parametrami instrukcji, ale myślę, że pokazują one jedną naturalną intuicję - że obwody działają jak algorytmy, a bardziej skomplikowane algorytmy wymagają podobnie skomplikowane obwody - mogą wprowadzać w błąd.$``\mathsf{P}"$