The class of problems at least as hard as every problem in NP, in the sense that any NP problem can be reduced to one, so an efficient algorithm for an NP-hard problem would give an efficient algorithm for all of NP; an NP-hard problem need not itself be in NP.
Facts
Core PrincipleA problem H is NP-hard if every problem in NP has a polynomial-time reduction to H. 1 Connections
Sources
1. NP-hardness, Wikipedia
Lead section, first sentenceQuote, Lead section, first sentence
a computational problem H is called NP-hard if, for every problem L which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from L to H.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.