¿Existe algún problema que esté en NP pero no en NP-Completo?
¿Existe alguna posibilidad de que este problema sea análogo al problema P=NP, si es así, hay algún problema que esté en NP, pero actualmente no hay ninguna prueba o refutación sobre su NP-Completitud?
Si hay algún problema no trivial* en $\text{NP}$ pero no es $\text{NP}$ -Completo, implicaría que $\text{P} \neq \text{NP}$ . Esto se debe a que si $\text{P} = \text{NP}$ entonces cada problema no trivial en $\text{P}$ (y por tanto, por suposición, en $\text{NP}$ ) es $\text{NP}$ -Completo, mediante una reducción en tiempo polinómico que resuelve el problema como parte de la reducción, y crea una entrada ficticia para el problema objetivo (aquí es donde necesitamos la suposición no trivial).
Un ejemplo clásico de problema en $\text{NP}$ que se conjetura que no está en $\text{P}$ y no $\text{NP}$ -Completo es el Problema de isomorfismo de grafos .
De hecho, bajo el supuesto de que $\text{P} \neq \text{NP}$ Ya ha sido probado que hay un número infinito de jerarquías en $\text{NP}$ : es decir, a partir de $\text{P}$ los problemas cada vez más difíciles (es decir, el subconjunto adecuado), terminando con el $\text{NP}$ -Problemas completos. Ver esta pregunta de cstheory: https://cstheory.stackexchange.com/questions/52/hierarchies-in-np-under-the-assumption-that-p-np
*No trivial significa aquí: cualquier lenguaje que no sea el conjunto vacío o su complemento.
La clase de problemas NP contiene también todos los problemas en P. De hecho, los problemas NP-completos son los más difíciles de la clase NP. Además, hay problemas que no se sabe que son NP-completos (no hay pruebas todavía) mientras que no conocemos ninguna solución polinómica para ellos (todavía).
Sí.
Hay todo un entramado de clases de complejidad bajo NP, la mayoría de las que se definen por su nombre no se conocen pero se sospecha que son subconjuntos propios de NP, el más famoso es P. Es decir, no se sabe si algún problema particular en P no es NP-completo (aunque se espera).
Pero P no es la única subclase de NBPu.t TPh eirse naorte tthhe ocnllays sseusb cNlLa,s sL ,o fA CN_Pn, TNhCe_rne, aLrOeG CtFhLe, cDlEBaTus,ts eePst ciN.sL ,pn roLet,s utAmhCae_b nlo,yn lNmyCu _csnhu, b scLmlOaaGlsClsFe Lro, f t DhNEaPTn., NTePht.ec r.(e s pearere est uhtmeha eb lcyl amsuscehs sNmLa,l lLe,r AtCh_ann, NNPC._ n(,s eLeO GtChFeL , DET, etc. presumiblemente mucho menor que NP. (Pero P no es la única subclase de NP. Existen las clases NL, L, AC_n, NC_n, LOGCFL, DET, etc. presumiblemente mucho más pequeñas que NP. (véase el Zoológico de la Complejidad para las descripciones de las clases). Hay muchos problemas abiertos sobre la inclusión adecuada aquí.
Pero resulta que NLTIME, una clase muy restringida, la clase de problemas resolubles en log -time- no determinista (no en el Zoológico de la Complejidad)), es -probablemente- un subconjunto propio de NP. Es decir, hay problemas en NP que, de forma demostrable, no pueden reducirse a un problema en NLTIME.
Se conoce el siguiente orden de inclusión suelto:
$$NLTIME \subseteq L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$$
Nótese que NLTIME es un subconjunto de NP. Las únicas inclusiones propias conocidas en esta lista particular son entre NLTIME y NP, y entre L y PSPACE. Pero nadie (todavía) sabe dónde (o si) hay una ruptura adyacente en este orden lineal particular.
Pero la verdadera pregunta que se hace no es sobre las clases de complejidad, sino sobre los problemas. Hay muchos problemas del mundo real que tienen análogos de clases de complejidad en el 'Zoo' (por ejemplo, la alcanzabilidad en grafos no dirigidos está en NL). No puedo encontrar una referencia para la clase NLTIME (es fácilmente definible por NTIME( $\log(n)$ ), y mucho menos un problema dado para ello. Sin pensarlo demasiado, supongo que algún tipo de versión de decisión de Búsqueda binaria encajaría.
(a modo de apunte, es muy posible que haya otras clases más destacadas, como $AC_0$ (con problemas bien conocidos, que se sabe que se incluyen correctamente en NP, pero resulta que no lo sé)
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
