An NP-hard problem is one for which no polynomial-time algorithm is known, and solving it quickly would allow us to solve all problems in the complexity class NP efficiently. These problems are at least as hard as the hardest problems in NP, and finding a polynomial-time solution to any NP-hard problem would imply P = NP, a major unsolved question in computer science.