Creo que asume erróneamente que el problema “duro de HP” es solo una palabra elegante para decir “un problema que pertenece a NP”. No lo es, no todos los problemas NP son difíciles de HP y no todos los problemas NP difíciles son NP. Como dijo Justin, NP-hard se define como “hay una reducción de tiempo polinomial de cualquier problema en NP a cualquier problema NP-hard” y la definición intuitiva es que “NP-hard problem es un problema que es tan difícil como CADA problema posible en NP o más duro “. Vea la tabla sobre la integridad de NP
Tiene razón si lo que quería preguntar es “¿un algoritmo de tiempo polinómico para un problema NP prueba que P = NP (…)?”, No hace mucho tiempo se publicó el algoritmo polinomial para la prueba de primalidad colocando este problema en P, fue algo enorme pero aún no sabemos si P = NP. Esto se debe a que la prueba de primalidad fue NP, pero no NP-completa (y por lo tanto tampoco NP-hard). (Además, bueno, P está contenido en NP, todo el problema obvio de P podría usarse para respaldar la verdad de su afirmación). NP-hard, por otro lado, es el término específicamente acuñado con esta razón particular en mente, que debería describir la clase de esos problemas para los cuales encontrar un algoritmo de tiempo polinómico significaría que P = NP.
- ¿Vale la pena estudiar un tema si no crees que podrías haber llegado incluso a las derivaciones / algoritmos / pruebas que se dan allí?
- ¿Qué es la ley de Fitts?
- ¿Debo comprar o construir un sistema informático para satisfacer mis necesidades?
- Cómo 'centrar verticalmente' más de 1 elementos flexibles
- ¿Cómo hace IDM que la descarga sea 5-8 veces más rápida?
