Czy implikuje ?

O ile rozumiem, program teorii geometrycznej złożoności próbuje oddzielić , udowadniając, że permament macierzy o złożonej wartości jest znacznie trudniejszy do obliczenia niż wyznacznik.$VP \neq VNP$

Pytanie, które zadałem po przejrzeniu dokumentów GCT: Czy to natychmiast oznaczałoby , czy jest to tylko duży krok w kierunku tego celu?$P \neq NP$

Krótka odpowiedź brzmi „nie”. Żadna taka implikacja nie jest znana. Istnieją dwie główne przeszkody: przejście od złożoności obwodu arytmetycznego do złożoności logicznej (VP ≠ VNP oznacza P / poli ≠ NP / poli), a następnie przejście od złożoności obwodu logicznego (P / poli ≠ NP / poli) do jednolitej złożoności (P ≠ NP ). Żaden z tych kroków nie jest znany. Uważam jednak, że P / poly ≠ NP / poly implikuje VP ≠ VNP.

Zakładając uogólnioną hipotezę Riemanna (GRH), znane są następujące dość silne powiązania między a upadkiem hierarchii wielomianowej ( ):$VP= VNP$${\rm PH}$

1. Jeśli (nad dowolnym polem), wówczas hierarchia wielomianowa zapada się na drugi poziom;$VP= VNP\,$
2. Jeśli w polu charakterystyki , to ;$VP=VNP\,$$0$$\rm{NC}^3/{\rm poly}={\rm P}/{\rm poly} = {\rm PH}/{\rm poly}$
3. Jeśli w polu skończonej charakterystyki , to .$VP=VNP\,$$p$$\rm{NC}^2/{\rm poly}={\rm P}/{\rm poly} = {\rm PH}/{\rm poly}$

Oto wyniki: Peter Burgisser, „Hipoteza Cooka a Valianta ”, Teoria. Komp. Sci., 235: 71–88, 2000.

Zobacz także: Burgisser, „ Kompletność i redukcja w teorii złożoności algebraicznej ”, 1998.

Mogę podać nieformalny powód, dla którego separacja nie udowodni .$P \ne NP$

VP i VNP koncentrują się na funkcjach algebraicznych, których stopień jest ograniczony przez wielomian. Zauważ, że łatwo jest obliczyć w funkcji algebraicznej stopnia wykładniczego za pomocą obwodu algebraicznego o wielkości wielomianowej.

Istnieje dobrze znana redukcja 1 głębokości dla obwodów algebraicznych: dowolny obwód algebraiczny o wielkości wielomianowej obliczający wielomian stopnia może zostać przekształcony w obwód algebraiczny o wielkości wielomianu i głębokości .$d$$O(\log d \log n)$

Można myśleć o jako algebraiczną wariantu , a tym samym udowadniając, że wynosi udowodnić algebraiczny niejednorodnej równowartość . To nie wykluczałoby , przynajmniej nie natychmiast.$VP$$NC^2$$VP \ne VNP$$NC^2 \ne \# P$$P = NP$

Oświadczenie : Nie mogę teraz uzyskać dostępu do papieru i nie pamiętam, czy redukcja działa na jakimkolwiek polu, czy tylko na skończonych.

1 LG Valiant, S. Skyum, S. Berkowitz, C. Rackoff. Szybkie równoległe obliczanie wielomianów przy użyciu kilku procesorów . SIAM J. Comput. 12 (4), s. 641–644, 1983.