Candidatos naturales para la jerarquía dentro de NPI

Supongamos que $\mathsf{P} \neq \mathsf{NP}$ . $\mathsf{NPI}$ es la clase de problemas en $\mathsf{NP}$ que no están ni en $\mathsf{P}$ ni en $\mathsf{NP}$ -duros. Puede encontrar una lista de problemas conjeturados como $\mathsf{NPI}$ aquí .

El teorema de Ladner nos dice que si $\mathsf{NP}\neq\mathsf{P}$ hay una jerarquía infinita de problemas $\mathsf{NPI}$ , es decir, hay problemas $\mathsf{NPI}$ que son más difíciles que otros problemas $\mathsf{NPI}$

Estoy buscando candidatos para tales problemas, es decir, estoy interesado en pares de problemas
- $A,B \in \mathsf{NP}$ ,
- conjetura que $A$ y $B$ son $\mathsf{NPI}$ ,
- $A$ sabe que 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 -hard? $\mathsf{NPI}$ $\mathsf{NP}$

complexity-theory np-hard Mohammad Al-Turkistany
fuente

Entonces, ¿está buscando problemas

tal que

con

P \in N P

$P \in \mathrm{NP}$

P_{1} \leq_{p} P \leq_{p} P_{2}

$P_1 \leq_p P \leq_p P_2$

P_{1} \in N P I

$P_1 \in \mathrm{NPI}$

P_{2} \in N P C

$P_2 \in \mathrm{NPC}$

Raphael

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

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

además, tenemos una lista muy buena en cstheory cstheory.stackexchange.com/questions/79/…

Marcos Villagra

¿Por qué la lista que enlaza Marcos no es la respuesta a su pregunta?

Suresh

Respuestas:

He encontrado un buen problema llamado ModularFactorial . ¡Tome como entrada dos enteros de dígitos e , 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. $n$ $x$ $y$ $x! \mod y$

Marcos Villagra
fuente

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

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?

n

$n$

k

$k$

n

$n$

d

$d$

1 < d \leq k

$1 < d \le k$

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.

x! \mod y

$x!\mod y$

k

$k$

Marcos Villagra