La respuesta es sí. Realmente es así de directo, pero de ninguna manera es una tarea fácil. Los principiantes que primero intentan resolver el problema P vs. NP generalmente comienzan con problemas gráficos como el ciclo hamiltoniano, luego pasan a tratar de resolver otros problemas.
En particular, creo que k-SAT con k> 2 demuestra muy claramente por qué P no es igual a NP. Simplemente no sabemos cómo demostrarlo.
Tenga en cuenta que con el problema del ciclo hamiltoniano debe comprender el problema. Claramente, si solo hay tres puntos, o menos, solo hay un ciclo posible, y por lo tanto, tales instancias no calificarían.
- ¿Cuál es el significado del módulo? ¿Cuál es el proceso de pensamiento detrás del uso del módulo?
- ¿A qué programas de Maestría en Ciencias de la Computación debo aplicar?
- ¿Cómo funcionan los ajustes del algoritmo del generador de sueños?
- ¿Es el código realmente ilegible sin los caracteres de espacio 'innecesarios'?
- ¿Cuál es el grado de una ecuación polinómica que tendría una raíz constructiva real positiva de esta forma, [math] \ sqrt {2} + \ sqrt [4] {3} [/ math]?
Además, existen soluciones de tiempo pseudopolinomial que utilizan programación dinámica. En otras palabras, si discretiza el problema, puede ser significativamente más fácil, pero no se considera una solución de tiempo P del problema original.
