Stephen Cook

Stephen Cook Immagine in Infobox. Stephen Cook Biografia
Nascita 14 dicembre 1939
Buffalo
Nome di nascita Stephen arthur cook
Nazionalità Canadese
americano
Formazione Università di Harvard
University of Michigan
Attività Informatico , professore universitario , matematico
Bambino Gordon Cook ( dentro )
Altre informazioni
Lavorato per Università di Toronto , Università della California a Berkeley
Campo Informatica
Membro di Association for Computing Machinery
American Academy of Arts and
Sciences Accademia delle scienze di Göttingen
Royal Society of Canada (1984)
Accademia americana delle scienze (1985)
Royal Society (1998)
Supervisore Wang hao
Sito web www.cs.toronto.edu/~sacook
Premi Premio Turing (1982)

Stephen Arthur Cook (nato nel 1939 a Buffalo, nello Stato di New York ) è uno scienziato informatico e matematico canadese-americano che ha dato diversi importanti contributi alla teoria della complessità . Attualmente è professore all'Università di Toronto , al Dipartimento di Informatica e al Dipartimento di Matematica.

Ha ricevuto il Premio Turing nel 1982.

Biografia

Cook ottiene un diploma nel 1961 Bachelor presso l' Università del Michigan e un master e un dottorato di ricerca presso l'Università di Harvard rispettivamente nel 1962 e nel 1966. Nel 1966 è entrato a far parte del dipartimento di matematica presso l' Università della California, a Berkeley, come assistente professore. Tuttavia, il suo incarico non è stato rinnovato nel 1970. Cook è poi entrato all'Università di Toronto come assistente professore, prima di ottenere il titolo di professore nel 1975, poi professore universitario nel 1985.

Era il supervisore della tesi di Walter Savitch .

Lavori

Stephen Cook ha formalizzato in particolare la nozione di NP-completezza . È autore di The Complexity of Theorem-Proving Procedures , in cui ha stabilito nel 1971 che il problema SAT è NP-completo . Questo teorema, da allora chiamato teorema di Cook , è fondamentale nella teoria della complessità e costituisce il punto di partenza della ricerca sul problema P = NP .

È uno dei fondatori del campo della complessità delle prove .

Premi

Riferimenti

  1. (it) “  Stephen Cook  ” , sul il sito Mathematics Genealogy Project
  2. (in) Stephen A. Cook , "The Complexity of Theorem Proving Procedures," in Conference Record of Third Annual ACM Symposium on Theory of Computing (STOC) ,1971, 151-158  p. ( leggi online )
  3. Paul Beame e Toniann Pitassi , "  Complessità della prova proposizionale: passato, presente e futuro  ", Bollettino della European Association for Theoretical Computer Science , n .  65, 1998, p.  66-89.
  4. "  AM TURING AWARD: Stephen A. Cook  " , su ACM .

link esterno