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

Gibt es , eine NP- oder P-vollständige Sprache mit einer Familie von Symmetriegruppen$L$$G_n$ (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 gegeben$L_n = \{ l \in L \mid |l| = n \}$$|L_n / G_n| < n^c$$n$$c$$G_n$ 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 = $\mathrm{FP}$$L$$\mathrm{PTIME}$$N$$\mathrm{P = NP}$$\mathrm{L = P}$Dies 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.$\mathrm{P/poly}$

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 P ⊆ c o A M / p o l o l y , so dass PH zu Z P $\mathsf{coAM}$$G_n$$\mathsf{NP} \subseteq \mathsf{coAM/poly} = \mathsf{coNP/poly}$ . Um zu vermeiden, dass PH zusammenbricht, müssten die Gruppen bei einer solchen Konstruktion für NPkeineneffizienten, nahezu gleichmäßigen Sampler haben.$\mathsf{ZPP}^{\mathsf{NP}}$

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