Candidatos naturales para la jerarquía dentro de NPI

16

Supongamos que . N P I es la clase de problemas en que no están ni en ni en N P -hard. Puede encontrar una lista de problemas conjeturados como N P I aquí .PNPNPIPNPPNPNPI

El teorema de Ladner nos dice que si entonces hay una jerarquía infinita de problemas N P I , es decir, hay problemas N P I que son más difíciles que otros problemas N P I.NPPNPINPINPyo

Estoy buscando candidatos para tales problemas, es decir, estoy interesado en pares de problemas
- , - Se conjetura que A y B son N P I , - Se sabe que A se reduce a B , - pero hay sin reducciones a partir conocida B a a .UN,sinortePAG
UNsinortePAGyo
UNsi
siUN

Aún mejor si hay argumentos para apoyarlos, por ejemplo, hay resultados que no reduce a A suponiendo algunas conjeturas en la teoría de la complejidad o la criptografía.siUN

¿Hay ejemplos naturales de tales problemas?

Ejemplo: Se supone que el problema de isomorfismo gráfico y el problema de factorización de enteros están en y hay argumentos que respaldan estas conjeturas. ¿Hay algún problema de decisión más difícil que estos dos pero no se sabe que es N P- duro?nortePAGyonortePAG

Mohammad Al-Turkistany
fuente
3
Publicado aquí según la sugerencia de Kaveh después de que una recompensa de CS Stackexchange expiró sin una respuesta satisfactoria.
Mohammad Al-Turkistany
Copia en informática .
Kaveh

Respuestas:

18

Isomorfismo grupal Isomorfismo gráfico m Isomorfismo en anillo. También Factorización entera m Isomorfismo de anillo [ Kayal y Saxena ]. También Graph Automorphism m Graph Isomorphism.metrometrometrometro

No solo no hay reducciones conocidas a la inversa, sino que probablemente no hay reducción de de Iso de gráfico a Iso de grupo [ Chattopadhyay, Toran y Wagner ].UNC0 0

Tenga en cuenta que una reducción de isomorfismo en anillo a isomorfismo gráfico también proporcionaría una reducción de factorización de enteros a isomorfismo gráfico. Para mí, tal reducción sería sorprendente, aunque quizás no impactante.

(Para Graph Automorphism vs Graph Isomorphism, se sabe que sus versiones de conteo son equivalentes entre sí y equivalentes a decidir Graph Isomorphism. Sin embargo, eso no necesariamente dice mucho, ya que la versión de conteo de coincidencia bipartita es equivalente a la versión de conteo de SAT. )

Creo que no hay un consenso real en cuanto a que, en su caso, de estos son en realidad en . Si alguno de estos problemas es N P -completo, entonces P H colapsa al segundo nivel. Si la factorización es N P -Complete, entonces se colapsa para el primer nivel, es decir, N P = c o N P .PAGnortePAGPAGHnortePAGnortePAG=ConortePAG

Además, me parece recordar que el uso de técnicas similares a Ladner puede mostrar que cualquier orden parcial contable puede integrarse en el orden de los problemas en N P (por lo que no es solo una jerarquía, sino un orden parcial contable arbitrariamente complicado) .metronortePAG

Joshua Grochow
fuente
1
Encuentro la mezcla silenciosa de versiones de conteo y versiones de decisión bastante confusa. Un anillo es una estructura finita, y el (versión de decisión de) isomorfismo de estructuras finitas es completo GI. Entonces, la versión de decisión del isomorfismo en anillo no es más difícil que GI ni más difícil que la factorización entera.
Thomas Klimpel
1
TyoMETROmi(O(norteIniciar sesiónnorte))
@ThomasKlimpel: Si al "mezclar en silencio" se refiere al párrafo entre paréntesis, las equivalencias a las que se hace referencia son en términos de reducciones de Turing de tiempo polinómico (también conocidas como reducciones de Cook), no reducciones de muchos.
Joshua Grochow
OK, he leído el comienzo de la referencia ahora. El anillo está dado por tablas de suma / múltiples, pero estas tienen una representación comprimida canónica para los anillos (porque el grupo aditivo es abeliano), por lo que el resultado de completitud GI para estructuras finitas no es relevante. No caracterizaría esta representación como "gens y relaciones", porque eso suena como la "mezcla silenciosa" de la que inicialmente me quejé. Comentario no relacionado: ni me referí al párrafo entre paréntesis, ni asumí que el isomorfismo en anillo debería ser completo GI, solo que no debería ser más difícil que GI.
Thomas Klimpel
@ThomasKlimpel: Lo siento, tienes razón, no se trata de gens y relaciones. (Y leí mal su comentario sobre GI-complete vs "no más difícil que GI".) Pensé que entendía lo que querías decir con "mezcla silenciosa", pero dado tu último comentario ya no entiendo. Pero quizás esto no sea tan pertinente para cstheory.stackexchange y podría enviarme un correo electrónico directamente para ayudar a aclarar mi comprensión (después de lo cual podría actualizar la respuesta si es necesario).
Joshua Grochow