Intermediate · Research
NP
Visual diagram · (in preparation) · Math · (in preparation) · Worked example · 3 difficulty levels.
TL;DR. A complexity class for decision problems where 'yes' answers can be verified quickly.
Technical Definition
A complexity class for decision problems where 'yes' answers can be verified quickly.
How it works
NP, or nondeterministic polynomial time, is a class in computational complexity theory that includes decision problems where a potential solution can be verified in polynomial time. If a problem instance has a 'yes' answer, a proof of this can be checked efficiently.
Related Concepts
- Computational complexity theory — Classifying computational problems by difficulty and understanding the relationships between different problem classes.
- NP-completeness — The hardest problems in NP, where checking a solution is fast, but finding it is generally hard.