Anonimni čitatelj piše: "U poslijepodnevnim satima 4. svibnja 1971, u Stouffer's Somerset Inn u Shaker Heights, Ohio, Steve Cook je predstavio svoj stoc radu se dokazuje da zadovoljivosti je NP-potpun i tautologija je NP-težak. 'Teoremi upućuju na to da tautologija je dobar kandidat za zanimljiv set nije u [P] i mislim da je vrijedan trošenja znatne napore pokušavaju dokazati ovu slutnju. Takav dokaz bi bio veliki pomak u teoriji složenosti. " I tako Cook formulirao ono što je uskoro se zove P versus NP problem. Ostalo je povijest. Evo 1971 stoc programa (bilo je 143 sudionika) i što to sveto tlo izgleda kao i danas. "
Pročitajte više ove priče na Slashdot.
Nema komentara:
Objavi komentar