¿Cómo demuestras que un problema es NP-hard? Reduce otro problema al problema que desea probar la dureza NP. Este proceso se llama reducción .
En una reducción , tomamos un problema que sabemos que es NP-duro, y demostramos que cualquier instancia de ese problema puede escribirse como una instancia del problema que deseamos probar la dureza de NP.
Sin embargo, tenga en cuenta que el TSP es NP-competir, es decir, pertenecer a los problemas NP-hard “más fáciles”. O bien, se podría decir que es un problema al mismo tiempo NP y NP-hard. Vale la pena señalar que todos los problemas de NP completo también son “equivalentes”.
- ¿Qué son las estrategias de diseño de algoritmos?
- ¿Es la prueba de primalidad Rabin-Miller más rápida que el tamiz de Eratóstenes?
- Acabo de completar el primer año de ingeniería informática. Quería mejorar mi pensamiento lógico y algorítmico resolviendo problemas de un juez en línea. ¿Dónde empiezo?
- ¿Cuál es el problema de programación más difícil que haya resuelto?
- ¿Cómo debo hacer para que una matriz de objetos Bullet pueda colisionar con una matriz de objetos Zombie?
Entonces, primero, lo reduce para probar la dureza NP, luego muestra que es NP. Para demostrar que es un problema de NP, simplemente tome una solución y pregúntese: “Oye, si tengo una solución óptima, ¿puedo estar seguro de que es una solución óptima?”. En otros términos, ¿puede saber si una solución es óptima o no, simplemente mirándola (o realizando algunos cálculos rápidos. “Rápido” aquí significa que su algoritmo para la verificación debe ejecutarse en tiempo polinómico).
Ahora, si desea probar que el TSP es NP completo (implica la dureza NP), puede echar un vistazo a esta pregunta ¿Por qué el problema del vendedor ambulante NP está completo? La respuesta dada por Luke Benning es detallada y bien explicada.
EDITAR: Olvidé mencionar en el cuarto párrafo que si no puede saber si la solución dada es óptima o no, entonces es NP.
