QED

Brian Hayes geeft een interessante opmerking in een artikel over de namen van complexiteitsklassen. Donald Knuth schrijft in een artikel:

I’m willing to give a prize of one live turkey to the first person who proves that P = NP.

Donald Knuth, “A Terminological Proposal”, SIGACT News, Vol. 6, No. 1 (1974)

Inderdaad, dit is het fameuze P = NP probleem waarvan een bewijs voor het Clay Mathematics Institute een miljoen dollar waard is. Knuth heeft echter wel een reputatie van zulke vreemde prijzen te geven. Wie een fout vindt in één van zijn boeken krijgt van hem bijvoorbeeld een check van 2,56 dollar, of 1 hexadecimale dollar. Weinig van deze checks worden echter geïnd, want ze worden door computernerds als trofeeën beschouwd. Ik heb de mijne nog ergens in een schuif liggen, en ik herinner me nog goed de opwinding toen ik als student computerwetenschappen een brief van Knuth kreeg omdat ik een fout in één van de oefeningen van zijn meesterwerk The Art of Computer Programming gevonden had. In een Slashdot-signatuur stond ooit zelfs:

Intelligence: Finding an error in a Knuth text.
Stupidity: Cashing that $2.56 check you got.