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.
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?
Odpowiedzi:
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.
źródło
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 PH
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.
źródło
Mogę podać nieformalny powód, dla którego separacja nie udowodni .P≠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(logdlogn)
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 NC2 VP≠VNP NC2≠#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.
źródło