Stephen Cook

De Viquipèdia
Salta a la navegació Salta a la cerca
Infotaula de personaStephen Arthur Cook
Prof.Cook.jpg
Biografia
Naixement 14 de desembre de 1939 (1939-12-14) (79 anys)
Buffalo, Nova York
Formació Harvard
Universitat de Michigan
Es coneix per NP-completesa
Complexitat de prova proposicional
Teorema de Cook-Levin
Activitat
Director de tesi Hao Wang Tradueix
Camp de treball Ciències de la computació
Ocupació Informàtica
Organització Universitat de Toronto
Universitat de Califòrnia a Berkeley
Obra
Estudiant doctoral Toniann Pitassi
Família
Fills Gordon Cook

Lloc web Lloc web oficial
Modifica les dades 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 a la pàgina Millennium Prize Problems - Clay Mathematics Institute
  5. Descripció oficial del problema P vs. NP per Stephen Cook a Millennium Prize Problems

Enllaços externs[modifica]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Stephen Cook Modifica l'enllaç a Wikidata