Apakah Ada Bahasa NP- atau P-Lengkap yang Sangat Simetris?

Apakah ada , bahasa NP- atau P-lengkap yang memiliki keluarga kelompok simetri G n (atau groupoid , tetapi kemudian pertanyaan algoritmik menjadi lebih terbuka) bertindak (dalam waktu polinomial) pada set L n = { l ∈ L ∣ | aku | = n } sedemikian sehingga ada beberapa orbit, yaitu sedemikian sehingga | L n / G n | < n c untuk n cukup besar dan beberapa c , dan sedemikian rupa sehingga G $L$$G_n$$L_n = \{ l \in L \mid |l| = n \}$$|L_n / G_n| < n^c$$n$$c$$G_n$dapat dihasilkan mengingat efisien?$n$

Intinya di sini adalah bahwa jika salah satu temuan bahasa / kelompok seperti ini, dan jika salah satu dapat menemukan bentuk normal dalam kelompok tindakan waktu polinomial di , maka salah satu dapat mengurangi L oleh P T I M E pengurangan ke bahasa jarang oleh menghitung bentuk normal untuk setiap N yang diberikan , menyiratkan bahwa P = N P atau L = $\mathrm{FP}$$L$$\mathrm{PTIME}$$N$$\mathrm{P = NP}$$\mathrm{L = P}$, tergantung pada apakah Anda memilih bahasa NP- atau P-lengkap pada awalnya, masing-masing. Jadi sepertinya tidak ada grup dengan orbit yang jarang atau komputasi bentuk normal sulit untuk semua grup seperti itu atau salah satu dari hasil ini akan bertahan yang saya pikir sebagian besar dari kita tidak percaya. Juga akan terlihat bahwa jika seseorang dapat menghitung hubungan ekivalensi atas orbit daripada bentuk normal, ia masih bisa melakukan ini secara tidak seragam, dalam . Berharap beberapa orang memikirkan hal ini.$\mathrm{P/poly}$

Untuk NP, ini tampaknya sulit untuk dibangun. Khususnya, jika Anda juga dapat mengambil sampel (hampir) elemen seragam dari grup Anda - yang berlaku untuk banyak cara alami membangun grup - maka jika bahasa lengkap-NP memiliki tindakan kelompok waktu-poli dengan sedikit orbit, PH akan runtuh. Karena, dengan asumsi tambahan tentang kemampuan sampel, protokol standar untuk Graph Isomorphism juga berfungsi untuk menguji apakah dua string berada dalam G n -orbit yang sama. Kami kemudian akan memiliki N P ⊆ c o A M / p o l y = c o N P /$\mathsf{coAM}$$G_n$ , sehingga runtuh PH ke Z P P N P . Jadi, untuk menghindari kolapsnya PH, konstruksi seperti apa pun untuk NP akan membutuhkan kelompok-kelompok tersebut untuktidakmemiliki sampler yang hampir seragam dan efisien.$\mathsf{NP} \subseteq \mathsf{coAM/poly} = \mathsf{coNP/poly}$$\mathsf{ZPP}^{\mathsf{NP}}$

Intuisi saya adalah bahwa bahasa NP-lengkap dari jenis ini akan menyebabkan runtuhnya hierarki polinomial seperti yang ada dalam teorema Karp-Lipton.

Lebih khusus, jika Anda naik ke tingkat kedua hierarki polinomial, Anda dapat menggunakan kekuatan hierarki untuk menebak kesetaraan antara elemen grup yang diberikan dan beberapa perwakilan dari kelas ekivalensi, dan kemudian Anda kembali ke Karp –Lipton case di mana fakta bahwa Anda memiliki banyak input yang tidak setara secara polinomi menempatkan Anda dalam P / poly.

(Hasilnya harus sama dengan jawaban Joshua Grochow, tetapi tanpa asumsi sampel yang ditambahkan.)