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 , taki że 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$

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

cc.complexity-theory circuit-complexity ho.history-overview

— Andras Farago
źródło

Zastanawiam się: czy mamy kandydatów do obalenia przypuszczeń Kołmogorowa? Oczywiście można wziąć pod uwagę każdy problem, który może mieć ponadliniową złożoność. Może niektóre z nich prawdopodobnie nie mają obwodów o rozmiarach liniowych?

— Bruno

spójrzmy prawdzie w oczy, nikt nie ma najmniejszego pojęcia. (re goldman cytuje w Hollywood: „nikt nic nie wie”). hipoteza (niepublikowana) może być otwarta nawet dłużej niż P =? NP. jednak warto przyjrzeć się przybliżonemu pomysłowi / kątowi: teorię kompresji i ściśliwość. jest to w gruncie rzeczy aluzja do Williamsa i może być w centrum wielu separacji klas złożoności. Chodzi o to, że istnieją podstawowe sposoby / algorytmy do kodowania danych, a niektóre wzorce są z natury trudniejsze do kompresji przy użyciu (dowolnych) kodowań. ale wydaje się, że wyniki w tym obszarze są bardzo nieliczne.

— vzn

a przy okazji, wiele powiązań złożoności Kołmogorowa ze złożonością obliczeniową, np. zbadanych przez Fortnow, może mieć pewne wyjaśnienie, dlaczego pytania są tak trudne do rozwiązania, ponieważ tak wiele pytań związanych ze złożonością Kołmogorowa jest nierozstrzygalne ...?

— vzn

@Bruno: Domyślam się, że -kompletne problemy byłyby dobrymi kandydatami, np. Programowanie liniowe lub problem z wartością obwodu. Jeśli problemów tych nie da się rozwiązać nawet nierównomiernie w wielorakiej wielkości i głębokości logarytmicznej, więc przynajmniej wydaje się rozsądne zgadywać, że takie problemy nie powinny być możliwe do rozwiązania w rozmiarze liniowym (i nieograniczonej głębokości). Determinant może być kolejnym rozsądnym kandydatem. Ale to tylko propozycje - nie mam silnych powodów, by sądzić, że mają obwód o obwodzie superliniowym.

P

$\mathsf{P}$

P ⊈ N C

$\mathsf{P} \not\subseteq \mathsf{NC}$

— Joshua Grochow

Odpowiedzi:

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 ” . $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)$

— Ryan Williams
źródło

Byłoby bardzo interesujące, gdyby istniał dyskretny analog, w który wierzył Kołmogorow. Przypuszczalnie badacze próbowali go znaleźć, ponieważ może to doprowadzić do dowodu . Jaką główną przeszkodę napotkali?

P \neq N P

$P\neq NP$

— Andras Farago

Blokady dróg? Nie sądzę, żeby ktokolwiek znalazł drogę :) Ponieważ większość ludzi uważa, że nie ma obwodów o rozmiarze , dla każdego ustalonego prawdopodobnie kilka osób nawet szukało drogi.

P

$P$

O (n^{k})

$O(n^k)$

k

$k$

— Ryan Williams

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$ $\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ą”. $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}"$

— usul
źródło