L'articolo del 1971 intitolato The Complexity of Theorem Proving Procedures ha stabilito le basi formali per il problema P contro NP, una questione centrale nell'informatica che rimane irrisolta ancora oggi. Scritto da Stephen Cook, questo lavoro ha introdotto il concetto di NP-completezza, cambiando il modo in cui matematici e informatici classificano la difficoltà intrinseca dei compiti di calcolo.
Formazione accademica
Nato a Buffalo nel 1939, Cook ha compiuto i suoi studi superiori negli Stati Uniti. Ha conseguito una laurea triennale presso l'Università del Michigan nel 1961, seguita da un master e da un dottorato in scienze presso l'Università di Harvard rispettivamente nel 1962 e nel 1966. Ha iniziato la sua carriera di insegnamento come professore assistente presso l'Università della California, Berkeley, nel 1966. A seguito della sua partenza nel 1970, è entrato a far parte dell'Università di Toronto, dove ha prestato servizio nei dipartimenti di informatica e matematica, diventando infine Professore Distinto.
Complessità computazionale
La ricerca di Cook si concentra principalmente sulla teoria della complessità e sulla complessità delle dimostrazioni. Il suo lavoro fondamentale sul problema della soddisfacibilità booleana, o SAT, ha dimostrato che questo problema è NP-completo, una scoperta speculare e indipendente di Leonid Levin e oggi riconosciuta come il teorema di Cook-Levin. I suoi contributi includono anche la definizione delle classi di complessità NC, SC e AC0. Oltre alla complessità, ha studiato il calcolo parallelo, la semantica dei linguaggi di programmazione e l'aritmetica limitata.
Riconoscimenti professionali
Il suo lavoro gli è valso importanti riconoscimenti internazionali, tra cui il Premio Turing dell'ACM nel 1982 per aver fatto progredire la comprensione della complessità computazionale. È fellow dell'Association for Computing Machinery e membro di prestigiosi organismi tra cui la Royal Society, la National Academy of Sciences e l'American Academy of Arts and Sciences. In Canada, ha ricevuto la Medaglia d'oro Gerhard Herzberg per la scienza e l'ingegneria del Canada nel 2012 ed è stato nominato Ufficiale dell'Ordine del Canada nel 2015.
Venti domande, otto minuti di orologio e un percentile misurato su tutti quelli che l’hanno fatto. Senza registrazione.
Fai il test del QI →Informazioni rapide
- Nato: 1939, Buffalo - Cittadinanza: Canada e Stati Uniti - Premio Turing: 1982 - Titolo di studio: Dottore in scienze - Sede accademica: Università di Toronto - Riconoscimento notevole: Ufficiale dell'Ordine del Canada - Campo di ricerca: Complessità computacional
Domande frequenti
### Che cos'è il problema P contro NP?
È una domanda che chiede se ogni problema di decisione con risposte verificabili in modo efficiente possa anche essere risolto da un algoritmo efficiente.
### Che cos'è il teorema di Cook-Levin?
È la dimostrazione formale che il problema della soddisfacibilità booleana è NP-completo, stabilito indipendentemente da Stephen Cook e Leonid Levin.
