Decision Problem
A decision problem is a question with only a “yes” or “no” answer. Instead of producing a complete object or list, it asks whether a condition holds. For example, “Does this graph contain a path shorter than k?” is a decision problem because the answer can only be yes or no.
Decidable Problems
A decision problem is decidable if there is an algorithm that always halts and correctly answers yes or no for every possible input. If no such algorithm exists, the problem is undecidable. Decidability means we can mechanically solve the problem for all valid inputs in a finite amount of time.
Class P
Class P is the collection of decision problems that can be solved efficiently by an algorithm whose running time grows at most as some fixed power of the input size. Problems in P are often thought of as “tractable” or “feasible” for computers.
Class NP
Class NP is the collection of decision problems where, if the answer is “yes,” there is some certificate or witness that can be verified efficiently. This does not necessarily mean we can find the solution efficiently, only that we can check it quickly once we have it.
P versus NP
The P versus NP question asks whether every problem whose solutions can be verified quickly can also be solved quickly. In other words, if it’s easy to check a solution, is it also easy to find it? This is one of the biggest open questions in computer science.
If You Solve It
The Clay Mathematics Institute offers a one million dollar prize for a correct solution to the P versus NP problem. Beyond the money, such a discovery would have huge implications for cryptography, optimization, and computing as a whole.