Konstruktywność w dowodzie naturalnym i złożoność geometryczna

Niedawno Ryan Willams udowodnił, że konstruktywność w naturalnym dowodzie jest nieunikniona, aby uzyskać separację klas złożoności: i . T C $\mathsf{NEXP}$$\mathsf{TC}^{0}$

Konstruktywność w naturalnym dowodzie jest warunkiem, że wszystkie dowody kombinatoryczne w złożoności obwodu są spełnione i że możemy zdecydować, czy funkcja docelowa w (lub innej „twardej” klasie złożoności) ma właściwość „twardą” przez działający algorytm w czasie wielokrotnym w tabeli prawdy funkcji celu.$\mathsf{NEXP}$

Pozostałe dwa warunki: warunek bezużyteczny, który wymaga właściwości „twardej”, nie może być obliczony przez żadne obwody w i warunek wielkości, że właściwość twarda jest łatwa do znalezienia.$\mathsf{TC}^0$

Moje pytanie brzmi :

Czy ten wynik powoduje, że teoria złożoności geometrycznej (GCT) jest niedostępna do rozwiązania głównych problemów związanych z separacją, takich jak vs , vs lub vs ?N P P N C N E X P T C$\mathsf{P}$$\mathsf{NP}$$\mathsf{P}$$\mathsf{NC}$$\mathsf{NEXP}$$\mathsf{TC}^0$

Referencje:

• Ryan Williams, „ Natural Proofs vs. Derandomization ”

Nie, nieunikniona konstruktywność zdecydowanie pozostawia otwartą GCT jako realny plan ataku na dolne problemy, takie jak vs. .P / p o l $NP$$P/poly$

Po pierwsze, warto wspomnieć, że wynik Ryana w zakresie konstruktywności jest bardzo podobny w smaku do tak zwanych „twierdzeń Flip” autorstwa Mulmuleya, które mówią, na przykład, że jeśli permanent nie ma obwodów arytmetycznych o wielkiej wielkości, to istnieje losowy konstruowalny zestaw (wielomianowo wielu) macierzy tak, że każdy mały obwód różni się od stałego na jednej z tych macierzy. Patrz: Explicit Proofs and The Flip, Technical Report, Departament Informatyki, University of Chicago, wrzesień 2010, autor: Mulmuley.$\{M_1, \dotsc, M_{p(n)}\}$

Po drugie, centralna charakterystyka symetrii (wspomniana już przez siuman) w GCT stała się bardziej widoczna od badania Regana. Jeśli charakterystyka symetrii okaże się tak istotna dla GCT, jak się wydaje, będzie to już miało miejsce, wówczas już to omija warunek wielkości. Definicja symetrii-characterzation znajduje się w tej odpowiedzi na ściśle powiązane poprzednie pytanie .

Aby dowieść, że charakterystyka symetrii narusza wielkość, zobacz rozdział 3.4.3 „Charakteryzacja symetrii unika bariery Razborowa – Rudicha” w mojej pracy magisterskiej (bezwstydne wtyczki, ale nie wiem nigdzie indziej, gdzie zapisano to tak całkowicie) . Podejrzewam, że to także narusza konstruktywność, ale pozostawiłem to jako otwarte pytanie. (Wcześniej w rozdziale 3 znajduje się również przegląd twierdzeń dotyczących przerzucania w GCT i ich związku z charakterystyką symetrii).

(Uważam za interesujące, że charakterystyka symetrii - ta własność, o której podejrzewamy, zostanie wykorzystana w GCT, która omija Razborowa - Rudicha) służy do udowodnienia twierdzeń typu flip, które zasadniczo mówią, że konstruktywność jest konieczna.)

Na koniec warto wspomnieć, że chociaż na dłuższą metę GCT dąży do rozwiązania kontra i innych problemów logicznych, w tej chwili większość prac w GCT koncentruje się na ich algebraicznych analogach, takich jak liczby zespolone, i tam nie jest jak dotąd algebraicznym analogiem Razborowa - Rudicha (o którym wiem).P / p o l $NP$$P/poly$

Pozwól mi najpierw poprawić możliwe nieporozumienie: niestety nie wiemy jeszcze, że . Moja ostatnia dolna granica to . N E X P ∩ c o N E X P ⊄ A C $NEXP \not\subset TC^0$$NEXP \cap coNEXP \not\subset ACC$

Odpowiedź na twoje pytanie brzmi: nie. Nadal jest bardzo możliwe, że techniki oparte na GCT mogą oddzielić od .N $P$$NP$

Jeszcze kilka komentarzy na ten temat: relacja między GCT a Natural Proofs była dyskutowana w przeszłości (nawet w samych oryginalnych dokumentach GCT). Chociaż wydaje się, że nie było konsensusu co do tego, która z „konstruktywności” lub „wielkości” zostałaby naruszona przez podejście GCT, Mulmuley i Sohoni argumentowali w pewnym momencie, że jeśli GCT można przeprowadzić, to powinien on naruszać wielkość. Odpowiednie informacje można znaleźć w części 6 przeglądu GCT firmy Regan . Powinienem jednak dodać, że ten przegląd ma już 10 lat i od tego czasu w GCT wykonano wiele pracy; Nie jestem pewien, czy są jakieś poprawione / nowe opinie na ten temat. (Być może Josh Grochow może wejść?)

Krótka odpowiedź brzmi: nie .

Podejście teorii złożoności geometrycznej jest ukierunkowane na pewne niezwykle rzadkie własności, które, jak twierdzi Mulmuley, nie są „duże”, jak zdefiniowali Razborov i Rudich. Aby uzyskać formalny argument, zobacz także tezę Jozuego Grochowa , Rozdział 3.4.3. Charakterystyka symetrii omija barierę Razborowa – Rudicha i jego odpowiedź .

Poniższy akapit pochodzi z On P vs. NP i Teorii Złożoności Geometrycznej Ketana Mulmuleya ( JACM 2011 lub manuskrypt ), Rozdział 4.3 Plan wysokiego poziomu :

Celem jest przeprowadzenie tych kroków w sposób jawny, wykorzystując charakterystykę przez symetrie trwałego i determinanta. Później określimy, co wyraźnie oznacza; por. Hipoteza 4.6. To podejście jest wyjątkowo sztywne w tym sensie, że działa tylko w przypadku bardzo rzadkich funkcji twardych, które charakteryzują się symetrycznością. Ta ekstremalna sztywność jest znacznie większa niż to, co jest potrzebne do ominięcia naturalnej bariery ochronnej [Razborov i Rudich 1997].

Ponieważ dla naturalnego dowodu wymagane są zarówno warunki konstruktywności, jak i rozległości (gdzie domniemana jest użyteczność), udowodnienie, że konstruktywność jest nieunikniona, nie wystarcza, aby wykluczyć takie podejście (choć jest to duży krok naprzód).