Et NP-hardt problem er minst like vanskelig som de vanskeligste problemene i NP (NP problem).
Egenskaper:
- Krever ikke å være i NP (verifiserbar polynomisk tid)
En liten fotnote: Vi bruker Turing Reduksjoner for NPH, mens vi bruker Karp Reduksjon for NPC
Vi bruker ofte begrepet NP-hardhet også om mer generelle problemer.
Eksempel
The Halting Problem is a famous problem in computer science that asks whether there is an algorithm that can determine, for any given program and input, whether the program finishes running (halts) or continues to run forever. Alan Turing proved that no such algorithm can exist; this is known as Turing’s Halting Problem.
The reason why the Halting Problem is considered NP-hard is because it is at least as hard as the hardest problems in NP. Any NP problem can be reduced to a Halting Problem instance. However, the Halting Problem is not in NP (since there’s no way to verify a solution in polynomial time), making it even harder than NP-complete problems. It’s a fundamental example of an undecidable problem, which means there is no algorithm that can solve it for all possible inputs.