¿Hay problemas de NP, no en P ni en NP Complete?

¿Hay algún problema conocido en $\mathsf{NP}$ (y no en $\mathsf{P}$ ) que no sea $\mathsf{NP}$ Complete? Tengo entendido que actualmente no hay problemas conocidos en este caso, pero no se ha descartado como una posibilidad.

Si hay un problema que es $\mathsf{NP}$ (y no $\mathsf{P}$ ) pero no $\mathsf{NP\text{-}complete}$ , ¿sería esto el resultado de un isomorfismo no existente entre las instancias de ese problema y el $\mathsf{NP\text{-}complete}$ set? En este caso, ¿cómo podríamos saber que el problema $\mathsf{NP}$ no es "más difícil" de lo que actualmente identificamos como $\mathsf{NP\text{-}complete}$ set?

¿Hay algún problema conocido en NP (y no en P) que no sea NP completo? Tengo entendido que actualmente no hay problemas conocidos en este caso, pero no se ha descartado como una posibilidad.

No, esto es desconocido (con la excepción de los lenguajes triviales y Σ ∗ , estos dos no están completos debido a la definición de reducciones de muchos, generalmente estos dos se ignoran al considerar las reducciones de muchos). La existencia de un problema de N P que no está completo para N P wrt muchas reducciones de tiempo polinomiales implicaría que P ≠ N P que no se conoce (aunque se cree ampliamente). Si las dos clases son diferentes entonces sabemos que hay problemas en N P que no se completa para que, toman ningún problema en P .$\emptyset$$\Sigma^*$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}\neq\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}$

Si hay un problema que es NP (y no P) pero no NP completo, ¿sería esto el resultado de un isomorfismo existente entre las instancias de ese problema y el conjunto NP completo?

Si las dos clases de complejidad son diferentes, entonces, según el teorema de Ladner, hay problemas que son intermedios, es decir, están entre P y N P - c o m p l e t e .$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP\text{-}complete}$

En este caso, ¿cómo podríamos saber que el problema NP no es "más difícil" de lo que actualmente identificamos como el conjunto NP completo?

Siguen siendo reducible tiempo polinómico a problemas por lo que no puede ser más difícil de N P - c o m p l e t e problemas.$\mathsf{NP\text{-}complete}$$\mathsf{NP\text{-}complete}$

Como dijo @Kaveh, esta pregunta solo es interesante si suponemos ; El resto de mi respuesta toma esto como una suposición, y en su mayoría proporciona enlaces para humedecer aún más su apetito. Bajo ese supuesto, por el teorema de Ladner sabemos que hay problemas que no están ni en P ni en N P C ; estos problemas se llaman N P intermedio: o N P I . Curiosamente, el teorema de Ladner se puede generalizar a muchas otras clases de complejidad para producir problemas intermedios similares. Además, el teorema también implica que hay una jerarquía infinita.$P \neq NP$$P$$NPC$$NP$$NPI$de los problemas intermedios que no son en tiempo poli reducible entre sí en .$NPI$

Desafortunadamente, incluso con la suposición es muy difícil encontrar problemas naturales que pudieran ser probables N P I (por supuesto, usted tiene los problemas artificiales que provienen de la demostración del teorema de Ladner). Por lo tanto, incluso suponiendo que P ≠ N P en este momento solo podemos creer que algunos problemas son N P I pero no lo demostramos. Llegamos a tales creencias cuando tenemos evidencia razonable para creer que un problema de N P no está en N P C y / o no está en $P \neq NP$$NPI$$P \neq NP$$NPI$$NP$$NPC$$P$; o solo cuando se ha estudiado durante mucho tiempo y se ha evitado encajar en cualquiera de las clases. Hay una lista bastante completa de tales problemas en esta respuesta . Incluye favoritos de todos los tiempos como factorización, registro discreto e isomorfismo gráfico.

$BQP$$BQP$N P I B Q P$NPC \not\subseteq BQP$$NPI$$BQP$

No NP problemas -Complete son conocidos por ser en P . Si hay un algoritmo de tiempo polinomial para cualquier problema NP completo, entonces P = NP , porque cualquier problema en NP tiene una reducción de tiempo polinomial para cada problema NP completo. (Así es como se define " NP- completo"). Y obviamente, si cada problema de NP- completo se encuentra fuera de P , esto significa que P ≠ NP . No estamos realmente seguros de por qué es difícil mostrarlo de una forma u otra; Si supiéramos la respuesta a esa pregunta, probablemente sabríamos mucho más sobre P yNP . Tenemos algunas técnicas de prueba que sabemos que no funcionan (relativización y pruebas naturales, por ejemplo), pero no tenemos una explicación basada en principios de por qué este problema es difícil.

Si hay problemas en NP que no están en P , entonces en realidad hay una jerarquía infinita de problemas en NP entre aquellos en P y aquellos que están completos en NP : este es un resultado llamado teorema de Ladner .

¡Espero que esto ayude!

$P$

$P$$P$

$P$

¹ Problema similar: el isomorfismo del subgrafo es NP-Completo en sentido fuerte.