Candidatos naturales para la jerarquía dentro de NPI

22

Supongamos que PNP . NPI es la clase de problemas en NP que no están ni en P ni en NP -duros. Puede encontrar una lista de problemas conjeturados como NPI aquí .

El teorema de Ladner nos dice que si NPP hay una jerarquía infinita de problemas NPI , es decir, hay problemas NPI que son más difíciles que otros problemas NPI

Estoy buscando candidatos para tales problemas, es decir, estoy interesado en pares de problemas
- A,BNP ,
- conjetura que AA y B son NPI ,
- A sabe que A se reduce a B ,
- pero hay sin reducciones a partir conocida B a A .

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

¿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 sea N P -hard?NPINP

Mohammad Al-Turkistany
fuente
1
Entonces, ¿está buscando problemas tal que P 1 p P p P 2 con P 1N P I y P 2N P C ? PNPP1pPpP2P1NPIP2NPC
Raphael
1
Sí, pero no hay una reducción conocida de P a P1 (de manera similar, no hay una reducción conocida de P2 a P).
Mohammad Al-Turkistany
2
Hay varios problemas con un estado similar a la factorización, vea este artículo de Papadimitriou theory.stanford.edu/~megiddo/pdf/papadimX.pdf
Marcos Villagra
8
además, tenemos una lista muy buena en cstheory cstheory.stackexchange.com/questions/79/…
Marcos Villagra
2
¿Por qué la lista que enlaza Marcos no es la respuesta a su pregunta?
Suresh

Respuestas:

5

He encontrado un buen problema llamado ModularFactorial . ¡Tome como entrada dos enteros de dígitos x e y , y dé salida a . Este problema es al menos tan difícil como Factoring y no se sabe que sea difícil para FNP . La referencia es el libro reciente (y hermoso) de Cristopher Moore y Stephan Mertens The Nature of Computation , página 79.nxyx!mody

Marcos Villagra
fuente
1
Creo que el OP está buscando problemas en NP. ¿Se puede reformular esto como un problema de decisión?
Zach Langley
FNP es la versión de función (es decir, problemas de búsqueda) de NP. De hecho, la factorización no está en NP, es FNP. Por ejemplo, el problema de decisión para factorizar es trivial, la complejidad es solo O (1), pero el problema de búsqueda es la parte difícil. Dado que el OP dio un factoring como ejemplo, creo que esta también es una respuesta válida.
Marcos Villagra
1
La factorización puede reformularse en un problema de decisión de la siguiente manera: dado un número entero y un número entero , ¿ contiene un factor con ? ¿Existe una versión de decisión análoga del problema ModularFactorial? k n d 1 < d knknd1<dk
Zach Langley
@Marcos, gracias. Estoy interesado en problemas de decisión en NP.
Mohammad Al-Turkistany
@ZachLangley, sí, por supuesto, estoy de acuerdo, pero estaba pensando en otra versión de decisión, a saber, "¿tiene x un factor?". La respuesta es simplemente "sí" siempre. Puede hacer lo mismo con modularfactorial, dar un número entero k y decidir si es mayor que o no. kx!modyk
Marcos Villagra