gegen

14

In unserer jüngsten Arbeit, lösen wir ein Rechenproblem , das in der kombinatorischen Kontext entstanden ist , unter der Annahme , dass , woEXPEXP ist die E X P -Version vonEXPEXP . Das einzige Papier aufP , das wir fanden, war dasPapier vonBeigel-Buhrman-Fortnow von1998, das imComplexity Zoozitiert wird. Wir verstehendass wir Parität Versionen nehmen N E X P -komplette Probleme (siehediese Frage), aber vielleicht viele von ihnen sind inTat nicht vollständig inEXPNEXP . EXP

FRAGE: Gibt es Gründe , Komplexität zu glauben , dass ? Gibt es natürliche kombinatorische Probleme, die in abgeschlossen sind ?EXPEXP ? Gibt es Referenzen, die uns fehlen könnten? EXP

Igor Pak
quelle
6
Ich denke, dass Paritätsversionen von mindestens einigen NEXP-vollständigen Problemen aus demselben Grund ⊕𝖤𝖷𝖯-vollständig wären, z. B. SUCCINCT 3SAT. Paritätsklassen sind syntaktisch wie existenzieller Nichtdeterminismus, daher haben Sie die gleichen Standardmethoden, um vollständige Probleme zu lösen.
Greg Kuperberg,
Danke, Greg. Ich verstehe. Es werden jedoch nicht alle Probleme funktionieren, z. B. ist die Parität der Anzahl der dreifarbigen SUCCINCT-Diagramme einfach.
Igor Pak
2
Das Problem in Ihrem Beispiel der Parität der Anzahl der 3-Farbtöne (die natürlich durch 6 teilbar ist) ist orthogonal zu der angegebenen Frage der EXP-Komplexitätsklassen. Die Frage ist, ob es eine sparsame Reduzierung gibt, dh eine Reduzierung, die die Anzahl der Zeugen bewahrt. Das ist oft bekannt, aber manchmal nicht. Zum Beispiel gibt es bei 3-Farben ein wunderschönes Papier von Barbanchon (das ich kürzlich aus meinen eigenen Gründen gesehen habe), das bis auf den Faktor 6 eine sparsame Reduktion gegenüber dem SAT darstellt.
Greg Kuperberg
2
Ah richtig. Interessant. Gefunden: Régis Barbanchon, Auf einzigartiger Grafik 3-Färbbarkeit und sparsame Verkleinerungen im Flugzeug (2004).
Igor Pak
3
@ GregKuperberg: Scheint wie eine Antwort! Man beachte , dass Valiant zeigte ( people.seas.harvard.edu/~valiant/focs06.pdf ) , die sogar ist P -komplette. 2SATP
Joshua Grochow

Antworten:

13

In Bezug auf die Komplexitätsgründen ( und nicht vollständige Probleme): Die Hartmanis-Immerman-Sewelson Satz sollte auch die Arbeit in diesem Zusammenhang, nämlich: iff gibt es eine polynomial spärlichen Satz in PP . Wenn man bedenkt, wie weit wir P und P auseinander halten - Toda hat beispielsweise gezeigt, dass P HB P P P -, wäre es ziemlich überraschend, wenn es in ihrem Unterschied keine spärlichen Mengen gäbe.EXPEXPPPPPPHBPPP

Wenn es keine sparse Sätze in ihren Unterschied wäre, wäre es , dass mehr direkt, sagen wir für jeden Verifizierer, wenn die Anzahl der Zeichenketten der Länge n mit einer ungeraden Anzahl von Zeugen begrenzt ist durch n O ( 1 ) , dann ist das Problem [ zu sagen, ob es eine ungerade Anzahl von Zeugen gibt] muss in P sein . Dies scheint eine bemerkenswerte und unwahrscheinliche Tatsache zu sein.NPnnO(1)P

Joshua Grochow
quelle
Ich verstehe den letzten Teil nicht. Jedes NP-Problem kann so ausgedrückt werden, dass die Anzahl der Zeugen immer gerade ist und 0 sicher polynomiell begrenzt ist. Sie sagen also effektiv, dass P = NP, und ich verstehe nicht, wie das folgt.
Emil Jeřábek unterstützt Monica
1
@Emil, der "Prüfer" in Klammern scheint zu verdeutlichen, was Josh meinte.
Kaveh
@ EmilJeřábek: In der Tat, Kaveh hat es genau verstanden. Wie Sie hervorheben, funktioniert die Aussage nur dann wirklich, wenn Sie über jeden NP-Verifizierer und nicht über jedes NP-Problem sprechen. Ich habe die Antwort so bearbeitet, dass dies kein Kommentar in Klammern mehr ist.
Joshua Grochow
Sorry, aber das hat nichts geklärt. Wenn die Aussage für alle Prüfer gilt, gilt sie insbesondere für Prüfer, die immer eine gerade Anzahl von Zeugen haben.
Emil Jeřábek unterstützt Monica
1
@ EmilJeřábek: Ah ja, ich sehe jetzt deine Verwirrung (denke ich). Geklärt. Das Ergebnis scheint mir ein wenig weniger auffällig zu sein, aber nicht viel (besonders das Licht von Todas Ergebnis).
Joshua Grochow