Si digo solo np-hard que no significa np o no npc, entonces ¿qué significa? ¿Es un problema indecidible?

Answer 1

Hablando en términos generales, los problemas NP completos son un subconjunto de problemas NP-difíciles.

Definiciones:

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

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. Así, 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.

Answer 2

Cuando un problema es NP-hard pero no en NP y no en NPC, entonces es un problema de optimización para el que no podemos verificar la solución en tiempo polinómico (para el problema de cobertura mínima de vértice no podemos verificar la solución en tiempo polinómico, si es solo la cubierta del vértice que podemos verificar en tiempo polinómico pero no para la cubierta mínima del vértice)