Vés al contingut

Stephen Cook

De la Viquipèdia, l'enciclopèdia lliure
Plantilla:Infotaula personaStephen Arthur Cook

Modifica el valor a Wikidata
Nom original(en) Stephen Cook Modifica el valor a Wikidata
Biografia
Naixement14 desembre 1939 Modifica el valor a Wikidata (84 anys)
Buffalo (Nova York) Modifica el valor a Wikidata
FormacióHarvard
Universitat de Michigan
Director de tesiHao Wang Modifica el valor a Wikidata
Es coneix perNP-completesa
Complexitat de prova proposicional
Teorema de Cook-Levin
Activitat
Camp de treballCiències de la computació Modifica el valor a Wikidata
OcupacióInformàtica
OrganitzacióUniversitat de Toronto
Universitat de Califòrnia a Berkeley
Membre de
Obra
Estudiant doctoralToniann Pitassi, Anna Lubiw, Mark Braverman, Walter Savitch, Arvind Gupta, Michael Soltys (en) Tradueix, H. James (Howard) Hoover (en) Tradueix, Paul William Beame (en) Tradueix, Romas Aleliunas (en) Tradueix, Valentine Kabanets (en) Tradueix, François Pitt (en) Tradueix, Bruce M. Kapron (en) Tradueix, Pierre Murdock McKenzie (en) Tradueix, Xudong Fu (en) Tradueix, Patrick William Dymond (en) Tradueix, Antonina Kolokolova (en) Tradueix, Roberto Lins de Carvalho (en) Tradueix, Alan Ramsay Skelley (en) Tradueix, Tomoyuki Yamakami (en) Tradueix, Tsuyoshi Morioka (en) Tradueix, Phuong The Nguyen (en) Tradueix, Steven Perron (en) Tradueix, Leslie Michael Goldschlager (en) Tradueix, Derek C. Oppen (en) Tradueix, Daniel Brand (en) Tradueix, Martin Dowd (en) Tradueix, Gloria Kissin (en) Tradueix, Stephen Bellantoni (en) Tradueix, Robert A. Reckhow (en) Tradueix, Akitoshi Kawamura (en) Tradueix, Dai Tri Man Le (en) Tradueix, Lila A. Fontes (en) Tradueix, R. Dustin Wehr (en) Tradueix, Kaveh Ghasemloo (en) Tradueix i Robert Robere (en) Tradueix Modifica el valor a Wikidata
Família
FillsGordon Cook Modifica el valor a Wikidata
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 webcs.toronto.edu… Modifica el valor a Wikidata

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

[modifica]

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

[modifica]

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

[modifica]
  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

[modifica]