Advanced · Research
NP-hardness
Visual diagram · (in preparation) · Math · (in preparation) · Worked example · 3 difficulty levels.
TL;DR. Problems that are at least as hard as the most difficult problems in the NP complexity class.
Technical Definition
Problems that are at least as hard as the most difficult problems in the NP complexity class.
How it works
NP-hard problems are informally defined as being at least as difficult as the hardest problems in the complexity class NP. This means that if an NP-hard problem could be solved efficiently, then all problems in NP could also be solved efficiently. The subset sum problem is a common example.
Related Concepts
- Computational complexity theory — Classifying computational problems by difficulty and understanding the relationships between different problem classes.
- NP — A complexity class for decision problems where 'yes' answers can be verified quickly.
- NP-completeness — The hardest problems in NP, where checking a solution is fast, but finding it is generally hard.