Nie, nieunikniona konstruktywność zdecydowanie pozostawia otwartą GCT jako realny plan ataku na dolne problemy, takie jak vs. .P / p o l yNPP/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.{M1,…,Mp(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 yNPP/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 CNEXP⊄TC0 NEXP∩coNEXP⊄ACC
Odpowiedź na twoje pytanie brzmi: nie. Nadal jest bardzo możliwe, że techniki oparte na GCT mogą oddzielić od .N PP 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ść?)
źródło
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 :
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).
źródło