Czy istnieją wysoce symetryczne języki NP lub P-complete?

Czy istnieje , język NP lub P-zupełny, który ma pewną rodzinę grup symetrii G n (lub groupoid , ale wtedy pytania algorytmiczne stają się bardziej otwarte) działając (w czasie wielomianowym) na zbiorach L n = { l ∈ L ∣ | l | = n } tak, że jest kilka orbit, tj. taki, że | L n / G n | < n c dla wystarczająco dużego n i trochę c , i takie, że G $L$$G_n$$L_n = \{ l \in L \mid |l| = n \}$$|L_n / G_n| < n^c$$n$$c$$G_n$mogą być generowane podano efektywnie?$n$

Chodzi o to, że jeśli znajdzie się taki język / grupę, a jeśli można znaleźć normalne formy pod wielomianowymi działaniami grup czasowych w , wówczas można zredukować L o P T I M E redukując do rzadkiego języka o obliczanie postaci normalnej dla dowolnego N , co oznacza, że P = N P lub L = $\mathrm{FP}$$L$$\mathrm{PTIME}$$N$$\mathrm{P = NP}$$\mathrm{L = P}$, w zależności od tego, czy początkowo wybrano język NP lub P-zupełny. Wygląda więc na to, że albo nie ma takich grup z rzadkimi orbitami, albo że obliczenie normalnych form jest trudne dla wszystkich takich grup, albo jeden z tych wyników utrzyma się, co myślę, że większość z nas nie wierzy. Ponadto wydaje się, że jeśli można obliczyć stosunek równoważności nad orbit zamiast zwykłych form można było nadal tym niejednorodnie w . Mam nadzieję, że niektórzy ludzie mają przemyślenia na ten temat.$\mathrm{P/poly}$

W przypadku NP wydaje się to trudne. W szczególności, jeśli możesz także próbkować (prawie) jednolite elementy ze swojej grupy - co jest prawdą w przypadku wielu naturalnych sposobów konstruowania grup - to jeśli język NP-complete ma działanie grupowe w czasie wielu z kilkoma orbitami, PH załamuje się. W przypadku, w tym dodatkowe założenie o sampleability norma protokołem Graph Izomorfizm działa również do testowania, czy dwa łańcuchy w tej samej G n -orbit. Wówczas mielibyśmy N P ⊆ c o A M / p o l y = c o N P /$\mathsf{coAM}$$G_n$ , tak załamuje pH do Z P P N P . Tak więc, aby uniknąć załamania PH, każda taka konstrukcja dla NP wymagałaby, aby grupyniemiały wydajnego, prawie jednolitego próbnika.$\mathsf{NP} \subseteq \mathsf{coAM/poly} = \mathsf{coNP/poly}$$\mathsf{ZPP}^{\mathsf{NP}}$

Moją intuicją jest to, że język NP-zupełny tego typu spowodowałby załamanie hierarchii wielomianowej, podobnie jak w twierdzeniu Karp-Lipton.

Mówiąc dokładniej, jeśli przejdziesz na drugi poziom wielomianowej hierarchii, możesz użyć potęgi hierarchii, aby odgadnąć równoważność między danym elementem grupy a jakimś przedstawicielem klasy równoważności, a następnie wrócisz do Karp –Lipton przypadek, w którym fakt, że masz wielomianowo wiele nierównych danych wejściowych, stawia cię w P / poli.

(Wynik powinien być taki sam jak odpowiedź Joshua Grochow, ale bez dodatkowego założenia próbności.)