¿Cuáles son algunos ejemplos de problemas que son: (1) NP pero no NP-Complete; (2) NP-Completo; (3) NP-Hard pero no NP-Complete?

Los únicos dos problemas que ciertamente pertenecen a la primera categoría son los dos problemas triviales “falso” y “verdadero”. Ambas están claramente en NP: puede diseñar fácilmente una máquina de Turing de tiempo polinómico que acepta todo / una que rechaza todo. La razón por la que no son NP completos es un tecnicismo: no hay una reducción válida de muchos de un conjunto no trivial al conjunto vacío.

A menudo escuchará la respuesta “X está en NP pero no es NP completo”, donde “X” es un problema particular que se puede resolver en tiempo polinómico determinista. Esto está mal. Bueno, no es probable que esté mal, al menos todavía no, pero al menos es engañoso. Déjame explicarte por qué.

Considere la afirmación “la ordenación no es NP-completa”. Esta es una declaración verdadera, pero no por la razón correcta. La razón por la cual esta afirmación es cierta es solo un tecnicismo. NP es una clase de problemas de decisión : problemas donde la respuesta para cada instancia es sí o no. La clasificación no es un problema de decisión, por lo que no pertenece a NP. (Por supuesto, hay problemas en NP, e incluso en P, que están relacionados con la ordenación, por ejemplo, “es [matemática] \ pi [/ matemática] la permutación que ordena la matriz A?”. Sin embargo, en mi experiencia esto nunca fue lo que el autor de la declaración original tenía en mente 🙂)

Ahora considere la afirmación “la posibilidad de alcanzar el gráfico no es NP-completa”. Esto parece ser una declaración verdadera, ¿verdad? Es un problema de decisión: la instancia es una lista de aristas y dos etiquetas de vértice, y debemos aceptar la instancia si hay una ruta entre los dos vértices dados. Además, este problema está claramente en P: cualquier algoritmo transversal del gráfico calculará la respuesta en tiempo polinómico. Entonces, ¿es cierta esta afirmación? La respuesta correcta: no lo sabemos.

¿Por qué? Si P = NP, todos los problemas en NP (excepto los dos triviales mencionados anteriormente) son NP completos: puede hacer cualquier reducción resolviendo el primer problema y luego generando una instancia buena / mala del segundo problema en consecuencia. Por otro lado, si P! = NP, los problemas de NP completo no pueden estar en P. Por lo tanto, la afirmación de que la posibilidad de alcanzar el gráfico es NP completa es probablemente falsa, pero decir si es verdadero o falso es equivalente a resolver el P vs Pregunta NP.

Aquí hay una afirmación verdadera: “La accesibilidad del gráfico es NP-completa si y solo si P = NP”.

La lista de problemas con NP completo tiene muchos problemas con NP completo.

Para que un problema sea NP difícil pero no NP completo, tiene que estar fuera de NP.

Algunos problemas de optimización de hardware pueden clasificarse como “NP-hard”. Por ejemplo, uno puede reducir la existencia de un camino hamiltoniano para resolver el problema del vendedor ambulante, por lo que podemos decir que TSP es NP-hard. Por otro lado, TSP (el problema de optimización) no está en NP, solo está su versión de decisión. Entonces TSP sería un buen ejemplo de un problema que es NP-hard pero no NP-complete.

Por supuesto, eso se siente como hacer trampa 🙂

Así que quedémonos solo con problemas de decisión. Hay muchos problemas de decisión que son NP-hard pero no NP-complete. Un ejemplo simple es el problema de detención de las máquinas de Turing. Cualquier problema en NP puede reducirse fácilmente al problema de detención.

Por supuesto, ahora eso se siente como hacer trampa 🙂 Se sabe que el problema de Detención no se puede resolver, por lo que no sorprende que sea más difícil que cualquier otra cosa en NP, ¿verdad?

Afortunadamente, también hay problemas de decisión que son decidibles y probablemente no en NP. Por ejemplo, según el teorema de la jerarquía de tiempo hay problemas que están en NEXP pero no en NP. Por ejemplo, el problema de la ruta hamiltoniana sucinta (ver NEXPTIME) está en NEXP, no está en NP y es probablemente NP-duro, ya que podemos reducir la ruta hamiltoniana tradicional a su versión sucinta.

Primero debe comprender el significado de NP, NP-Hard y NP-Complete.

Dando definiciones directamente de Wikipedia:

NP es una “clase de problemas computacionales para los que las soluciones pueden ser calculadas por una máquina de Turing no determinista en tiempo polinomial. O, de manera equivalente, aquellos problemas para los que las soluciones pueden ser verificadas en tiempo polinómico por una máquina de Turing determinista”.

Otra forma de decir esto es que, dada una solución a este problema, puede verificarse en tiempo polinómico.

Los problemas NP-Hard son una “clase de problemas que son al menos tan difíciles como los problemas más difíciles en NP. Los problemas en NP-hard no tienen que ser elementos de NP, de hecho, incluso pueden no ser problemas de decisión”.

Los problemas de NP-Complete son una “clase de problemas que contiene los problemas más difíciles en NP. Cada elemento de NP-complete tiene que ser un elemento de NP”.

Otra forma de decir esto es que un problema es NP-Complete si es NP-Hard y se le da una solución a cualquier instancia del problema, la solución se puede verificar en tiempo polinómico.

Entonces, un ejemplo de un problema en NP pero no NP-Complete es el problema de clasificación. es decir, dados [math] n [/ math] enteros, reorganice los números de manera que no estén en orden decreciente. Esto se puede resolver fácilmente en [math] O (n \ log {n}) [/ math] (bueno, en realidad mejor). Claramente, puede verificar si una solución propuesta es realmente una solución en [math] O (n) [/ math], que es polinomial en [math] n [/ math].

Ningún problema puede ser NP-Completo, sin ser NP-Hard según la definición de NP-Completitud.

Un ejemplo de un problema NP-Complete es la camarilla. es decir, dado un gráfico no dirigido, ¿cuál es el gráfico completo más grande que es un subgrafo del gráfico?

Ahora, para un problema NP-Hard que no está en NP (es decir, no NP-Complete). Dados algunos [matemáticos] n [/ matemáticos], encuentre todas las camarillas en todos los gráficos con vértices [matemáticos] n [/ matemáticos]. Claramente, este problema es más difícil que el problema de la camarilla anterior ya que si podemos resolver este problema, podemos resolver el problema de la camarilla anterior. Además, tenga en cuenta que la respuesta a este problema es en realidad todos los subconjuntos de los vértices [matemáticos] n [/ matemáticos] que forman camarillas. Pero también tenga en cuenta que para verificar que tenemos la respuesta correcta, debemos verificar que tenemos todos los subconjuntos que forman camarillas. De hecho, este problema es NP-Hard, pero no NP-Complete.

Ver: Np completo

Voy a mantener mi respuesta breve ya que hay mucho sobre este tema.

(1) Problema de árbol de expansión mínimo (dado el resultado de una instancia de MST, es muy sencillo proporcionar un algoritmo que verifique si es un árbol de expansión y determina si su peso total es como máximo k en tiempo polinómico, o no. Esto implica que este problema está en NP. Este problema se puede resolver en tiempo polinómico usando algoritmos como el Algoritmo de Prim, por lo que también se encuentra en P. Encontrará que muchos problemas en P también se encuentran en NP.
(2) problema del árbol Steiner,
(3) Problema de detención (ver dureza NP).

Para agregar a las otras respuestas, la factorización de enteros (encontrar todos los factores primos de un número) es un ejemplo interesante de un problema que es NP pero no se sabe que es NP completo.

Está claramente en NP, ya que puede verificar en tiempo polinómico si una factorización dada es correcta.

No se sabe que esté en P, ya que no se han encontrado algoritmos deterministas de tiempo polinómico. (Técnicamente, no se han encontrado tales algoritmos para la versión de decisión del problema: dado N y M

Finalmente, hay alguna evidencia débil que sugiere que (si P! = NP) la factorización no es tan difícil como los problemas de NP completo. Ver Factorización entera

AFAIR el problema de ‘tautología’ que se ‘da una expresión booleana, si esa expresión es siempre verdadera’ es un problema NP difícil porque:
1. El problema de “satisfacción” puede reducirse a este problema.
2. No se sabe que el problema de ‘tautología’ esté en NP.

Para agregar a las otras respuestas, en particular a la pregunta (3), muchos problemas de razonamiento lógico son NP-hard, pero no en NP: aquellos problemas que son NExpTime-hard o más difíciles. Dos ejemplos bastante interesantes son los problemas para decidir la coherencia de las ontologías expresadas en OWL 1 DL y OWL 2 DL, que forman parte del estándar del W3C para la Web Semántica. La consistencia de la ontología en OWL 1 DL es NExpTime-hard, mientras que en OWL 2 DL, es N2ExpTime-hard, que es aún más difícil.

Consulte: Descripción general del lenguaje de ontología web de OWL y Descripción general del documento del lenguaje de ontología web de OWL 2 (segunda edición)