NP-hard
Named by 4 essays across 3 fields — each of them below, with the objects they name alongside it.
The fewest swaps to a winner
When no candidate beats every other head to head, Charles Dodgson proposed in 1876 to elect the one that is closest to doing so — the candidate that the fewest swaps of neighbouring names on the ballots would turn into a winner of every contest. The rule is easy to state and hard to compute: the count needs a search, and deciding the winner is provably among the hardest problems of its kind. A much simpler count, the votes still to be won, usually agrees, more often the larger the electorate.
There is a relation such that
A graph can be coloured with three colours exactly when there are three sets of its points such that every point lies in one and no edge joins two points of the same set. The sets are a guess; once guessed, the rest is a list of simple checks. Ronald Fagin proved in 1974 that this shape of sentence — 'there exist relations such that' followed by first-order conditions — describes exactly the problems whose solutions can be checked quickly, the class called NP. The central question of computer science is therefore also a question about what sentences can say.
What a junction can save
Join a set of towns by roads that may meet only at towns, and the shortest such network is easy to find. Allow junctions anywhere and the network gets shorter — but never, it is conjectured, by more than 13.4%, the saving the Fermat point makes on an equilateral triangle. Computed exactly on 1,304 random sets of up to seven towns, the average saving is about 3%. An adversarial search drives it down to the bound and no further, and a hexagon with its centre attains it exactly. The proof of the bound that was accepted for twenty years has a gap.
The order that keeps elimination narrow
Eliminating letters one at a time costs whatever the widest step costs, and the least width any order can achieve is the treewidth of the formula's graph. Finding it exactly is NP-hard, but a search over sets of letters instead of sequences finds it for small graphs, and a greedy rule that adds the fewest new edges finds it on 566 of 600 random graphs and misses by more than one only once. On Tseitin's 6 × 6 grid that rule forms twenty-four times fewer resolvents than sweeping row by row. What it cannot do is prove that its order is the best.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchApproximationBorda countCondorcet winnerConjectureDecompositionEhrenfeucht fraisse gameEquilateral triangleGraphGraph colouringGraph minorGreedy algorithm