Choosing a structure

The knapsack table has $n W$ cells, and a capacity written in $\log_{2} W$ bits makes that exponential in the size of the input rather than polynomial.

That is not a defect of the method. Nobody knows a genuinely polynomial algorithm for 0/1 knapsack, and the same is true of a long list of problems that look no harder. This last lesson says what is known about that boundary, what to do when a problem sits on the wrong side of it, and then closes the course by turning seventeen lessons of structures into a procedure for picking one.

What "efficient" was taken to mean

The second lesson priced the growth hierarchy and treated polynomial as tractable and exponential as not. That convention deserves a defence, because $n^{100}$ is polynomial and ${1.0001}^{n}$ is exponential, and for any realistic $n$ the first is far worse.

The defence is twofold. Empirically, the polynomial algorithms that arise have small exponents, almost always 3 or less, and the exponential ones have bases of 2 or more. And structurally, polynomials are closed under addition, multiplication and composition, so a polynomial algorithm calling a polynomial subroutine polynomially often is still polynomial, which makes the class stable under the way algorithms are actually built. Exponentials are not.

The numbers make the boundary concrete. At $10^{12}$ operations per second, an $n^{3}$ algorithm handles $n = 1000$ in a millisecond and $n = 10^{6}$ in eleven days. A $2^{n}$ algorithm handles $n = 30$ in a millisecond, $n = 50$ in nineteen minutes, and $n = 100$ in $1.3 \times 10^{18}$ seconds, which is about three times the age of the universe.

Example. At $10^{12}$ operations per second, how large an input can a $2^{n}$ algorithm finish in one hour, and what does a machine a thousand times faster change?

One hour is $3.6 \times 10^{15}$ operations, and $\log_{2} (3.6 \times 10^{15}) = 51.7$ , so $n = 51$ . On a machine a thousand times faster the budget is $3.6 \times 10^{18}$ operations and $\log_{2}$ of that is 61.6, so $n = 61$ . A thousandfold improvement in hardware bought ten more elements, because a factor of 1000 is about ten doublings and each doubling is worth exactly one element.

Now you. Answer the same two questions for an $n^{3}$ algorithm.

Answer

$\sqrt[3]{3.6 \times 10^{15}} = 1.53 \times 10^{5}$ , so about 153,000 elements in an hour. A thousand times faster gives $\sqrt[3]{3.6 \times 10^{18}} = 1.53 \times 10^{6}$ , ten times as many. Hardware multiplies what a polynomial algorithm can reach and merely adds to what an exponential one can reach, which is the practical content of the distinction.

P is the class of decision problems solvable in time polynomial in the input length. Sorting, shortest paths, minimum spanning trees, edit distance, matching, linear programming: all in P, and everything in the course so far except the knapsack table is in it.

Checking against finding

Now the second class, and it rests on a distinction worth stating slowly.

Consider subset sum: given a set of integers and a target, is there a subset adding to exactly the target? Searching for one means examining up to $2^{n}$ subsets. But if somebody hands you a subset and claims it works, checking the claim takes $n$ additions and a comparison.

Example. From the set 267, 493, 869, 961, 1034, 1289, 1522, is there a subset summing to 2590? Compare the work of finding an answer with the work of checking one.

Finding it means considering $2^{7} = 128$ subsets. Checking the proposed subset 267, 493, 869, 961 means three additions: $267 + 493 = 760$ , $+ 869 = 1629$ , $+ 961 = 2590$ . Correct. With seven numbers the gap is unimpressive. With 100 numbers, checking is still 99 additions and searching is $1.27 \times 10^{30}$ subsets.

Now you. From 112, 348, 507, 683, 899, 1204, verify the claim that some subset sums to 1694, given the proposed subset 112, 683, 899.

Answer

$112 + 683 = 795$ , $+ 899 = 1694$ . Two additions confirm it. Note what the certificate does not do: it gives no help at all in deciding whether some subset sums to 1695, and no way to conclude that none does. A short certificate exists for a yes answer, and nothing here provides one for a no answer, which is the asymmetry the definition of NP is built on.

NP is the class of decision problems whose yes-instances have a certificate, of length polynomial in the input, verifiable in polynomial time. The name is "nondeterministic polynomial", not "non-polynomial", and the difference matters: every problem in P is in NP, since the solution can be recomputed instead of checked.

The open question is whether the reverse holds. Does the existence of a quickly checkable answer imply a quick way to find it? That is P versus NP, posed by Stephen Cook in 1971, one of the seven Clay Millennium Prize problems since 2000, and unanswered. Almost everyone expects P $\neq$ NP, and nobody can prove it.

Reduction, and the hardest problems in NP

The tool that organises this is reduction. Problem $A$ reduces to problem $B$ if any instance of $A$ can be transformed, in polynomial time, into an instance of $B$ with the same answer. A fast algorithm for $B$ then gives a fast algorithm for $A$ , so $B$ is at least as hard as $A$ .

A problem is NP-hard if every problem in NP reduces to it, and NP-complete if it is also in NP. An NP-complete problem is a hardest problem in NP: a polynomial algorithm for one would give a polynomial algorithm for all of them, and prove P $=$ NP.

That such a problem exists at all is the Cook-Levin theorem, proved independently by Cook in 1971 and Leonid Levin in 1973: boolean satisfiability, asking whether a logical formula can be made true, is NP-complete. The following year Richard Karp reduced satisfiability to 21 other problems, showing them NP-complete too, and the list has grown to thousands. Knapsack, subset sum, the travelling salesman decision problem, graph colouring, vertex cover, clique, bin packing, and scheduling with deadlines are all on it.

The practical value is that a reduction is a licence to stop searching. If a new problem is shown NP-complete, no polynomial algorithm for it will be found without settling a 50-year-old open question, so effort is better spent elsewhere.

What to do instead

NP-complete does not mean unsolvable, and treating it as a wall is the most common mistake made with this material. Real instances get solved constantly, by five distinct routes.

Solve it exactly, but cleverly. Exponential is not uniform. The travelling salesman by brute force over all tours is $Θ (n!)$ , hopeless at $n = 25$ where $25!$ is $1.6 \times 10^{25}$ . The Held-Karp dynamic programming algorithm from 1962, over subsets rather than tours, is $Θ (n^{2} 2^{n})$ : $2.1 \times 10^{10}$ operations at $n = 25$ , about twenty seconds. Still exponential, and still a change of what is reachable. Branch and bound goes much further: the Concorde solver proved an optimal tour through all 85,900 points of a circuit-board drilling instance in 2006.

Accept a bound on the error. An approximation algorithm runs in polynomial time and guarantees a result within a stated factor of optimal. For vertex cover, repeatedly picking both endpoints of any uncovered edge gives a cover at most twice the minimum, from three lines of code. For travelling salesman with distances obeying the triangle inequality, doubling a minimum spanning tree gives a factor of 2, and Christofides' 1976 refinement gives 1.5. Note that these guarantees need structure: for general travelling salesman with arbitrary distances, no constant-factor approximation exists unless P $=$ NP.

Give up the guarantee and measure instead. Local search, simulated annealing and genetic methods offer no bound at all and routinely land within a per cent or two of optimal on real instances. Modern SAT solvers, which cannot possibly be fast in the worst case, dispatch industrial formulas with millions of variables, because real formulas have structure that random ones do not.

Bound the part that is hard. Vertex cover is solvable in $O ({1.28}^{k} + k n)$ time for a cover of size $k$ , which is fast whenever $k$ is small however large the graph is. This is parameterised complexity: the exponential blow-up is confined to a parameter that is small in practice.

Or notice that the real instance is a special case. Graph colouring is NP-complete in general and easy on trees, on interval graphs and on planar graphs when four colours suffice. Knapsack's pseudo-polynomial table is entirely usable when $W$ is genuinely small, which for a physical bag it often is.

Choosing a structure

The course set out to make one decision reliably. Here is the procedure, and every step of it has been earned.

Start with the operations, not the data. Write down what will be asked of the collection and roughly how often. A structure is a set of trade-offs, and it can only be chosen against a workload. Every lesson here paid for one operation with another: hashing bought constant lookup with the loss of order, heaps bought a constant-time minimum by refusing every other query, linked lists bought constant insertion with the loss of indexing.

Then ask whether order is ever needed. If the only question is "is this exact key present", take a hash table: expected constant time, and nothing else comes close. If anything asks for a minimum, a maximum, a successor, a range, a rank, or an ordered listing, a hash table cannot answer it at any price and a balanced tree is the structure, at $O (\log n)$ for everything.

Then ask whether the ordering is needed in full. If the only ordered question is "what is the smallest", a heap gives it in constant time, updates in $\log n$ , and lives in a bare array. If the answer is needed once rather than continuously, sorting once at $Θ (n \log n)$ and then binary searching beats maintaining a tree.

Then ask what the data is. A sequence with positional access is an array, and the array's contiguity is worth more in practice than any operation count suggests. A queue or a stack is an array with a restricted interface. A hierarchy is a tree. A set of relationships is a graph, stored as adjacency lists unless the edge count approaches $V^{2}$ .

Then check the worst case, and ask who supplies the input. Expected constant time and average logarithmic height are statements about the distribution of the data. If the data comes from an untrusted source, or arrives sorted, those statements do not hold, and the answer is a randomised hash, a balanced tree rather than a plain one, or a hard fallback.

Then measure. Asymptotic classes settle which structure to reach for and say nothing about the factor of three between two implementations of the same class. Linked lists lose to arrays, quicksort beats mergesort, and B-trees beat binary trees, all for reasons no operation count can see.

Example. A service holds 50 million session records, each keyed by a 32-character token, and must look a session up by token on every request while deleting all expired sessions once a minute. What structures?

Lookup by exact key with no ordered query at all is a hash table, keyed by token, with the load factor held below about 0.75 and a randomised hash because the tokens come in over the network. Expiry is a different question with a different answer: it repeatedly asks for the earliest expiry time and nothing else, which is a min-heap keyed by expiry, so the sweep pops until the root is in the future rather than scanning 50 million records. Two structures over the same objects, cross-referenced, each chosen for one query. That is the normal outcome rather than a compromise.

Now you. A leaderboard for 10 million players must report a player's current rank, list the top 100, and update a score. What structures?

Answer

Rank is an ordered query, so a hash table is out on its own and a heap cannot answer it either, since a heap knows only its minimum. Use a balanced binary search tree keyed by score, with each node additionally storing the number of nodes in its subtree; that count turns rank into a single root-to-leaf walk at $O (\log n)$ , and the top 100 into a reverse in-order walk that stops after 100. Add a hash table from player identifier to tree node so that an update finds the node in constant time rather than searching for it by score. This is what Redis calls a sorted set, and it is implemented as exactly this pairing, with a skip list standing in for the balanced tree.

What a finisher has

Cost is measured against input size under a stated model, and asymptotic notation compares algorithms while hiding constants that sometimes matter more. Sorting is $Θ (n \log n)$ and provably no better by comparison, and linear if the keys have structure to exploit. Lookup is constant with hashing, logarithmic with order, and the choice between them is a question about which queries will be asked. Trees stay short by rotation or by widening, graphs are traversed in $Θ (V + E)$ and searched by weight with a heap. Greed needs an exchange argument before it can be believed, dynamic programming replaces the choice it cannot make with a table, and some problems have neither and are solved anyway by approximation, by parameterisation, or by exploiting the shape of the instance that actually arrived.

None of that is a catalogue to recall. It is a way of asking what a program costs, and then choosing the structure that makes the expensive question cheap, which is what the whole subject amounts to.