Ist

Soweit ich weiß, versucht das Programm der geometrischen Komplexitätstheorie, zu trennen, indem es beweist, dass das Permament einer komplexwertigen Matrix viel schwerer zu berechnen ist als die Determinante.$VP \neq VNP$

Die Frage , die ich hatte , nachdem sie durch das GCT Paper Skimming: Würde dies sofort bedeuten , oder ist es nur ein wichtiger Schritt in diese Richtung?$P \neq NP$

Die kurze Antwort lautet "nein". Eine solche Implikation ist nicht bekannt. Es gibt zwei Haupthindernisse: Übergang von der Komplexität der arithmetischen Schaltung zur booleschen Komplexität (VP ≠ VNP impliziert P / poly ≠ NP / poly) und Übergang von der Komplexität der booleschen Schaltung (P / poly ≠ NP / poly) zur gleichmäßigen Komplexität (P ≠ NP ). Keiner dieser Schritte ist bekannt. Ich glaube jedoch, dass P / poly ≠ NP / poly VP ≠ VNP impliziert.

Unter der Annahme der verallgemeinerten Riemann-Hypothese (GRH) sind die folgenden ziemlich starken Zusammenhänge zwischen und dem Zusammenbruch der Polynomhierarchie ( P H ) bekannt:$VP= VNP$${\rm PH}$

1. Wenn $VP= VNP\,$ (über ein beliebiges Feld) dann kollabiert die Polynomhierarchie auf die zweite Ebene;
2. Wenn $VP=VNP\,$über ein Feld der Charakteristik , dann N C 3 / p o l y = P / P o l y = P H / p o l y ;$0$$\rm{NC}^3/{\rm poly}={\rm P}/{\rm poly} = {\rm PH}/{\rm poly}$
3. Wenn $VP=VNP\,$über ein Feld mit endlicher Charakteristik , dann ist N C 2 / p o l y = P / p o l y = P H / p o l y .$p$$\rm{NC}^2/{\rm poly}={\rm P}/{\rm poly} = {\rm PH}/{\rm poly}$

Dies sind Ergebnisse aus: Peter Burgisser, " Cook's versus Valiant's Hypothese ", Theor. Comp. Sci., 235: 71–88, 2000.

Siehe auch: Burgisser, " Vollständigkeit und Reduktion der algebraischen Komplexitätstheorie ", 1998.

Ich kann Ihnen einen informellen Grund geben , warum die Trennung nicht beweisen .$P \ne NP$

VP und VNP konzentrieren sich auf algebraische Funktionen, deren Grad durch ein Polynom begrenzt ist. Beachten Sie, dass es einfach ist, eine algebraische Funktion exponentiellen Grades mit einer algebraischen Schaltung polynomialer Größe zu berechnen.

Es ist eine wohlbekannte 1 Tiefenreduktion für algebraische Schaltungen: eine beliebige Größe algebraischen Polynoms Schaltung ein Polynom vom Grad Rechen kann in eine algebraische Schaltung von Polynom Größe und Tiefe gedreht werden O ( log d log n ) .$d$$O(\log d \log n)$

Sie können sich als eine algebraische Variante von N C 2 vorstellen und somit beweisen, dass V P ≠ V N P ein algebraisches ungleichmäßiges Äquivalent von N C 2 ≠ # P ist . Das würde P = N P nicht ausschließen, zumindest nicht sofort.$VP$$NC^2$$VP \ne VNP$$NC^2 \ne \# P$$P = NP$

Haftungsausschluss : Ich kann momentan nicht auf das Papier zugreifen und kann mich nicht erinnern, ob die Reduzierung in irgendeinem Bereich oder nur in endlichen Bereichen funktioniert.

1 LG Valiant, S. Skyum, S. Berkowitz, C. Rackoff. Schnelle parallele Berechnung von Polynomen mit wenigen Prozessoren . SIAM J. Comput. 12 (4), S. 641-644, 1983.