Existe-t-il des langages NP ou P complets très symétriques?

14

Existe-t-il , un langage NP ou P-complet qui a une famille de groupes de symétrie G n (ou groupoïde , mais alors les questions algorithmiques deviennent plus ouvertes) agissant (en temps polynomial) sur des ensembles L n = { l L | l | = n } tel qu'il y ait peu d'orbites, ie tel que | L n / G n | < n c pour assez grand n et certains c , et tel que G nLGnLn={lL|l|=n}|Ln/Gn|<ncncgnpeut être généré étant donné efficacement?n

Le point ici est que si l'on trouve un langage / groupe tel que celui-ci, et si l'on peut trouver des formes normales sous des actions de groupe de temps polynomial dans , alors on peut réduire L par une réduction de P T I M E à une langue clairsemée par calculer la forme normale pour tout N donné , ce qui implique que P = N P ou L = PFPLPTIMENP=NPL=P, selon que vous avez choisi une langue NP ou P-complete au départ, respectivement. Il semble donc qu'il n'y ait pas de tels groupes avec des orbites clairsemées ou que le calcul des formes normales soit difficile pour tous ces groupes ou l'un de ces résultats tiendra, ce que je pense que la plupart d'entre nous ne croient pas. Il semblerait également que si l'on peut calculer la relation d'équivalence sur les orbites au lieu des formes normales, on pourrait toujours le faire de manière non uniforme, en . En espérant que d'autres personnes y réfléchissent.P/poly

Samuel Schlesinger
la source
4
Qu'entendez-vous par une " langue complète "? {NP,P}
Emil Jeřábek soutient Monica
Je veux dire un langage complet ou N P. PNP
Samuel Schlesinger
1
Pourquoi pensez-vous que l'existence d'une réduction de polytemps réduirait P à L?
Emil Jeřábek soutient Monica
J'aurais pensé sous les réductions logarithmiques mais étant donné la forme normale, le calcul serait presque certainement en P, cela n'est vraiment pertinent que pour NP. Merci d'avoir mentionné cela.
Samuel Schlesinger

Réponses:

12

Pour NP, cela semble difficile à construire. En particulier, si vous pouvez également échantillonner des éléments (presque) uniformes de votre groupe - ce qui est vrai pour de nombreuses façons naturelles de construire des groupes - alors si un langage NP-complet a une action de groupe poly-temps avec peu d'orbites, le PH s'effondre. Car, avec cette hypothèse supplémentaire sur l'échantillonnage, le protocole standard pour l'isomorphisme graphique fonctionne également pour tester si deux chaînes sont dans la même orbite G n . On aurait alors N Pc o A M / p o l y = c o N P / pcoAMGn ,sorteeffondrement de PH à Z P P N P . Ainsi, pour éviter l'effondrement du PH, une telle construction pour NP nécessiterait que les groupesnedisposentpasd'un échantillonneur efficace presque uniforme.NPcoAM/poly=coNP/polyZPPNP

Joshua Grochow
la source
Agréable! C'est exactement ce que je pensais qu'il se passerait après avoir lu une autre de vos réponses sur le problème du représentant de l'orbite.
Samuel Schlesinger
5

Mon intuition est qu'un langage NP-complet de ce type entraînerait un effondrement de la hiérarchie polynomiale un peu comme celui du théorème de Karp-Lipton.

Plus précisément, si vous montez au deuxième niveau de la hiérarchie polynomiale, vous pouvez utiliser le pouvoir de la hiérarchie pour deviner l'équivalence entre un élément de groupe donné et un représentant d'une classe d'équivalence, puis vous revenez au Karp –Lipton cas où le fait que vous ayez plusieurs entrées polynomiales inéquivalentes vous place en P / poly.

(Le résultat devrait être le même que la réponse de Joshua Grochow, mais sans l'hypothèse supplémentaire de l'échantillonnage.)

David Eppstein
la source
Cela dépend de la taille du groupe, non? Je n'ai même pas dit que le groupe était fini, juste qu'il agit efficacement sur la langue et peut être généré efficacement. Cela étant dit, j'ai l'impression que si le groupe peut être échantillonné efficacement (comme dans la réponse de Joshua), cela vous permettrait de résoudre SAT dans BPP en impliquant ce que vous proposez. Pas positif, mais il y a une approche que je poursuis qui utilise l'auto-réductibilité de SAT et élague cet arbre de réductions au hasard. Pour autant que je sache, cela nécessite que les orbites aient une taille similaire.
Samuel Schlesinger
1
Comment pouvez-vous agir en temps polynomial s'il faut plus que du temps polynomial pour écrire un élément de groupe?
David Eppstein
Beaucoup de groupes infinis ont des présentations finies, non? Ce ne sont pas nécessairement des groupes de permutation, ils ont juste un homomorphisme avec un groupe de symétrie de notre langue.
Samuel Schlesinger
Cela étant dit, je pense que l'échantillonnage efficace devrait de toute façon vous confiner à de grands groupes exponentiellement
Samuel Schlesinger
1
Σ2P