Concept

NP-hard

The property of a problem that every problem whose solutions can be checked quickly reduces to it in polynomial time. A fast algorithm for any one such problem would give fast algorithms for all of them, and none is known.

Named by 2 essays across 2 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.

applied · Voting rules

Three-colourability as a sentence: there exist three sets such that …. Petersen graph coloured with three colours; witness sets R = {0,2,6}, G = {1,3,5,9}, B = {4,7,8}; all 25 first-order checks pass.

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.

logic · Quantifiers

Named alongside it

The objects these essays reach for when they reach for this one.

Exhaustive search Approximation Borda count Condorcet winner Ehrenfeucht fraisse game Graph colouring Majority rule Quantifier Second-order logic Voting rule

All concepts