“Informalmente, NP es el conjunto de todos los problemas de decisión para los cuales las instancias donde la respuesta es” sí “tienen pruebas verificables de manera eficiente”.
Es decir, no puede verificar la inexistencia en tiempo polinomial.
Prueba por contradicción de que es poco probable que sea posible verificar la inexistencia en el tiempo polinómico.
- Cómo entender las matemáticas del algoritmo de propagación hacia atrás en redes neuronales
- Sistemas distribuidos: ¿El resultado de imposibilidad de FLP y el teorema de CAP de Brewer son básicamente equivalentes?
- ¿Por qué el tiempo de ejecución para la parte de fusión de merge sort [math] \ theta (n) [/ math]?
- ¿Se pueden convertir las máquinas de Turing en un DFA?
- ¿Existe alguna analogía en la vida real con el concepto de expresiones regulares?
Supongamos que tiene un algoritmo X que puede verificar la inexistencia de una ruta hamiltoniana en tiempo polinómico.
Dado un gráfico G, simplemente declaramos “sin solución” y dejamos que el algoritmo X lo verifique en tiempo polinómico. Si X verifica la respuesta, ha determinado que G no tiene una ruta hamiltoniana en el tiempo polinomial, si X rechaza la respuesta, entonces ha determinado que G tiene una ruta hamiltoniana en el tiempo polinomial.
Sabemos que el problema de decisión es NP-complete => NP-hard. Todos los problemas NP-hard pueden reducirse entre sí, por lo que para cualquier otro problema NP NP-hard simplemente podemos generar un gráfico equivalente G en tiempo polinómico al que si conocemos la existencia / no existencia de una solución garantiza una existencia similar / inexistencia de una solución en P.
Por lo tanto, el algoritmo X resuelve efectivamente el problema de decisión de NP completo y finalmente dejaría de lado la pregunta de $ 1,000,000 de P = NP. Además, el algoritmo X será una prueba constructiva.
