Stephen Cook
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]- ↑ A Personal View of Computer Science at Berkeley - Richard Karp
- ↑ "The Complexity of Theorem Proving Procedures", fitxer en PDF escanejat
- ↑ "The Complexity of Theorem Proving Procedures", fitxer en PDF d'una versió tornada a picar
- ↑ Problema P vs. NP Arxivat 2007-08-11 a Wayback Machine. a la pàgina Millennium Prize Problems - Clay Mathematics Institute
- ↑ 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]- 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
- Persones vives
- Premiats amb el Premi Turing
- Informàtics de l'estat de Nova York
- Matemàtics de l'estat de Nova York
- Persones de Buffalo
- Alumnes de la Universitat Harvard
- Alumnes de la Universitat de Michigan
- Membres de la Royal Society
- Professors de la Universitat de Toronto
- Professors de la Universitat de Califòrnia a Berkeley
- Informàtics canadencs
- Matemàtics canadencs
- Científics de l'estat de Nova York