Folgen von #P = FP

Was wären die Konsequenzen von #P = FP?

Ich interessiere mich sowohl für praktische als auch für theoretische Konsequenzen.

Aus praktischer Sicht interessieren mich insbesondere die Konsequenzen für die künstliche Intelligenz.

Hinweise auf Papiere oder Bücher sind ausdrücklich erwünscht.

Bitte sagen Sie nicht, dass #P = FP P = NP impliziert, das weiß ich bereits. Sagen Sie bitte auch nicht "es wird keine praktischen Konsequenzen geben, wenn der Algorithmus in der Zeit läuft , wobei die Anzahl der Elektronen im Universum ist" $\Omega(n^{\alpha})$ $\alpha$ : Lassen Sie mich annehmen, wenn ein deterministischer polynomieller Zeitalgorithmus für Wenn ein # P-vollständiges Problem vorliegt, ist seine Laufzeit "clement" ( z. B. ). $O(n^2)$

cc.complexity-theory ds.algorithms complexity-classes counting-complexity ai.artificial-intel Giorgio Camerani
quelle

Antworten:

Hier sind einige theoretische Konsequenzen der Gleichheit FP = # P, obwohl sie nichts mit künstlicher Intelligenz zu tun haben. Die Annahme FP = # P ist äquivalent zu P = PP . Lassen Sie mich also die letztere Notation verwenden.

Wenn P = PP, dann haben wir P = BQP : Quantenpolynomzeitberechnung kann durch klassische, deterministische Polynomzeitberechnung simuliert werden. Dies ist eine direkte Folge von BQP⊆PP [ADH97, FR98] (und eines früheren Ergebnisses von BQP⊆P ^PP [BV97]). Nach meinem Wissen folgt P = BQP nicht aus der Annahme P = NP. Diese Situation unterscheidet sich vom Fall der randomisierten Berechnung ( BPP ): Da BPP⊆NP ^NP [Lau83] ist, folgt die Gleichheit P = BPP aus P = NP.

Eine weitere Konsequenz von P = PP ist, dass das Blum-Shub-Smale-Modell der Berechnung über den Real mit rationalen Konstanten in gewissem Sinne Turing-Maschinen gleichwertig ist. Genauer gesagt impliziert P = PP P = BP (P _ℝ⁰ ); das heißt, wenn eine Sprache L ⊆ {0,1} ^* durch ein konstantes freies Programm über die Realzahlen in Polynomzeit entscheidbar ist, dann ist L durch eine Polynomzeit-Turing-Maschine entscheidbar. (Hier steht „BP“ für „Boolescher Teil“ und hat nichts mit BPP zu tun.) Dies folgt aus BP (P _ℝ⁰ ) ⊆ CH [ABKM09]. Siehe das Papier für Definitionen. Ein wichtiges Problem in BP (P _ℝ⁰ ) ist das Quadratwurzelsummenproblemund Freunde (zB "Wenn man eine ganze Zahl k und eine endliche Menge von Ganzzahlkoordinatenpunkten auf der Ebene hat, gibt es einen Spannbaum mit einer Gesamtlänge von höchstens k ?") [Tiw92].

Ähnlich wie beim zweiten Argument ist das Problem von ein spezifisches Bit in der Berechnung x ^y als positiver ganzer Zahlen x und y sind in binären gegeben wird in P , wenn P = PP sein.

Verweise

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen und Peter Bro Miltersen. Zur Komplexität der numerischen Analyse. SIAM Journal on Computing , 38 (5): 1987–2006, Januar 2009. http://dx.doi.org/10.1137/070697926

[ADH97] Leonard M. Adleman, Jonathan DeMarrais und Ming-Deh A. Huang. Quantenrechenbarkeit. SIAM Journal on Computing , 26 (5): 1524–1540, Oktober 1997. http://dx.doi.org/10.1137/S0097539795293639

[BV97] Ethan Bernstein und Umesh Vazirani. Quantenkomplexitätstheorie. SIAM Journal on Computing , 26 (5): 1411–1473, Oktober 1997. http://dx.doi.org/10.1137/S0097539796300921

[FR98] Lance Fortnow und John Rogers. Komplexitätsbeschränkungen bei der Quantenberechnung. Journal of Computer and System Sciences , 59 (2): 240–252, Okt. 1999. http://dx.doi.org/10.1006/jcss.1999.1651

[Lau83] Clemens Lautemann. BPP und die Polynomzeithierarchie. Information Processing Letters , 17 (4): 215–217, November 1983. http://dx.doi.org/10.1016/0020-0190(83)90044-3

[Tiw92] Prasoon Tiwari. Ein Problem, das beim algebraischen RAM zu Stückkosten leichter zu lösen ist. Journal of Complexity , 8 (4): 393–397, Dez. 1992. http://dx.doi.org/10.1016/0885-064X(92)90003-T

Tsuyoshi Ito
quelle

Du hast mich geschlagen! Eigentlich hast du recht, was BQP vs NP angeht. Es scheint vernünftige Beweise dafür zu geben, dass BQP nicht in PH enthalten ist (siehe zum Beispiel arxiv.org/abs/0910.4698 ), obwohl ich der Meinung bin, dass die im zweiten Bit verwendete verallgemeinerte Linial-Nisan-Vermutung sich seitdem als falsch erwiesen hat.

Joe Fitzsimons

@turkistany: Wenn ich mich nicht irre, impliziert P = NP P = BPP, weil BPP in PH enthalten ist, und wenn P = NP, dann P = PH.

Niel de Beaudrap

Übrigens: +1 für (FP = # P) ⇔ (P = PP), auch wenn der Rest des Inhalts der Antwort weggelassen wird.

Niel de Beaudrap

@ Joe: Angesichts der Antworten auf die andere Frage denke ich, dass der beste Beweis für „P = NP bedeutet nicht P = BQP“, ohne tatsächlich zu beweisen, dass P = NP ≠ BQP wahrscheinlich ein Ergebnis der Orakeltrennung ist: „Es gibt etwas ein Orakel A, so dass P ^ A = NP ^ A ≠ BQP ^ A. ”Natürlich ist dies überhaupt nicht einfach, da dieses Ergebnis BQP ^ A⊈PH ^ A implizieren würde, was eine große offene Frage aufwirft.

Tsuyoshi Ito

@ Tsuyoshi: Kannst du ein solches Orakel nicht aus einem Orakel konstruieren, für das BQP nicht in PH enthalten ist, indem du es einfach mit PH zusammennimmst, um ein neues Orakel zu bilden?

Joe Fitzsimons

In grafischen Modellen sind viele der Schätzprobleme # P-vollständig, da sie Summenproduktberechnungen a la Permanent über allgemeine Diagramme umfassen. Wenn #P = FP, werden grafische Modelle plötzlich viel einfacher, und wir müssen uns nicht mehr mit Modellen mit niedriger Baumbreite herumschlagen.

Suresh Venkat
quelle

$PH \subseteq P^{\#P}$ $\sharp P=FP$ $PH$

Mohammad Al-Turkistany
quelle

Kann jemand klarstellen: Ist das nicht dasselbe wie "P = PH" (was sich unmittelbar aus P = NP ergeben würde)?

Niel de Beaudrap

@Niel: Es ist nicht dasselbe, es ist stärker.

Giorgio Camerani

P^{FP} = P

$\text P^{\text{FP}} = \text P$

# P = FP

$\#\text P = \text{FP}$

PH \subseteq P^{# P} = P^{FP} = P \subseteq PH

$\text{PH} \subseteq \text P^{\#\text P} = \text P^{\text{FP}} = \text P \subseteq \text{PH}$

@All: Nur um das zu verdeutlichen --- mein erster Kommentar oben lautete: "Entspricht die Antwort von turkistany der Aussage, dass FP = # P P = PH impliziert?" Wenn ich wissen wollte, ob FP = # P gleich P = PH ist, hätte ich dies in einem Kommentar zum ursprünglichen Beitrag gefragt, nicht in der Antwort von turkistany.

Niel de Beaudrap

@Niel: Du hast recht. Dies ist dasselbe wie P = PH, was sich aus P = NP ergibt. Daher war die Verwendung von Todas Theorem nicht notwendig, da FP = #P bereits P = NP = PH impliziert.

Robin Kothari