JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Decision Problems, P, and NP

Before we can ask whether a problem is hard, we have to agree on what counts as a problem and what counts as fast. This guide builds those two ground rules — yes/no problems and polynomial time — and then meets the most consequential set of problems in computing: NP, where finding a solution looks impossibly slow but checking one is easy.

From "find the answer" to "yes or no"

Every algorithm you have climbed past so far solved an optimization or search problem: return the shortest path, return the longest common subsequence, return a maximum matching. To build a clean theory of hardness, we shrink that ambition on purpose. A decision problem is one whose answer is a single bit — yes or no. Not "what is the shortest tour?" but "is there a tour of length at most 100?". Not "how many vertices cover all edges?" but "is there a vertex cover of size at most k?". Stripping the answer down to one bit is what makes problems comparable to each other, and comparison is the whole game in this rung.

It feels like a loss, but almost nothing is thrown away. Given a fast yes/no oracle for "is there a tour of length at most B?", you can binary-search on B to find the optimal length, then peel off one edge at a time and re-ask to reconstruct an actual shortest tour — all with only a polynomial number of extra calls. So the decision version is essentially as hard as the search version, never harder; if the easy-looking yes/no question turns out to be intractable, the richer optimization question certainly is too. That is exactly the implication we want: prove the simplest form hard, and everything built on it inherits the hardness.

One more piece of bookkeeping before we can measure anything. The size of an input is the number of bits it takes to write down — its encoding. A graph on n vertices, a list of k integers, a boolean formula: each gets spelled out in bits, and an algorithm's running time is judged against that bit-length. This sounds pedantic, but it bites in one famous place. An integer N is written in only about log N bits, so an algorithm that loops N times is exponential in the input size, not linear — a trap we will meet again when subset-sum and partition look deceptively easy.

P: the problems we call efficient

Now we draw the first line. P is the class of decision problems that some algorithm solves in polynomial time — time O(n^c) for a fixed constant c, where n is the input size in bits. "Is this number a multiple of three?", "is there a path from s to t?", "can these intervals all be scheduled?" — these have algorithms running in O(n), O(n + m), O(n log n), and so on, so they all sit comfortably in P. The whole earlier ladder you climbed — sorting, shortest paths, dynamic programming, flow — was, viewed from up here, a tour of P.

Why pick polynomial as the dividing line, rather than, say, "under a billion steps"? Two honest reasons. First, robustness: the class P does not change if you swap one reasonable machine model for another, or measure bits versus words, because one polynomial composed with another is still a polynomial. That stability is rare and precious — it means P is a property of the problem, not of your laptop. Second, the gap it captures is enormous in practice: as n grows, an n^3 algorithm stays usable while a 2^n one detonates. At n = 60, n^3 is a couple hundred thousand steps; 2^n is more than a billion billion.

NP: easy to check, maybe hard to find

Some yes/no questions resist every polynomial algorithm we have ever tried, yet share one suggestive feature: if the answer is yes, there is a short piece of evidence that makes the yes obvious. "Is this 10000-variable formula satisfiable?" may stump us for the lifetime of the universe — but hand me a satisfying assignment and I will plug it in and confirm "yes" in seconds. "Does this graph have a Hamiltonian cycle?" is brutal to decide, yet a proposed cycle is trivial to walk and verify. The asymmetry between finding and checking is the heart of the next class.

NP is the class of decision problems where every yes instance has a short certificate — a proposed solution of polynomial length — that a polynomial-time verifier can check. Pin down the precise rules, because this definition is exact: for a yes-instance there must exist a certificate the verifier accepts; for a no-instance the verifier must reject every claimed certificate, so no string can fool it. The verifier is the worker; the certificate is a hint whispered to it. NP is exactly the set of problems where a good hint turns a hard question into an easy check.

A worked example: SAT in NP

Let us actually verify, step by step, that SAT — "does this boolean formula have an assignment that makes it true?" — really belongs to NP. The recipe for proving any problem is in NP is always the same shape: name a certificate, bound its length, describe the verifier, and check the verifier runs in polynomial time and is never fooled. SAT is the cleanest possible illustration.

  1. Certificate: a truth assignment — one bit (true/false) for each of the formula's variables. If the formula has v variables, the certificate is just v bits, which is at most the size of the formula itself, so it is comfortably polynomial in the input length.
  2. Verifier: substitute those truth values into the formula and evaluate it. Walk the formula once, computing each AND, OR and NOT from its inputs. This is a single pass over the formula, so it runs in time linear in the input size — well within polynomial time.
  3. Accept iff the formula evaluates to true. Now check the two halves of the NP definition: if the formula is satisfiable, some assignment makes it true and the verifier accepts that certificate (a yes-instance HAS a good certificate). If it is unsatisfiable, every assignment evaluates to false, so the verifier rejects no matter which certificate is offered (a no-instance fools no one).

That four-line argument is a complete, rigorous proof that SAT is in NP — and notice what it never did. It never found a satisfying assignment; it only checked one it was handed. Whether some clever algorithm can find the assignment in polynomial time is a wide-open question, and SAT will turn out to be the very problem that the Cook-Levin theorem pins as the hardest in all of NP. For now, the lesson is the method: membership in NP is proved by exhibiting a short hint and a fast checker, not by solving the problem.

P inside NP, and the question worth a million dollars

First, a fact that surprises people: every problem in P is also in NP, so P is a subset of NP. The argument is a one-liner. If you can solve a problem in polynomial time, you do not even need the hint — let the certificate be empty, and let the verifier simply ignore it and run your polynomial-time solver. Easy to solve implies easy to check, trivially. So NP contains all the tractable problems and, seemingly, a pile of intractable-looking ones like SAT and Hamiltonian cycle on top.

P  =  { decision problems solvable  in poly time }
NP =  { decision problems verifiable in poly time, given a short certificate }

          P  is a subset of  NP        (proven, easy)
          P  =  NP   ?                  (OPEN -- nobody knows)
The known containment, and the famous open gap between the two classes.

The trillion-dollar question is whether that containment is strict. Could it be that checking-easy already implies finding-easy — that every problem in NP is secretly in P, and the apparent hardness of SAT is just a failure of human cleverness? That is the P versus NP problem, and it is genuinely open: no one has found a polynomial algorithm for SAT, and no one has proved that none exists. Be scrupulous about what "this problem is hard" can therefore mean — for the problems we will study, it means "no polynomial-time algorithm is known," which is a statement about the current state of knowledge, not a proof of impossibility. Mistaking the second for the first is the deepest trap in this whole subject.

So this is where the rung is heading. We have two classes, P inside NP, and a haunting gap between them that nobody can close. The thrilling discovery — the subject of the guides that follow — is that vast numbers of natural NP problems are equivalent: solve any one of them in polynomial time and you solve them all, collapsing P and NP together. The tool that links them is the polynomial-time reduction, and the crown jewels they all reduce to are the NP-complete problems. Decision problems, P, and NP are the three definitions on which that entire structure is built.