¿Hay lenguajes NP o P completos altamente simétricos?

14

¿Existe , un lenguaje completo NP o P que tiene una familia de grupos de simetría (o grupoide , pero luego las preguntas algorítmicas se vuelven más abiertas) actuando (en tiempo polinómico) en conjuntos tal que hay pocas órbitas, es decir, tal que para suficientemente grande algunosLGnLn={lL|l|=n}|Ln/Gn|<ncnc , y tal que puede generarse dado n eficientemente?Gnn

El punto aquí es que si uno encuentra un idioma / grupo como este, y si puede encontrar formas normales bajo acciones de grupos de tiempo polinomiales en , entonces puede reducir L por una reducción P T I M E a un lenguaje disperso calcular la forma normal para cualquier N dado , lo que implica que P = N P o L = PFPAGLPAGTyoMETROminortePAG=nortePAGL=PAG, dependiendo de si eligió un lenguaje NP o P completo inicialmente, respectivamente. Por lo tanto, parece que no existen tales grupos con órbitas dispersas o que calcular formas normales es difícil para todos esos grupos o que uno de estos resultados se mantendrá, lo que creo que la mayoría de nosotros no cree. También parece que si uno puede calcular la relación de equivalencia sobre las órbitas en lugar de las formas normales, todavía podría hacerlo de manera no uniforme, en . Esperando que otras personas tengan pensamientos sobre esto.PAG/ /pagoly

Samuel Schlesinger
fuente
44
¿Qué quiere decir con " -complete language"? {NP,P}
Emil Jeřábek apoya a Monica el
Me refiero a un lenguaje completo o N P. PAGnortePAG
Samuel Schlesinger el
1
¿Por qué crees que la existencia de una reducción polytime colapsaría P hasta L?
Emil Jeřábek apoya a Monica el
Habría pensado bajo las reducciones logarítmicas, pero dada la forma normal, el cálculo probablemente estaría en P, esto solo es relevante para NP. Gracias por mencionar eso.
Samuel Schlesinger

Respuestas:

12

Para NP, esto parece difícil de construir. En particular, si también puede muestrear elementos (casi) uniformes de su grupo, lo cual es cierto para muchas formas naturales de construir grupos, entonces si un lenguaje NP-completo tiene una acción de grupo poli-tiempo con pocas órbitas, el PH colapsa. Para, con esta suposición adicional sobre la capacidad de muestreo, el protocolo estándar para el isomorfismo gráfico también funciona para probar si dos cadenas están en el mismo órbita G n . Entonces tendríamos N Pc o A M / p o l y = c o N P / pCoUNMETROsolnorte , por lo colapsos pH a Z P P N P . Por lo tanto, para evitar el colapso del PH, cualquier construcción de este tipo para NP necesitaría que los gruposnotuvieran una muestra eficiente y casi uniforme.nortePAGCoUNMETRO/ /pagoly=ConortePAG/ /pagolyZPAGPAGnortePAG

Joshua Grochow
fuente
¡Agradable! Esto es exactamente lo que pensé que sucedería después de leer otra respuesta tuya sobre el problema representativo de la órbita.
Samuel Schlesinger
5

Mi intuición es que un lenguaje NP-completo de este tipo causaría un colapso de la jerarquía polinómica muy similar al del teorema de Karp-Lipton.

Más específicamente, si sube al segundo nivel de la jerarquía polinómica, puede usar el poder de la jerarquía para adivinar la equivalencia entre un elemento de grupo dado y algún representante de una clase de equivalencia, y luego vuelve al Karp - Caso de Lipton donde el hecho de que tenga polinomialmente muchas entradas no equivalentes lo coloca en P / poli.

(El resultado debería ser el mismo que el de la respuesta de Joshua Grochow, pero sin el supuesto adicional de capacidad de muestreo).

David Eppstein
fuente
Sin embargo, depende del tamaño del grupo, ¿verdad? Ni siquiera dije que el grupo era finito, solo que actúa en el lenguaje de manera eficiente y puede generarse de manera eficiente. Dicho esto, tengo la impresión de que si el grupo se puede muestrear eficientemente (como en la respuesta de Joshua), esto le permitirá resolver SAT en BPP, lo que implica lo que sugiere. No estoy seguro de esto, pero hay un enfoque que he estado persiguiendo que utiliza la auto reductibilidad de SAT y poda este árbol de reducciones al azar. Por lo que puedo decir, esto requiere que las órbitas tengan un tamaño similar.
Samuel Schlesinger
1
¿Cómo puede actuar en tiempo polinómico si se necesita más que tiempo polinómico solo para escribir un elemento de grupo?
David Eppstein
Muchos grupos infinitos tienen presentaciones finitas, ¿no? Estos no son necesariamente grupos de permutación, solo tienen un homomorfismo con un grupo de simetría de nuestro idioma.
Samuel Schlesinger
Dicho esto, creo que la capacidad de muestreo eficiente debería limitarlo a grupos simplemente exponencialmente grandes de todos modos
Samuel Schlesinger
1
Σ2PAG