Backtracking
Named by 4 essays across 3 fields — each of them below, with the objects they name alongside it.
A threshold nobody can place
Random three-literal clauses on n variables: below about 4.27 clauses a variable a formula can almost always be satisfied, above it almost never. The change is proved to be sharp and nobody has proved where it is. Counting solutions overshoots to 5.19, counting pairs of them fails outright, and every algorithm with a proof stops well short.
The fewest entries that fix a Latin square
Reveal six of the twenty-five entries of the cyclic Latin square of order five — three in the top left corner, three in the bottom right — and only one Latin square agrees with them; reveal any five and at least two do. John Nelder conjectured that a square of order n can never be pinned down by fewer than ⌊n²/4⌋ entries. A search over every set of cells confirms it for every square to order five, and finds that the more symmetric a square is, the fewer entries it takes.
The sizes at which a sentence can come true
Write a sentence about a relation and ask for which numbers of points some relation makes it true. "Every two points have exactly one common neighbour" comes true at every odd size and no even one, and every graph that satisfies it is a windmill of triangles. "Every two players are both beaten by some third" fails for every tournament of two to six players and holds from seven on. A search can settle one size at a time; only a proof settles all of them, and the two sentences need different kinds.
One random path down a search tree
Before running a search that may take a week, it is worth knowing whether it will take a week or a century. Donald Knuth's answer, from 1975, is to walk down the search tree once at random, multiply the numbers of choices met on the way, and add up the products: the result is, on average, exactly the size of the tree. On the eight-queens tree one path guesses 769 against a true 2,057 and twenty thousand paths average to within a tenth of a per cent. On a tree built to hide its bulk, the same unbiased estimate is almost always wrong by a factor of thousands.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchConjectureEigenvalueFirst momentGroupImportance samplingLatin squareLower boundMonotone propertyMonte CarloPhase transitionProbabilistic method