A decision problem is a computational question where each input requires a simple “yes” or “no” answer. Examples include checking if a number is prime or if one number divides another evenly. Formally, a decision problem is often described as the set of inputs for which the answer is “yes.”
A decision problem is decidable if there exists an algorithm that always halts and correctly returns “yes” or “no” for every possible input. If no such algorithm can exist, the problem is undecidable—for example, the halting problem.
P (Polynomial time): This is the class of decision problems that can be solved efficiently—meaning a deterministic algorithm can solve them in time bounded by a polynomial in the input size.
NP (Nondeterministic Polynomial time): This is the class of decision problems where, if the correct answer is “yes,” there exists a proof (certificate) that can be verified quickly (in polynomial time) by a deterministic algorithm. Equivalently, a nondeterministic machine can solve them in polynomial time.
Every problem in P is also in NP, since being able to solve a problem efficiently implies you can also verify solutions efficiently. But the reverse question—whether NP problems can all be solved efficiently (P = NP)—is still unknown.
The P vs NP problem asks: If you can quickly verify a proposed solution (NP), can you also quickly find the solution itself (P)?
In other words, is P equal to NP, or is NP strictly larger? Most experts believe P ≠ NP, suggesting there exist problems that are easy to check but very hard to solve.
Solving the P vs NP problem earns a $1 million prize from the Clay Mathematics Institute. More importantly, proving P = NP could transform cryptography, artificial intelligence, and automated reasoning. Even proving P ≠ NP would reshape our understanding of computational boundaries.