Anonymní čtenář píše: "V odpoledních hodinách dne 04.5.1971, v Somersetu Inn Stouffer v Shaker Heights, Ohio, Steve Cook představil své STOC papír prokazující, že splnitelnosti je NP-kompletní a Tautologie je NP-tvrdý. 'Věty naznačují, že tautologie je dobrým kandidátem na zajímavý soubor není v [P] a mám pocit, že se vyplatí věnovat značné úsilí snaze dokázat toto tvrzení potvrzují. Takový důkaz by byl zásadní průlom v teorii složitosti. ' Cook a tak formuloval to, co bylo brzy být volán P versus NP problém. Zbytek je historie. Zde je z roku 1971 STOC programu (tam bylo 143 účastníků), a co to posvátné místo vypadá dnes. "
Přečtěte si více o tomto příběhu na Slashdot.
Žádné komentáře:
Okomentovat