Zakres barier naturalnych dowodów

Naturalna bariera dowodowa Razborova i Rudicha mówi, że przy wiarygodnych założeniach kryptograficznych nie można mieć nadziei na oddzielenie NP od P / poli poprzez znalezienie kombinatorycznych właściwości funkcji, które są konstruktywne, duże i użyteczne. Istnieje kilka dobrze znanych wyników, które potrafią ominąć barierę. Istnieje również kilka artykułów omawiających możliwe luki w tych trzech warunkach, takich jak Chow pokazujący, że bariera jest wrażliwa na słabe naruszenia wielkości, oraz niedawny artykuł Chapmana i Williamsasugerując, jak potencjalnie ominąć barierę, rozluźniając warunek przydatności. Moje pytanie brzmi, czy istnieją jakieś przykłady, a nawet możliwość uniknięcia bariery naturalnych dowodów, nie poprzez naruszanie konstruktywności, wielkości lub użyteczności, ale przez wykraczanie poza jej zakres. Oznacza to, że wcale nie jest dla mnie oczywiste, dlaczego każda potencjalna metoda dowodu powinna opierać się na znalezieniu kombinatorycznych „właściwości”, a następnie podzieleniu wszystkich funkcji na te, które spełniają i nie spełniają tej właściwości. Dlaczego te ramy działania muszą mieć zastosowanie do wszystkich możliwych dowodów, a jeśli nie, to jak wyglądałyby inne rodzaje dowodów?

Niech będzie funkcją, a niech będzie klasą algorytmów działających na skończonych plasterkach . Każdy obwód dolnej granicy, co jest dowodem, że jakiegoś i niektóre . Rozważ „kombinatoryczną właściwość funkcji boolowskich” , taką jak$f: \{0,1\}^* \rightarrow \{0,1\}$$C$$f$$f \notin C$$f$$C$${\cal P}_f$

${\cal P}_f(f) = 1$ i dla wszystkich .${\cal P}_f(g) = 0$$g \neq f$

Dowód, że jest dowodem na to, że jest przydatny przeciwko , w terminologii Razborova i Rudicha. Oznacza to, że „użyteczność” jest całkowicie nieunikniona - nie ma sposobu, aby „wyjść poza jej zakres”. Jeśli w ogóle udowodniłeś dolną granicę obwodu, podałeś użyteczną właściwość.$f \notin C$${\cal P}_f$$C$

Zauważ, że jeśli , to jest również konstruktywny, jeśli chodzi o terminologię Razborowa i Rudicha. Tak więc dla funkcji obliczalnych w obrębie ale nie w (powiedzmy) , konstruktywność miałaby również zastosowanie do co najmniej jednej właściwości funkcji boolowskich, która jest przydatna przeciwko .P f f E P / p o l y P / p o l $f \in TIME[2^{O(n)}]$${\cal P}_f$$f$$E$$P/poly$$P/poly$

Razborov i Rudich są bardziej fundamentalni, niż początkowo moglibyście sądzić.

Masz rację: twierdzenie o naturalnych dowodach dotyczy właściwości naturalnych (i tylko nieformalnie o dowodach). Sam Razborow napisał dwa artykuły w tym samym czasie, analizując klasę dowodów formalnych i złożoność dolnych granic:

• Ograniczona arytmetyka i dolne granice w złożoności boolowskiej , 1995
• Niedopuszczalność dolnych granic wielkości obwodu w niektórych fragmentach ograniczonej arytmetyki , 1995

W pierwszym badaniu sformalizowano istniejące dowody dolnej granicy w słabych fragmentach arytmetyki (górne granice twardości udowodnienia teorii złożoności dolnych granic).

Drugi artykuł dotyczy dolnej granicy twardości dowodzenia silniejszej teorii złożoności dolnej granicy: ile matematyki potrzebujemy, aby udowodnić ? $\mathsf{P} \neq \mathsf{NP}$Czy potrzebujemy ? ? ? Może przynajmniej ? ( jest uważane za teorię odpowiadającą rozumowaniu przy użyciu pojęć w ). Idealny wynik dla drugiego artykułu byłby:ZFPAPVPV$ZFC$$ZF$$PA$$PV$$PV$$\mathsf{P}$

P ≠ N $PV$ nie może udowodnić (rozsądnej formalizacji) .$\mathsf{P} \neq \mathsf{NP}$

Aby to zrobić, musielibyśmy sformalizować nieformalny pomysł, że możemy wyodrębnić naturalne właściwości z dowodów z dolnej granicy w . Jednak wyniki w drugim artykule są znacznie słabsze niż to.$PV$

Tak więc, zgodnie z naszą najlepszą wiedzą, ma dowód, że nie używa żadnej koncepcji poza . W rzeczywistości, według naszej najlepszej wiedzy, o wiele słabsze teorie mogą świadczyć o rozdzieleniu.$\mathsf{P} \neq \mathsf{NP}$$\mathsf{P}$