Cook, Stephen Arthur

Stephen Arthur Cook ( född 14  december 1939 , Buffalo , USA ) är en amerikansk datavetare. Berömd för sitt arbete med teorin om beräkningskomplexitet , vinnare av Turing Award .

I sitt arbete "The Complexity of Theorem Proving Procedures" [1] bevisade Cook att tillfredsställbarhetsproblemet för booleska formler är NP-komplett . Således tog han upp frågan om jämlikheten mellan komplexitetsklasserna P och NP , en av de svåraste frågorna inom teorin om datorsystem, som det fortfarande inte finns något svar på.

Medlem av Royal Society of Canada (1984), US National Academy of Sciences (1985) [2] , Royal Society of London (1998) [3] .

Biografi

Cook fick sin kandidatexamen från University of Michigan 1961 . Ett år senare tog han sin Master of Science-examen från Harvard , där han tog sin doktorsexamen 1966 . Fram till 1970 arbetade han som biträdande  professor i matematik vid Berkeley , där han aldrig fick status som fast anställd. Richard Karp , 1985 års Turing Award-vinnare , har detta att säga

Det kommer för alltid att förbli vårt fel att vi inte kunde övertala den matematiska fakulteten att ge honom denna status.

Denna ära tilldelades honom av University of Toronto , genom att utse Stephen Cook till professor 1975 .

Utmärkelser

• 1982  - Turing Award "För de betydande framsteg han har gjort när det gäller att förstå datorernas komplexitet. Hans arbete lade grunden för teorin om NP-fullständighet. Studiet av egenskaperna och gränserna för denna klass har blivit en av de viktigaste riktningarna i teorin om datorsystem under de senaste tio åren. [5  ]
• 1999  - CRM-Fields-PIMS-pris
• 2012  - Kanadensiske Gerhard Herzberg guldmedalj
• 2015  - BBVA Foundation Frontiers of Knowledge Awards "För hans viktiga roll i att definiera vad datorer kan och inte effektivt kan lösa. Hans arbete har haft en enorm inverkan på alla områden där komplexa beräkningar är kritiska." [6  ]

Se även

• Cooks teorem

Anteckningar

1. ↑ "The Complexity of Theorem Proving Procedures" Arkiverad 7 juli 2007 på Wayback Machine 
2. ↑ Cook, Stephen Arthur på US National Academy of Sciences  webbplats
3. ↑ Stephen Cook Arkiverad 31 augusti 2019 på Wayback Machine 
4. ↑ "A Personal View of Computer Science at Berkeley" Arkiverad 4 mars 2016 på Wayback Machine Richard Karp 30-årsjubileum av Berkeley Computer Science Department 
5. ↑ ACM Award Citation / Stephen A Cook  (länk ej tillgänglig)
6. ↑ BBVA Foundation Frontiers of Knowledge Award går till Stephen Cook för att ha fastställt att vissa problem inte lämpar sig för effektivt beräkningsbara lösningar | Virtual-S... (inte tillgänglig länk) . Datum för åtkomst: 19 januari 2016. Arkiverad från originalet 22 februari 2019. (obestämd) 

Länkar

• Stephen Cooks webbplats vid University of  Toronto
• "Stephen Cook" på NSERC-  webbplatsen

Tematiska platser	Google Scholar Matematisk släktforskning ORCID ResearchGate Scopus zbMATH Öppna
Ordböcker och uppslagsverk	Britannica (online)
I bibliografiska kataloger GND : 140808973 ISNI : 0000 0000 8220 6950 J9U : 987007458560905171 LCCN : nr2003030022 NKC : xx0115837 NTA : 072925124 NUKAT : n2011172061 SUDOC : 074089021 VIAF : 107793001 WorldCat VIAF : 107793001