No necesariamente. La noción de capacidad de decisión es un poco diferente de NP-Hardness y NP-Completeness.
Hablando en términos generales, los problemas NP completos son un subconjunto de problemas NP-difíciles.
Vamos a obtener algunas definiciones correctas y luego daré ejemplos.
NP-hard : se dice que un problema P es NP hard si todos los problemas en NP son reducibles a P.
NP-Complete : Se dice que un problema P es NP-Complete si:
(i) todos los problemas en NP son reducibles a P, es decir, P es NP-duro
y (ii) P se encuentra en NP
- ¿Qué enfoque debería usarse para resolver esta pregunta sobre hackerrank?
- Cómo encontrar el enésimo número faltante más pequeño de una matriz de números
- ¿Qué es un buen algoritmo para las respuestas de la prueba de personalidad?
- ¿Cuál es la complejidad de este algoritmo de conteo de bits?
- ¿Cómo se puede ser bueno para resolver problemas de algoritmos / programación? Soy un principiante, y me sugirieron que leyera el libro CLRS para aprender sobre algoritmos.
Por lo tanto, los problemas NP-completos son los problemas más difíciles que se encuentran en NP.
Problema P Idioma L
Cualquier problema P puede convertirse en un problema de decisión mediante el cual sus entradas sean aceptadas o rechazadas. Por lo tanto, un lenguaje L se construye a partir del problema que contiene todas las entradas que se aceptan. Por ejemplo: considere el problema de encontrar números primos. Esto se puede enmarcar como dado un número ‘p’ encontrar si es primo o no. El lenguaje L será, por lo tanto, un conjunto de todos los números primos.
Decidible : se dice que un problema L es decidible si existe un algoritmo con acepta todos los elementos de L y rechaza aquellos que no pertenecen a L. Tenga en cuenta que el tiempo no es una restricción cuando se trata de la capacidad de decisión. Si uno puede escribir algún algoritmo que haga el trabajo, el problema será decidible.
Por lo tanto, todos los problemas que pertenecen a NP son decidibles. Pero NP hard no implica decidabile siempre. En principio, todos los problemas en NP pueden reducirse a Halting Problem, que puede clasificarse como NP-hard e indecidible.
En resumen:
1. NP completo = NP difícil + el problema radica en NP
2. Los problemas difíciles de NP pueden o no estar en NP
3. La capacidad de decisión no depende de la complejidad del tiempo.
4. NP-hard no implica ni decidible ni indecidible.
Ejemplos:
1. NP-Hard, decidible pero no NP-Complete
El lenguaje de la fórmula booleana cuantificada verdadera es decidible en el espacio polinomial, pero no en el tiempo polinomial no determinista. Por lo tanto, es un buen ejemplo, ya que se encuentra más allá de NP, es decidible y NP-duro también.
2. NP-Hard, decidible y también NP-Complete
Esto básicamente se reduce a un problema NP-Completo que es decidible. Por lo tanto, todos los problemas de NP-Complete son ejemplos, ya que todos ellos son decidibles.
