| Definition | A problem that is at least as hard as the hardest problems in NP. | A problem that belongs to both NP and is NP-hard. |
| Polynomial-time Reduction | Polynomial-time reduction from any NP problem to an NP-hard problem. | Polynomial-time reduction from any NP problem to an NP-complete problem. |
| Membership in NP | Not necessarily in NP. | Must be in NP. |
| Solvability | May or may not be solvable in polynomial time. | Unlikely to have a polynomial-time algorithm; no known polynomial-time algorithm exists. |
| Examples | Traveling Salesman Problem (TSP), 3-SAT, Vertex Cover. | Boolean Satisfiability (SAT), Knapsack Problem, Hamiltonian Cycle. |
| Importance | Serves as a benchmark for the complexity of problems. | Identifies the hardest problems in NP and serves as a basis for many other complexity results. |
| Relationship | All NP-complete problems are also NP-hard. | Not all NP-hard problems are NP-complete. Some NP-hard problems may not be in NP. |
