Anonimowy czytelnik pisze: "W godzinach popołudniowych z dnia 4 maja 1971 r., w Inn Somerset Stouffer w Shaker Heights, Ohio, Steve Cook przedstawił papieru STOC udowodnienia, że Spełnialność jest NP-zupełny i tautologii jest NP-trudny. Twierdzenia wynika, że Tautologia jest dobrym kandydatem na ciekawe nie jest ustawiony w [P] i czuję, że warto poświęcić znacznego wysiłku próbując udowodnić to przypuszczenie. Taki dowód byłby to przełom w teorii złożoności. I tak Cook sformułował, co było tylko o nazwie P versus problem NP. Reszta jest historią. Oto 1971 STOC Program (było 143 uczestników) i co, że święta ziemia wygląda jak dzisiaj. "
Czytaj więcej tej historii w Slashdot.
Brak komentarzy:
Prześlij komentarz