Teoría de la complejidad computacional: ¿Qué es un problema NP difícil?

Para una respuesta más completa, vea ¿Qué son P, NP, NP-complete y NP-hard?

Para una respuesta breve y simplificada:

Un problema de decisión es simplemente un conjunto de cadenas. Por ejemplo, SAT, el conjunto de todas las expresiones booleanas satisfactorias (escritas como cadenas) es un problema de decisión.
Un programa decide un conjunto si se le da un elemento del conjunto, genera un sí y se detiene, y si se le da un elemento que no está en el conjunto, genera un no y se detiene.
NP es el conjunto de todos los problemas de decisión [matemática] L [/ matemática] con la siguiente propiedad: Existe un programa [matemático] P [/ matemático] que dio un elemento [matemático] x \ en L [/ matemático] y un prueba de eso puede verificar eficientemente que la prueba es correcta. Además, dado cualquier [matemática] x \ not \ en L [/ matemática], no hay prueba de que el algoritmo acepte como válido. Esencialmente un problema de decisión está en NP si sus miembros pueden ser verificados eficientemente.
Un problema de decisión A se reduce a otro problema de decisión B si el problema A se puede decidir eficientemente dado un programa que decide eficientemente B.
Un problema de decisión es NP-difícil si todos los problemas en NP se reducen a él. Esencialmente, un problema es NP-hard si una solución eficiente nos permitiría resolver problemas NP de manera eficiente.

Aprendizaje automáticoinformáticateoría de la complejidad computacional

¿Dónde puedo encontrar conjuntos de datos para aprender autocorrección o corrección ortográfica?

Los algoritmos parecen estar involucrados con muchas partes de nuestras vidas. ¿Qué son y cómo podría aprender más?

¿Cuáles son algunas aplicaciones del aprendizaje semi-supervisado?

¿Qué has aprendido haciendo investigación?

En sus estatutos, ICANN declara que “coordina la asignación y asignación” de nombres de dominio y direcciones IP. ¿Qué diferencia hacen entre “asignación” y “asignación”?

¿Existe algún hardware especializado para algoritmos de aprendizaje profundo?

Informalmente, NP-hard significa más difícil o más difícil que los problemas más difíciles con soluciones fácilmente verificables. Se refiere al conjunto de todos los problemas que cumplen con este criterio.

Cuando decimos que el problema A es más difícil o tan difícil como otro problema B, queremos decir que el problema B puede expresarse en términos de (reducido a) problema A. Esto implica que resolver B es al menos tan fácil como resolver A, porque si tenemos un algoritmo eficiente para resolver A, también tenemos un algoritmo eficiente para resolver B que consiste en convertirlo a A y luego resolver A. Cuando decimos reducible, queremos decir que hay un algoritmo de tiempo polinómico que puede traducirse de un problema a otro. el otro.

Lo que se entiende por “los problemas más difíciles con soluciones fácilmente verificables” es la conocida clase de complejidad NP-complete. Nuevamente de manera informal, NP es el conjunto de todos los problemas cuyas soluciones pueden verificarse en una cantidad de tiempo razonable (polinómica). NP-complete se refiere al conjunto de los problemas más difíciles en NP. Si P no es igual a NP, como la mayoría cree, entonces ninguno de los problemas que son NP completos se pueden resolver en tiempo polinómico.

Por lo tanto, un problema NP-hard es cualquier problema al que se pueda reducir un problema NP-complete.

Si bien los problemas NP-completos deben ser problemas de decisión (se preocupan por descubrir si una declaración particular es verdadera o falsa), los problemas NP-hard pueden ser problemas de decisión, problemas de búsqueda (relacionados con la búsqueda de un objeto que cumpla con ciertos criterios) u optimización problemas (encontrar el mejor objeto que cumpla con ciertos criterios).

Algunos problemas NP-hard bien conocidos son las variantes de decisión y optimización de SAT, el Problema del vendedor ambulante, el Problema de subconjunto Problema de enrutamiento del vehículo, el Problema del vendedor ambulante. Muchos problemas NP-difíciles. Los algoritmos más conocidos para estos problemas toman tiempo exponencial. NP-hard también incluye problemas tales como los problemas de detención, que probablemente no se puedan resolver en un número finito de pasos

Sandy Ryza

Aquí hay un simplificado que realmente me quedó grabado.

NP es fácil. NP significa que si me das la respuesta al problema, será fácil para mí decir que es correcto.
NP-Hard significa que el problema es al menos tan difícil como cualquier cosa en NP . Técnicamente, significa que puede tomar cualquier problema en NP y convertirlo fácilmente en su problema NP-Hard . Lo que significa que si encuentra una manera rápida de resolver un problema NP-Hard , encontrará una manera rápida de resolver CADA problema en NP .
NP-Complete significa que el problema está tanto en NP como en NP-Hard. Es “completo” en el sentido de que es tan difícil como puede ser un problema, mientras todavía está en NP .