Un lecteur anonyme écrit: «Dans l'après-midi du 4 mai 1971, dans le Stouffer's Somerset Inn à Shaker Heights, Ohio, Steve Cook a présenté son document STOC prouver que la satisfiabilité est NP-complet et tautologie est NP-difficile. 'Les théorèmes suggèrent que La tautologie est un bon candidat pour un ensemble intéressant de ne pas en [P] et je pense qu'il est l'effort de la peine de dépenser beaucoup d'essayer de prouver cette conjecture. Une telle preuve serait une avancée majeure dans la théorie de la complexité. " Et c'est ainsi que Cook a formulé ce qui allait bientôt être appelé le P versus NP problème. Le reste est histoire. Voici le programme STOC 1971 (il y avait 143 participants) et ce que cela ressemble à une terre sacrée aujourd'hui. "
Lire la suite de cette histoire à Slashdot.
Aucun commentaire:
Enregistrer un commentaire