Obwody dolne granice i złożoność Kołmogorowa

Rozważ następujące uzasadnienie:

Niech oznacza złożoność Kołmogorowa ciągu . Twierdzenie Chaitina o niekompletności tak mówi $K(x)$ $x$

dla jakiejkolwiek spójnej i wystarczająco silny system formalny , istnieje stała (zależnie tylko od formalnego systemu i jego języka) tak, że dla każdej struny , nie może udowodnić, że . $S$ $T$ $x$ $S$ $K(x) \geq T$

Niech będzie funkcją logiczną dla zmiennych, a złożoność Kołmogorowa jego widma wynosi co najwyżej . Niech będzie złożonością obwodu , tj . minimalnego obwodu obliczającego . $f_n$ $n$ $k$ $S(f_n)$ $f_n$ $f_n$

Górna granica dla to dla stałej a jest zajętą funkcją bobra (maksymalne możliwe kroki to zatrzymanie Maszyna Turinga z opisem wielkości może wykonać). (Dla każdego w spektrum skonstruuj minter odpowiadający prawdzie i weź OR wszystkich tych mintermów razem). $S(f_n)$

S (f_{n}) \leq c \cdot B B (k) \cdot n

$S(f_n)\leq c\cdot BB(k) \cdot n$

c

$c$

B B (k)

$BB(k)$

k

$k$

1

$1$

Załóżmy teraz, że dla nieskończonej rodziny funkcji boolowskich mamy formalny dowód, że wymaga obwodów o rozmiarach nieliniowych, tj. $L = \{f_n\}_{n}$ $L$

S ⊢ \forall n \geq n_{0}, g (n) \cdot n \leq S (f_{n})

$S \vdash \forall n \geq n_0, \ g(n)\cdot n \leq S(f_n)$ gdzie .

g (n) \in ω (1)

$g(n)\in \omega(1)$

Jeśli przyjmiemy, że jest wystarczająco duże, będziemy mieli $n$

g (n) > c \cdot B B (T)

$g(n) > c\cdot BB(T)$

W szczególności byłby to dowód, że złożoność Kołmogorowa widma wynosi co najmniej , co jest niemożliwe. $f_n$ $T$

To prowadzi do dwóch pytań:

1) W powyższym uzasadnieniu powinno być coś nie tak. Głównie dlatego, że sprawiłoby, że obwody superliniowe nie byłyby możliwe do udowodnienia.

2) Czy znasz podobne podejścia do pokazywania barier dla dolnych granic, to znaczy pokazując, że niektóre rodzaje (obwodowych) dolnych granic są formalnie nie do udowodnienia?

cc.complexity-theory reference-request lo.logic circuit-complexity kolmogorov-complexity Magnus Find
źródło

ciekawe pomysły. w pewnym stopniu związane z dowodami razborov / rudich odnoszącymi się do „naturalnych dowodów”, które szkicują bariery dla P =? NP (ale prawdopodobnie mają również zastosowanie do innych separacji klas złożoności wymienionych jako przykłady w artykule). Czy przeczytałeś ten artykuł? patrz także bariery P =? NP i bariery / złożoność obwodu monotonicznego . pozorne wskazówki świadczą o tym, że separacje klas złożoności są podobne w strukturze do dowodów niesprawdzalności.

vzn

czy możesz rozwinąć „spektrum” f_n? czy istnieje sposób sformułowania pytania bez odwoływania się do „widma”?

vzn

prawdopodobnie prawdą jest, że można badać złożoność funkcji, badając najmniejszą TM [w sensie tabeli stanów / stanów], która je oblicza i że będzie to mniej więcej odpowiadało dolnym granicom obwodu. jeśli potrafisz wykazać, że znalezienie tej najmniejszej bazy TM jest niemożliwe, a nie naprawdę trudne, możesz coś tam mieć. jednak „najprostsze” jest znalezienie najmniejszej bazy TM za pomocą kanonicznego wyliczenia obwodów lub baz TM. zastanawiając się, dlaczego to podejście działa, może pomóc zrozumieć, dlaczego pytanie nie prowadzi do problemu.

vzn

Dobrze. Dzięki za referencje. Wiem o papierze Natural Proofs. Nie wiem, czy pytanie można sformułować bez „widma”. Przez „widmo” rozumiem sekwencję

(f (0, 0, . ., 0), f (0, 0, . ., 1), . ., f (1, 1, . ., 1))

$(f(0,0,..,0),f(0,0,..,1),..,f(1,1,..,1))$

Magnus Znajdź

Odpowiedzi:

Nie ma nic złego w twojej argumentacji, ale nie ma sprzeczności. Udowodnić, że od jakiegoś wystarczająco duże złożoności Kołmogorowa widma jest zawsze przy najmniejszym . Ale to stwierdzenie jest banalnie prawdziwe! Chociaż nie możemy udowodnić, że złożoność Kołmogorowa jednego łańcucha jest duża, jeśli mamy sekwencję, to od pewnego momentu może zawierać tylko łańcuchy o dużej złożoności. Więc co to jest , które masz? Musi spełniać , czyli liczby, której nie możemy obliczyć (z powodu ), więc nie ma żadnego problemu. $N$ $f_n$ $T$ $N$ $N>g^{-1}(c \cdot BB(T))$ $BB$

domotorp
źródło

Dziękuję Ci. Wpadłem w pułapkę przekonania, że można „wybrać” pewną wartość N dostatecznie dużą, ale jak zauważysz, nie jest to możliwe w obrębie , a także, jak słusznie zauważysz, byłoby to prawdą w przypadku każdej rodziny rosnące sekwencje.

S

$S$

Magnus Znajdź

Oto jeszcze prostsza problematyczna sytuacja. Niech będzie pierwszym ciągiem (w porządku leksykograficznym) takim, że ; taki ciąg istnieje dla wszystkich . Następnie . $A(k)$ $K(A(k)) \geq k$ $k$ $K(A(k)) \geq k$

Winowajcą może być to, że system formalny nie może obliczyć . $BB(T)$

Edycja: Oto „bardziej wyraźna” problematyczna sytuacja. Niech będzie maksymalną długością łańcucha, którego złożoność Kołmogorowa wynosi co najwyżej ; istnieje możliwe do udowodnienia. Następnie . $\alpha(k)$ $k$ $\alpha(k)$ $K(0^{\alpha(k)+1}) > k$

Yuval Filmus
źródło

Dlaczego ta sytuacja jest problematyczna? Nie podałeś programu, którego wynikiem byłoby A (k), a jego długość byłaby mniejsza niż k.

domotorp

B B (k)

$BB(k)$

k

$k$

Jest to problematyczne (prawdopodobnie) w tym samym sensie, co pierwotne pytanie.

Yuval Filmus,

Nadal nie rozumiem. Nie pokazujesz łańcucha i dowodu, że jego złożoność Kołmogorowa jest duża. Pokazujesz dowód, że istnieje ciąg, którego złożoność jest duża.

Sasho Nikolov

Myślę, że są problematyczne na różne sposoby. Gdy czytam, wskazujesz na konkretne prawdziwe stwierdzenie, które nie ma dowodu. Przedstawiając to w moim pytaniu, wskazuję, że pociąga to za sobą dowód na coś, czego nie można udowodnić.

Magnus Znajdź