Stiven Kuk
Stiven Artur Kuk (engl. Stephen Arthur Cook rođen 1939, Bufalo, Njujork) je poznati informatičar.
Stiven Kuk | |
---|---|
Lični podaci | |
Datum rođenja | 14. decembar 1939. |
Mesto rođenja | Bufalo (Njujork), SAD |
Obrazovanje | Univerzitet Harvard, Univerzitet Mičigena |
Zvanični veb-sajt | |
www |
Kuk je formalizovao pojam NP-kompletnosti u svom čuvenom radu iz 1971, Kompleksnost procedura za dokazivanje teorema, koji je takođe sadržao Kukovu teoremu, dokaz da je SAT problem NP-kompletan. Ovaj rad je ostavio nerešeno najveće trenutno pitanje u terijskom računarstvu - da li su klase složenosti P i NP ekvivalentne.
Kuk je dobio Tjuringovu nagradu 1982. za ovo otkriće. Obrazloženje za nagradu glasi:
Za njegovo unapređivanje našeg razumevanja složenosti izračunavanja na značajan i dubok način. Njegov rad, Kompleksnost procedura za dokazivanje teorema, predstavljen 1971. na ACM SIGACT simpozijumu , je postavio osnove za teoriju NP-kompletnosti. Istraživanje granica i prirode klase NP-kompletnih problema, koje je usledilo je predstavljalo jednu od najaktivnijih i najvažnijih istraživačkih aktivnosti u računarstvu tokom protekle decenije.
Kuk je diplomirao 1961. na Univerzitetu u Mičigenu. Magistrirao je na Harvardu, 1962. a doktorirao 1966. Od 1966. do 1970. je radio na Berkliju. Prešao je na Univerzitet u Torontu 1970.
Spoljašnje veze
uredi