NP-Hard

← Back to Complexity Classes

Problems that are at least as hard as the hardest problems in NP. NP-Hard problems may not themselves be in NP (they may not even be decision problems or verifiable in polynomial time).

Key Properties

• At Least as Hard as NP-Complete

Related

• NP-Complete (NP-Complete = NP-Hard and in NP)
• NP (NP-Hard may not be in NP)

---

computational-complexity complexity-classes np-hard