Gibt es hochsymmetrische NP- oder P-vollständige Sprachen?

14

Gibt es , eine NP- oder P-vollständige Sprache mit einer Familie von SymmetriegruppenLGn (oder Gruppoid , aber dann die algorithmischen Fragen offener worden) wirken (in Polynomialzeit) auf Mengen so, dass es nur wenige Umlaufbahnen gibt, dh so, dass | L n / G n | < n c für groß genug n und einige c , und so dass G n erzeugt werden kann gegebenLn={lL|l|=n}|Ln/Gn|<ncncGn effizient?n

Der Punkt hier ist, dass wenn man eine Sprache / Gruppe wie diese findet und wenn man normale Formen unter polynomiellen Zeitgruppenaktionen in findet, man L um eine P T I M E Reduktion auf eine spärliche Sprache um reduzieren kann Berechnen der Normalform für jedes gegebene N , was impliziert, dass P = N P oder L = P istFPLPTIMENP=NPL=PDies hängt davon ab, ob Sie zu Beginn eine NP- oder eine P-vollständige Sprache gewählt haben. Es scheint also, dass es entweder keine solchen Gruppen mit spärlichen Umlaufbahnen gibt oder dass es für alle diese Gruppen schwierig ist, normale Formen zu berechnen, oder eines dieser Ergebnisse wird zutreffen, was meines Erachtens die meisten von uns nicht glauben. Es wäre auch scheinen , dass , wenn man die Äquivalenzbeziehung über die Bahnen anstelle der normalen Formen berechnen kann, eine noch diese nicht einheitlich tun konnte, in . Ich hoffe, dass andere Leute darüber nachdenken.P/poly

Samuel Schlesinger
quelle
4
Was meinst du mit einer " -vollständigen Sprache"? {NP,P}
Emil Jeřábek unterstützt Monica am
Ich meine eine oder N P vollständige Sprache. PNP
Samuel Schlesinger
1
Warum denkst du, würde die Existenz einer Polyzeitverkürzung P auf L reduzieren?
Emil Jeřábek unterstützt Monica am
Ich hätte unter log Reductions gedacht, aber bei der normalen Formberechnung wäre das mit ziemlicher Sicherheit in P, das ist wirklich nur für NP relevant. Danke, dass du das erwähnt hast.
Samuel Schlesinger

Antworten:

12

Für NP scheint dies schwer zu konstruieren. Insbesondere, wenn Sie auch (nahezu) einheitliche Elemente aus Ihrer Gruppe abtasten können - was für viele natürliche Arten der Gruppenkonstruktion gilt -, dann kollabiert PH, wenn eine NP-vollständige Sprache eine Polyzeitgruppenaktion mit wenigen Umlaufbahnen aufweist. Mit dieser zusätzlichen Annahme über die Abtastbarkeit funktioniert das Standard- -Protokoll für den Graphisomorphismus auch zum Testen, ob zwei Strings im selben G n -orbit sind. Wir hätten dann N Pc o A M / p o l o l y , so dass PH zu Z P P zusammenbrichtcoAMGnNPcoAM/poly=coNP/poly . Um zu vermeiden, dass PH zusammenbricht, müssten die Gruppen bei einer solchen Konstruktion für NPkeineneffizienten, nahezu gleichmäßigen Sampler haben.ZPPNP

Joshua Grochow
quelle
Nett! Dies ist genau das, was ich erwartet hatte, nachdem ich eine andere Antwort von Ihnen über das Problem mit dem Vertreter der Umlaufbahn gelesen hatte.
Samuel Schlesinger
5

Meine Intuition ist, dass eine NP-vollständige Sprache dieses Typs einen Kollaps der Polynom-Hierarchie verursachen würde, ähnlich wie im Karp-Lipton-Theorem.

Genauer gesagt, wenn Sie auf die zweite Ebene der Polynom-Hierarchie aufsteigen, können Sie mithilfe der Potenz der Hierarchie die Äquivalenz zwischen einem bestimmten Gruppenelement und einem Vertreter einer Äquivalenzklasse erraten. Dann kehren Sie zum Karp zurück - Lipton-Fall, in dem die Tatsache, dass Sie polynomiell viele ungleiche Eingaben haben, Sie in P / poly versetzt.

(Das Ergebnis sollte mit der Antwort von Joshua Grochow übereinstimmen, jedoch ohne die zusätzliche Annahme der Abtastbarkeit.)

David Eppstein
quelle
Es kommt aber auf die Größe der Gruppe an, oder? Ich habe nicht einmal gesagt, dass die Gruppe endlich ist, nur dass sie effizient auf die Sprache einwirkt und effizient generiert werden kann. Davon abgesehen habe ich den Eindruck, dass Sie SAT in BPP lösen können, wenn die Gruppe effizient abgetastet werden kann (wie in Joshuas Antwort) und dies impliziert, was Sie vorschlagen. Das ist nicht positiv, aber ich habe einen Ansatz verfolgt, der die Selbstreduzierbarkeit von SAT nutzt und diesen Baum von Reduktionen zufällig beschneidet. Soweit ich das beurteilen kann, müssen die Umlaufbahnen jedoch eine ähnliche Größe haben.
Samuel Schlesinger
1
Wie kann man in Polynomialzeit handeln, wenn man mehr als Polynomialzeit benötigt, um ein Gruppenelement aufzuschreiben?
David Eppstein
Viele unendliche Gruppen haben endliche Präsentationen, nicht wahr? Dies sind nicht unbedingt Permutationsgruppen, sie haben nur einen Homomorphismus zu einer Symmetriegruppe unserer Sprache.
Samuel Schlesinger
Abgesehen davon denke ich, dass eine effiziente Abtastbarkeit Sie sowieso auf exponentiell große Gruppen beschränken sollte
Samuel Schlesinger
1
Σ2P