NP-hard es al menos tan duro como el problema más duro en NP, lo que significa que si puede resolverlo en tiempo polinómico, puede resolver todos los problemas en NP en tiempo polinómico, por lo tanto P = NP.
Sin embargo, estar en NP significa que la solución debe ser comprobable en tiempo polinómico.
Entonces, si su problema es tan difícil que incluso su solución no puede verificarse en tiempo polinómico, entonces no está en NP, de hecho, esta es la definición de NP-duro en el sentido fuerte, por lo que preguntó: al menos igual de difícil como el problema más difícil en NP, pero no en NP.
- Entrevista Street puzzle: ¿Pregunta de hormigas en la sección de matemáticas?
- ¿Cuáles son las posibles amenazas para un algoritmo RSA y cuáles son sus contramedidas?
- Cómo escribir un orden de fusión en SQL sin formato
- ¿Cuál es el algoritmo utilizado para la agrupación de documentos de texto después de aplicar LSA?
- ¿Cómo usaría BFS en un árbol para imprimir los valores de cada nivel por separado?
La respuesta a su segunda pregunta, si resulta que P = NP, esto aún dejaría abierta la posibilidad de problemas que son NP-hard en el sentido fuerte, NP-hard, pero no en NP. Este diagrama ilustra la diferencia entre P = / = NP y P = NP:
