Czy implikuje ?

37

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.VPVNP

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?PNP

Benno
źródło
3
AFAIK, zoo podaje wszystkie znane informacje. qwiki.stanford.edu/wiki/Complexity_Zoo:V#vnp
Michaël Cadilhac
Monografia „Kompletność i redukcja w teorii złożoności algebraicznej” autorstwa Petera Bürgissera (math-www.uni-paderborn.de/agpb/work/habil.ps) może dać ci lepszy pogląd na to pytanie.
MCH
Właśnie aktualizuję adres URL Michaëla: complexityzoo.uwaterloo.ca/Complexity_Zoo:V#vnp
András Salamon

Odpowiedzi:

27

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.

Moritz
źródło
4
Twoje ostatnie zdanie jest prawdziwe: jeśli istnieje pole, w którym VP = VNP, to P / poly = NP / poly (kliknij link w komentarzu Cadilhaca).
Diego de Estrada
22

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

  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=VNP0NC3/poly=P/poly=PH/poly
  3. Jeśli w polu skończonej charakterystyki , to .VP=VNPpNC2/poly=P/poly=PH/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.

Iddo Tzameret
źródło
1
Myślę, że miałeś na myśli, że oznacza załamanie się wielomianowej hierarchii, nie że implikuje to. VP=VNPVPVNP
Robin Kothari,
15

Mogę podać nieformalny powód, dla którego separacja nie udowodni .PNP

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 .dO(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.VPNC2VPVNPNC2#PP=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.

MassimoLauria
źródło
2
czy jest to algebraiczny nierównomierny odpowiednik czy ? NC2NPNC2#P
Joshua Grochow
@JoshuaGrochow: masz rację, a ja to naprawiłem. Choć jest uważany za moralny odpowiednik , jest w rzeczywistości bardziej zbliżony do ducha . W rzeczywistości udział rozwiązuje problemy. VNPNP#P
MassimoLauria,
2
Valiant i in. wynik działa dla dowolnego pola.
Iddo Tzameret,