When no fast algorithm is known

A circuit has thirty on-off switches and one bulb. Each switch controls a wire, and the wires meet at gates, the small components that combine signals. An AND gate lights its output only when both inputs are live, an OR gate when at least one is, and a NOT gate inverts its input.

To decide whether some setting of the switches lights the bulb, you can try every setting, and there are 1,073,741,824 of them. At a billion checks per second the search takes about a second, which sounds bearable until the circuit grows: with sixty switches the count is 1,152,921,504,606,846,976 and the same search takes about 36 years. Nothing about the circuit changed except the number of switches. !P holds the problems a polynomial procedure solves; NP holds those whose candidate answer can be checked in polynomial time, and the circuit problem sits there. That no fast procedure is known, that the problem is NP-hard, and that it is intractable are three different claims. Only the third is a bound on every procedure. Status: schematic.

Checking one proposed setting takes a single pass through the gates. That pass costs time proportional to the number of gates, so a yes answer is cheap to verify [S:1:398]. Finding a setting that lights the bulb seems to require looking at the settings one by one, and nobody has found a method that does better in general.

Those two facts carry the standard vocabulary. A decision problem is one whose answer is yes or no. The yes answer to this problem is cheap to check, which puts it in NP. NP is the class of decision problems whose yes answers a candidate can check in polynomial time, meaning time bounded by a polynomial in the input size [S:1:399].

P is the class that can actually be solved in polynomial time, and nobody knows whether the two classes are the same [S:1:400]. A problem is called hard when no polynomial-time procedure for it is known, which is a claim about the current state of knowledge rather than a theorem about what must be true forever.

A problem is NP-hard when a polynomial-time procedure for it would yield one for every problem in NP. The circuit problem is NP-hard, because every problem in NP can be turned into a circuit of polynomial size, so a fast procedure for the circuit would give one for all of them [S:1:402]. That is a conditional statement, and it transfers hardness rather than asserting that no fast procedure exists. An NP-hard problem with a fast procedure would prove that P and NP are the same class, which nobody has done.

Worked example. Compare an exponential search with a cubic procedure as the input grows.

At ten switches the two counts are almost equal, and a stopwatch could not separate them. At twenty the exponential count is a hundred times larger, and by sixty the ratio has thirteen digits. The cubic column is not a fast procedure in any absolute sense; it is merely on a rung where doubling the input multiplies the work by eight instead of squaring it.

$$C(n)=2^n$$

The exhaustive search performs one step per candidate setting, and the count of settings doubles each time one switch is added.

Three sentences get conflated in practice, and keeping them apart is most of the skill. The first is that no polynomial-time algorithm for this problem is known, which is a dated fact about the literature and would be settled by a single new procedure. The second is that the problem is NP-hard, which is a conditional theorem about the consequences of such a procedure. The third is that the problem is intractable, which is an unconditional lower bound and is proved for very few problems.

Only the third sentence earns the word intractable, and most claims that use it are the first sentence wearing the second sentence's clothes. A claim that a problem is intractable is therefore a claim about every possible procedure, and it is much stronger than a report that the current one is slow. This matters whenever a problem is called hard, because the practical response depends on which of the three sentences is true. A problem that is merely unsolved may yield to a better method, while a problem with a proved lower bound will not.

The classification has two limits that matter. It is a statement about the worst case over all instances, so it says nothing about the instance in front of you. Solvers find satisfying assignments even for formulas with millions of variables, although it is hard to predict which formulas are amenable [S:5:64]. A formula is a statement built from variables joined by AND, OR and NOT. A satisfying assignment is a choice of true or false for each variable that makes the statement true, and amenable here means that the solver finishes quickly on it.

The classification is also asymptotic, so it says nothing about the constants at the sizes you actually meet, and a procedure with a bad polynomial can lose to an exponential one on small inputs. What the classification does give you is a warning: when a problem is NP-hard, the search for a fast general procedure is a search for a proof that P equals NP.

The formal statement. Fix a finite alphabet and a language, which is a set of strings. The class $\mathrm{P}$ is the set of languages that a deterministic Turing machine decides in time polynomial in the input length. The class $\mathrm{NP}$ is the set that a nondeterministic machine decides in polynomial time, which is the same as the set of languages where every yes instance has a certificate that a deterministic machine checks in polynomial time [S:1:399]. A problem is NP-hard when a polynomial-time procedure for it would give one for every problem in NP, and NP-complete when it is also in NP [S:1:401]. The Cook–Levin theorem says that circuit satisfiability is NP-hard [S:1:402].

The derivation. The definition is robust because the machine model is not. A word-RAM program that runs in $T(n)$ steps is simulated by a single-tape Turing machine in $O(T(n{)}^4)$ steps [S:1:402]. The exponent is a constant, so a polynomial becomes a polynomial. That lemma is the step which turns $\mathrm{P}$ from a fact about one machine into a class of problems. The proof of the simulation is omitted here, and it encodes the tape and the program counter of the random-access machine as blocks of the Turing tape.

The edge case. Input size is measured in bits, not in magnitude. Partition has a procedure that runs in $O(nM)$ time, where $M$ is the sum of the absolute values of the numbers [S:1:433]. That is polynomial in $M$ and exponential in the number of bits needed to write $M$, so it does not put Partition in $\mathrm{P}$ and does not prove that $\mathrm{P}=\mathrm{NP}$. Every polynomial claim is a claim about an encoding.

A second edge. Hardness is a worst-case statement over instances. The theorem says that some instance family defeats every polynomial procedure. It does not say that a particular instance is slow, and a solver that dispatches an easy instance quickly is consistent with the definition.

What the core hid. The core named the worst case and the conditional reading of NP-hardness, so it hid neither. What it did not give is the model-independence lemma that makes $\mathrm{P}$ a class of problems [S:1:402], and the formal definition of NP-hardness as a reduction from every problem in NP [S:1:401].

Where the ladder breaks. Easy and hard suggest two rungs. There is an infinite sequence of classes, and the strongest separation proved is a three-step gap [S:1:432]. Calling a problem hard is therefore a statement about one rung of a ladder whose neighbouring rungs are not known to differ.

Original sources. Polynomial time as the definition of efficient was formalized independently by Cobham in 1965, Edmonds in 1965, and Rabin in 1966, with earlier notions considered by Gödel, Nash and von Neumann [S:1:399]. Cook published the hardness of circuit satisfiability in 1971, and Levin reached it independently in 1973 [S:1:401]. The theorem that circuit satisfiability is NP-hard is the Cook–Levin theorem [S:1:402].

An open question. Whether $\mathrm{P}=\mathrm{NP}$ is open, and the text calls it the most important unanswered question in theoretical computer science [S:1:400]. Evidence that would settle it: a polynomial-time procedure for any NP-complete problem, which would collapse the classes, or a proof that no such procedure exists. Barrier results show that several whole families of proof cannot settle it, which is why the question has stayed open [S:1:400]. This is also why NP-hardness is stated as a conditional: it transfers difficulty from one problem to another without proving a single lower bound [S:1:401].

A frontier result. The same definitions decide when a learning problem is efficient. Shalev-Shwartz and Ben-David define the runtime of a learner as a function of accuracy and confidence, and show that hardness of implementing empirical risk minimisation does not imply hardness of learning [S:79:101]. Their example is exact: with a hypothesis class of size $2^n$ the sample complexity stays polynomial while exhaustive search grows exponentially [S:79:103]. That is 5.6 applied to a model class rather than to a circuit.

What to read next. Read chapter 12 of Erickson for the formal definitions, the reduction from CircuitSat to 3Sat, and the list of NP-complete problems [S:1:401]. Read section 8.1 of Shalev-Shwartz and Ben-David for the learning version of the same argument [S:79:101]. Then read the closing section of Erickson for the hierarchy above NP [S:1:432].