Stephen Cook

Stephen Arthur Cook

Nom original	(en) Stephen Cook
Biografia
Naixement	14 desembre 1939 (84 anys) Buffalo (Nova York)
Formació	Harvard Universitat de Michigan
Director de tesi	Hao Wang
Es coneix per	NP-completesa Complexitat de prova proposicional Teorema de Cook-Levin
Activitat
Camp de treball	Ciències de la computació
Ocupació	Informàtica
Organització	Universitat de Toronto Universitat de Califòrnia a Berkeley
Membre de	Association for Computing Machinery (membre de l'Association for Computing Machinery) (2009–) Royal Society (Membre de la Royal Society) (1998–) Acadèmia Nacional de Ciències dels Estats Units (membre de l'Acadèmia Nacional de Ciències dels Estats Units) (1985–) Royal Society del Canadà (1984–) Acadèmia Americana de les Arts i les Ciències Acadèmia de Ciències de Göttingen
Obra
Estudiant doctoral	Toniann Pitassi, Anna Lubiw, Mark Braverman, Walter Savitch, Arvind Gupta, Michael Soltys ^(en) , H. James (Howard) Hoover ^(en) , Paul William Beame ^(en) , Romas Aleliunas ^(en) , Valentine Kabanets ^(en) , François Pitt ^(en) , Bruce M. Kapron ^(en) , Pierre Murdock McKenzie ^(en) , Xudong Fu ^(en) , Patrick William Dymond ^(en) , Antonina Kolokolova ^(en) , Roberto Lins de Carvalho ^(en) , Alan Ramsay Skelley ^(en) , Tomoyuki Yamakami ^(en) , Tsuyoshi Morioka ^(en) , Phuong The Nguyen ^(en) , Steven Perron ^(en) , Leslie Michael Goldschlager ^(en) , Derek C. Oppen ^(en) , Daniel Brand ^(en) , Martin Dowd ^(en) , Gloria Kissin ^(en) , Stephen Bellantoni ^(en) , Robert A. Reckhow ^(en) , Akitoshi Kawamura ^(en) , Dai Tri Man Le ^(en) , Lila A. Fontes ^(en) , R. Dustin Wehr ^(en) , Kaveh Ghasemloo ^(en) i Robert Robere ^(en)
Família
Fills	Gordon Cook
Premis
Premi Turing (1982) CRM-Fields-PIMS prize (1999) Premi John L. Synge (2006) Bernard Bolzano Medal Gerhard Herzberg Canada Gold Medal for Science and Engineering (2012) Premi de la Fundació BBVA Fronteres del Coneixement (2015)
Lloc web	cs.toronto.edu…

Stephen Arthur Cook, OC, OOnt (nascut el 14 de desembre de 1939) és un prestigiós informàtic i matemàtic que ha fet contribucions importants en els camps de la complexitat computacional i la complexitat de proves. És professor de la Universitat de Toronto, als departaments d'Informàtica i de Matemàtiques.

Biografia

Cook es va llicenciar el 1961 a la Universitat de Michigan, i va fer un màster i doctorat a Harvard, respectivament els anys 1962 i 1966. Va passar a fer de professor ajudant al departament de matemàtiques de la Universitat de Califòrnia a Berkeley el 1966, i s'hi va quedar fins al 1970 quan no el van renovar. En un discurs de celebració del 30è aniversari del departament d'informàtica de Berkeley, un altre professor de Berkeley guanyador del Premi Turing, Richard Karp va dir, "serà sempre una vergonya per nosaltres que no poguéssim convèncer el departament de matemàtiques que el fessin catedràtic."^[1] Aquell mateix any Cook va passar als departaments d'Informàtica i de Matemàtiques de la Universitat de Toronto, com a professor associat; allà fou promocionat a professor el 1975 i "professor distingit" el 1985.

Recerca

Stephen Cook és considerat com un dels pares de la teoria de la complexitat computacional.

En el seu doctorat, Cook va treballar en la complexitat de les funcions, sobretot en la multiplicació. En el seu article crucial de 1971 "The Complexity of Theorem Proving Procedures",^[2][3] Cook va formalitzar els conceptes de transformació polinòmica (coneguda també com a reducció de Cook) i NP-completesa, i va demostrar l'existència d'un problema NP-complet mostrant que el problema de satisfacibilitat booleana (conegut com a SAT) és NP-complet. Aquest teorema el va demostrar de forma independent Leonid Levin a la Unió Soviètica, i per això es coneix com a Teorema Cook-Levin. L'article també formulava el problema més famós de la informàtica: P versus NP. De manera informal, la pregunta "P vs. NP" qüestiona si tots els problemes d'optimització les respostes dels quals es poden verificar de forma eficient per correctesa/optimalitat es poden resoldre de manera òptima amb un algorisme eficient. Degut a l'abundància d'aquest tipus de problemes d'optimització en la vida diària, una resposta afirmativa a la pregunta "P vs. NP" tindria profundes conseqüències pràctiques i filosòfiques.

La conjectura de Cook és que hi ha problemes d'optimització (amb solucions que es poden comprovar fàcilment) que no es poden resoldre amb algorismes eficients, és a dir, que P no és igual que NP. Aquesta conjectura ha generat molta recerca en teoria de la complexitat computacional, que ha millorat considerablement la comprensió de la dificultat inherent dels problemes de computació, i del que es pot calcular de forma eficient. No obstant, la conjectura continua oberta i és un dels set problemes del mil·lenni.^[4][5]

El 1982, Cook va rebre el prestigiós Premi Turing per les seves contribucions a la teoria de la complexitat. El text de l'anunci diu:

Pel seu avenç de la nostra comprensió de la complexitat del càlcul de forma significativa i profunda. El seu article pioner, The Complexity of Theorem Proving Procedures, presentat al Simposi de l'ACM SIGACT de 1971 sobre Teoria de la Computació, va posar els fonaments de la teoria de NP-Completesa. L'exploració que va seguir sobre els límits i la natura de la classe de problemes NP-complets ha estat una de les activitats de recerca més actives i importants de la informàtica durant l'última dècada.

Referències

1. A Personal View of Computer Science at Berkeley - Richard Karp
2. "The Complexity of Theorem Proving Procedures", fitxer en PDF escanejat
3. "The Complexity of Theorem Proving Procedures", fitxer en PDF d'una versió tornada a picar
4. Problema P vs. NP Arxivat 2007-08-11 a Wayback Machine. a la pàgina Millennium Prize Problems - Clay Mathematics Institute
5. Descripció oficial del problema P vs. NP Arxivat 2007-09-27 a Wayback Machine. per Stephen Cook a Millennium Prize Problems

Enllaços externs

• Pàgina personal de Stephen A. Cook
• ‘P versus NP’ and the Limits of Computation Arxivat 2016-03-04 a Wayback Machine. - Conferència de Stephen Cook a la Universitat de Toronto
• Entrevista d'història oral amb Stephen Cook al Charles Babbage Institute, University of Minnesota. Cook parla de la seva educació a les Universitats de Michigan i Harvard i la primera feina a Berkeley, i el seu creixent interès en problemes de complexitat computacional. Cook va explicar el seu trasllat a la Universitat de Toronto el 1970 i la rebuda de la seva feina en NP-completesa, que va portar al seu Premi Turing.
• Stephen Cook al Mathematics Genealogy Project.
• Stephen Cook Arxivat 2012-04-10 a Wayback Machine. al DBLP