Decision problems, satisfiability and reductions

A decision problem is a question with a yes or no answer for each input: is this number prime, does this graph have a Hamilton cycle, is this formula satisfiable. Framing problems this way lets us compare their difficulty precisely. An algorithm runs in polynomial time if its number of steps is \( O(n^c) \) for some constant \( c \), where \( n \) is the length of the input. The class P is the set of decision problems solvable in polynomial time, and it is the standard formal meaning of "efficiently solvable".

Many problems have a different feature: a yes answer can be checked quickly given the right evidence. A proposed Hamilton cycle can be verified by walking round it, and a proposed 3-colouring by looking at each edge. The class NP is the set of decision problems for which every yes instance has a certificate of polynomial length that a polynomial-time verifier accepts, while for a no instance the verifier rejects every proposed certificate. Every problem in P is in NP (the verifier can ignore the certificate and solve the problem). Brute force solves any NP problem by trying all certificates, but there can be exponentially many of them.

The central NP problem is Boolean satisfiability (SAT): given a formula, is there an assignment of truth values that makes it true? A formula in conjunctive normal form is an AND of clauses, each an OR of variables or their negations. The example \( (p \lor q) \land (\lnot p \lor r) \land (\lnot q \lor \lnot r) \) is satisfiable (take \( p \) true, \( r \) true, \( q \) false), and the truth table finds every satisfying row. With \( n \) variables the table has \( 2^n \) rows: for 30 variables, over a billion. 2-SAT, with two literals per clause, can be solved in linear time using a graph of implications; 3-SAT has no known polynomial algorithm.

A reduction from problem \( A \) to problem \( B \) is a polynomial-time transformation of each instance of \( A \) into an instance of \( B \) with the same answer. It shows that \( B \) is at least as hard as \( A \): a fast algorithm for \( B \) would give a fast algorithm for \( A \). The direction matters, and it is the most common error: to show a new problem is hard, reduce a known hard problem to it. A small example: a set \( S \) of vertices touches every edge (a vertex cover) exactly when its complement contains no edge (an independent set), so a graph on \( n \) vertices has a vertex cover of size \( k \) if and only if it has an independent set of size \( n - k \), and each problem reduces to the other. A problem to which every NP problem reduces is NP-hard, and an NP-hard problem that is itself in NP is NP-complete. The Cook-Levin theorem (1971) shows SAT is NP-complete, and chains of reductions from it establish 3-SAT, 3-colouring, Hamilton cycle, vertex cover and thousands more.

Whether P = NP is one of the great open questions of mathematics, and one of the Clay Millennium Prize Problems. A polynomial-time algorithm for any single NP-complete problem would give one for every problem in NP; nobody has found such an algorithm, and nobody has proved that none exists. Most researchers expect P and NP to be different, but that is a belief, not a theorem: an NP-completeness proof shows a problem is as hard as any in NP, and it is only this open question that stops it from also proving that no fast algorithm exists.

Picture it: finding a satisfying assignment is searching a huge maze; checking one is following a path someone hands you. NP is the class of mazes where every exit has a short path that can be checked, and a reduction is a way of redrawing one maze as another.

Think it: NP-completeness is a statement about the worst case of a general problem, not about every instance. SAT solvers routinely handle industrial formulas with millions of variables, and special cases (2-SAT, colouring with 2 colours, trees) are easy. Proving a problem NP-complete tells you to look for special structure, approximations or good heuristics rather than a fast exact algorithm for every input.