343:
1259:
1244:
58:
1232:, University of Minnesota. Cook discussed his education at the University of Michigan and Harvard University and early work at the University of California, Berkeley, and his growing interest in problems of computational complexity. Cook recounted his move to the University of Toronto in 1970 and the reception of his work on NP-completeness, leading up to his A.M. Turing Award.
430:. Informally, the "P vs. NP" question asks whether every optimization problem whose answers can be efficiently verified for correctness/optimality can be solved optimally with an efficient algorithm. Given the abundance of such optimization problems in everyday life, a positive answer to the "P vs. NP" question would likely have profound practical and philosophical consequences.
458:
In his "Feasibly
Constructive Proofs and the Propositional Calculus" paper published in 1975, he introduced the equational theory PV (standing for Polynomial-time Verifiable) to formalize the notion of proofs using only polynomial-time concepts. He made another major contribution to the field in his
453:
presented at the 1971 ACM SIGACT Symposium on the Theory of
Computing, laid the foundations for the theory of NP-Completeness. The ensuing exploration of the boundaries and nature of NP-complete class of problems has been one of the most active and important research activities in computer science
682:
2015 in the
Information and Communication Technologies category "for his important role in identifying what computers can and cannot solve efficiently," in the words of the jury's citation. His work, it continues, "has had a dramatic impact in all fields where complex computations are crucial."
366:, mathematics department in 1966 as an assistant professor, and stayed there until 1970 when he was denied reappointment. In a speech celebrating the 30th anniversary of the Berkeley electrical engineering and computer sciences department, fellow
1219:
433:
Cook conjectures that there are optimization problems (with easily checkable solutions) that cannot be solved by efficient algorithms, i.e., P is not equal to NP. This conjecture has generated a great deal of research in
2194:
438:, which has considerably improved our understanding of the inherent difficulty of computational problems and what can be computed efficiently. Yet, the conjecture remains open and is among the seven famous
519:
390:
During his PhD, Cook worked on complexity of functions, mainly on multiplication. In his seminal 1971 paper "The
Complexity of Theorem Proving Procedures", Cook formalized the notions of
2139:
1044:
2174:
664:
176:
2189:
523:
594:
168:
2179:
1303:
484:
460:
671:
for "both the sustained excellence and overall influence of research work conducted in Canada in the natural sciences or engineering". He was named an
1597:
374:
said that, "It is to our everlasting shame that we were unable to persuade the math department to give him tenure." Cook joined the faculty of the
2169:
324:
618:
464:
679:
192:
610:
2209:
2204:
2144:
866:
378:, Computer Science and Mathematics Departments in 1970 as an associate professor, where he was promoted to professor in 1975 and
1158:
449:
For his advancement of our understanding of the complexity of computation in a significant and profound way. His seminal paper,
2184:
1136:
2199:
2164:
2154:
2149:
907:
614:
1117:
2044:
1590:
711:
840:
633:
629:
1664:
1286:
363:
229:
1935:
686:
Cook has supervised numerous MSc students, and 36 PhD students have completed their degrees under his supervision.
475:. They proved that the existence of a proof system in which every true formula has a short proof is equivalent to
2159:
1787:
1583:
491:
435:
331:
312:
672:
641:
499:
407:
267:
1872:
1324:
1239:
1096:
737:
27:
1295:
445:
In 1982, Cook received the Turing Award for his contributions to complexity theory. His citation reads:
1508:
931:
Cook, Stephen A.; Reckhow, Robert A. (1979). "The
Relative Efficiency of Propositional Proof Systems".
852:
468:
1435:
1229:
874:
848:
779:
598:
439:
391:
463:, "The Relative Efficiency of Propositional Proof Systems", in which they formalized the notions of
1523:
1518:
1403:
585:
E.W.R. Steacie
Memorial Fellowship in 1977, a Killam Research Fellowship in 1982, and received the
981:
606:
602:
507:
379:
279:
2129:
1279:
1264:
423:
355:
123:
104:
1816:
1469:
1356:
667:, the highest honor for scientists and engineers in Canada. The Herzberg Medal is awarded by
652:
586:
375:
320:
225:
152:
2134:
503:
351:
1030:
750:
342:
8:
2018:
1564:
590:
515:
257:
160:
1973:
1838:
1720:
1670:
1658:
1398:
1258:
1071:
964:
956:
913:
863:
511:
359:
308:
100:
1243:
805:
1866:
1844:
1549:
1528:
1393:
1334:
1272:
948:
903:
88:
1045:"Awarded The Bernard Bolzano Honorary Medals for Merit in the Mathematical Sciences"
917:
2040:
2028:
2002:
1957:
1953:
1698:
1692:
968:
940:
895:
888:"Feasibly constructive proofs and the propositional calculus (Preliminary Version)"
656:
495:
472:
427:
316:
303:
252:
215:
119:
47:
645:
144:
2101:
2054:
2034:
1919:
1905:
1834:
1793:
1771:
1714:
1676:
1635:
1559:
1489:
1423:
1413:
1408:
870:
844:
555:
547:
539:
476:
299:
271:
184:
43:
362:, respectively in 1962 and 1966, from the Mathematics Department. He joined the
2089:
2024:
2012:
1990:
1967:
1961:
1901:
1828:
1759:
1629:
1575:
1544:
1513:
1474:
1418:
1383:
1346:
543:
395:
275:
837:
2123:
2107:
2095:
2064:
2050:
2006:
1947:
1799:
1781:
1777:
1765:
1743:
1641:
1479:
1351:
1299:
1012:
952:
892:
Proceedings of seventh annual ACM symposium on Theory of computing - STOC '75
566:
426:. The paper also formulated the most famous problem in computer science, the
1235:
994:
733:
569:
was inspired by Cook's automata for recognizing concatenated palindromes in
2068:
1822:
1755:
1688:
1682:
1606:
1457:
1440:
1388:
775:
625:
527:
419:
415:
371:
367:
136:
1502:
1495:
1463:
1446:
1429:
1362:
1340:
1318:
899:
311:
and mathematician who has made significant contributions to the fields of
2195:
University of
California, Berkeley College of Letters and Science faculty
1996:
1878:
1860:
1854:
1708:
1623:
1554:
1378:
1368:
699:
570:
411:
403:
399:
114:
20:
887:
2085:
2058:
1941:
1915:
1911:
1895:
1737:
1702:
1484:
1452:
1329:
960:
283:
1249:
16:
American-Canadian computer scientist, contributor to complexity theory
1931:
1848:
1214:
1197:
562:
1172:
944:
1925:
1609:
1222:– Public lecture given by Stephen Cook at the University of Toronto
638:
fundamental contributions to the theory of computational complexity
894:. New York: Association for Computing Machinery. pp. 83–97.
695:
660:
1294:
1069:
487:
in this area titled "Logical
Foundations of Proof Complexity".
236:
665:
Gerhard
Herzberg Canada Gold Medal for Science and Engineering
177:
Gerhard
Herzberg Canada Gold Medal for Science and Engineering
1225:
668:
582:
57:
1253:
817:
550:
is named after him. The definition of the complexity class
480:
2140:
Members of the United States National Academy of Sciences
551:
2175:
2008 fellows of the Association for Computing Machinery
1137:"Computer scientist wins Canada's top science prize"
698:. They have two sons, one of whom is Olympic sailor
2190:
Harvard Graduate School of Arts and Sciences alumni
1097:"Gödel Lecturers – Association for Symbolic Logic"
873:problem's official description by Stephen Cook on
1118:"25 Appointees Named to Ontario's Highest Honour"
780:"A Personal View of Computer Science at Berkeley"
510:. Other areas that he has contributed to include
471:, which started an area now called propositional
307:(born December 14, 1939) is an American-Canadian
2121:
1605:
815:
729:
727:
319:. He is a university professor emeritus at the
818:"The Complexity of Theorem-Proving Procedures"
1591:
1280:
1017:Theoretical Computer Science – Stack Exchange
999:Theoretical Computer Science – Stack Exchange
451:The Complexity of Theorem Proving Procedures,
242:On the Minimum Computation Time of Functions
807:The Complexity of Theorem Proving Procedures
803:
774:
724:
680:BBVA Foundation Frontiers of Knowledge Award
619:Göttingen Academy of Sciences and Humanities
193:BBVA Foundation Frontiers of Knowledge Award
2180:Academic staff of the University of Toronto
1220:'P versus NP' and the Limits of Computation
930:
533:
483:. Cook co-authored a book with his student
414:. This theorem was proven independently by
330:He is considered one of the forefathers of
1598:
1584:
1287:
1273:
1257:
1242:
56:
1013:"Who introduced the complexity class AC?"
982:"Logical Foundations of Proof Complexity"
26:For other people named Stephen Cook, see
1226:Oral history interview with Stephen Cook
609:. Cook was elected to membership in the
341:
1122:Ministry of Citizenship and Immigration
358:, and his master's degree and PhD from
2170:Fellows of the Royal Society of Canada
2122:
1159:"Current Winner – 2012 – Stephen Cook"
617:. He is a corresponding member of the
1579:
1268:
1134:
1070:Association for Computing Machinery.
615:American Academy of Arts and Sciences
323:, Department of Computer Science and
885:
712:List of pioneers in computer science
576:
526:, and lower bounds in propositional
1031:"Twenty Questions for Donald Knuth"
630:Association for Computing Machinery
520:complexity of higher type functions
459:1979 paper, joint with his student
422:, and has thus been given the name
13:
1135:Emily, Chung (February 27, 2013).
748:
364:University of California, Berkeley
230:University of California, Berkeley
14:
2221:
1208:
813:– via University of Toronto
784:University of California Berkeley
402:, and proved the existence of an
886:Cook, Stephen A. (May 5, 1975).
689:
2210:Theoretical computer scientists
2205:Officers of the Order of Canada
2145:Members of the Order of Ontario
1190:
1165:
1151:
1128:
1110:
1089:
1063:
1037:
1023:
1005:
995:""Steve's class": origin of SC"
987:
601:(2008), and is a fellow of the
436:computational complexity theory
332:computational complexity theory
975:
924:
879:
857:
831:
797:
768:
742:
673:Officer of the Order of Canada
659:in 2013, the highest honor in
642:Association for Symbolic Logic
538:He named the complexity class
500:programming language semantics
408:Boolean satisfiability problem
370:winner and Berkeley professor
1:
2185:University of Michigan alumni
1240:Mathematics Genealogy Project
1198:"Stephen A. Cook – Home Page"
933:The Journal of Symbolic Logic
738:Mathematics Genealogy Project
717:
28:Stephen Cook (disambiguation)
2200:American emigrants to Canada
2165:Fellows of the Royal Society
2155:Canadian computer scientists
2150:American computer scientists
1215:Home page of Stephen A. Cook
694:Cook lives with his wife in
611:National Academy of Sciences
558:are also introduced by him.
490:His main research areas are
406:problem by showing that the
337:
7:
1051:. Czech Academy of Sciences
869:September 27, 2007, at the
705:
632:honored him as a Fellow of
385:
10:
2226:
1447:Ronald Charles Newman
853:Clay Mathematics Institute
469:propositional proof system
410:(usually known as SAT) is
185:Officer of Order of Canada
25:
18:
2078:
1983:
1888:
1809:
1730:
1651:
1616:
1537:
1458:Trevor Charles Platt
1436:Raghunath Anant Mashelkar
1310:
1230:Charles Babbage Institute
1173:"SaltWire | Halifax"
875:Millennium Prize Problems
849:Millennium Prize Problems
843:October 14, 2013, at the
816:Stephen A. Cook (2009) .
640:. He was selected by the
599:Czech Academy of Sciences
440:Millennium Prize Problems
392:polynomial-time reduction
325:Department of Mathematics
289:
263:
251:
235:
221:
211:
204:
129:
110:
96:
67:
55:
37:
1519:S. R. Srinivasa Varadhan
1503:John Michael Taylor
613:(United States) and the
534:Some other contributions
19:Not to be confused with
607:Royal Society of Canada
603:Royal Society of London
546:. The complexity class
508:artificial intelligence
498:, with excursions into
380:Distinguished Professor
2160:Turing Award laureates
1630:Maurice Vincent Wilkes
1529:Brian Worthington
1341:David Keith Bowen
663:. He has won the 2012
524:complexity of analysis
456:
424:the Cook–Levin theorem
356:University of Michigan
347:
105:University of Michigan
1470:Richard J. Puddephatt
1357:Thomas Cavalier-Smith
900:10.1145/800116.803756
804:Stephen Cook (1971),
751:"Stephen Arthur Cook"
678:Cook was granted the
655:appointed him to the
653:Government of Ontario
595:Bernard Bolzano Medal
587:CRM-Fields-PIMS prize
447:
376:University of Toronto
345:
321:University of Toronto
226:University of Toronto
169:Bernard Bolzano Medal
153:CRM-Fields-PIMS prize
1490:Jonathan Sprent
1424:Geoffrey Hinton
1363:David W. Clarke
1256:Bibliography Server
589:in 1999. He has won
581:Cook was awarded an
504:parallel computation
454:for the last decade.
2019:Michael Stonebraker
1817:Fernando J. CorbatĂł
1565:Rolf M. Zinkernagel
1496:James Staunton
1319:Colin Atkinson
1236:Stephen Arthur Cook
591:John L. Synge Award
516:reverse mathematics
296:Stephen Arthur Cook
161:John L. Synge Award
72:Stephen Arthur Cook
1974:Charles P. Thacker
1839:Richard E. Stearns
1721:Kenneth E. Iverson
1671:Edsger W. Dijkstra
1659:James H. Wilkinson
1607:A. M. Turing Award
1430:Steven Martin
1399:Richard B. Flavell
755:A. M. Turing Award
554:and its hierarchy
512:bounded arithmetic
360:Harvard University
350:Cook received his
348:
309:computer scientist
124:Cook–Levin theorem
101:Harvard University
2117:
2116:
1991:Leslie G. Valiant
1867:Douglas Engelbart
1845:Edward Feigenbaum
1573:
1572:
1550:Elias James Corey
1394:Charles Ellington
1335:Harshad Bhadeshia
1325:David Barker
1049:Medals of the CAS
909:978-1-4503-7419-4
624:Cook won the ACM
577:Awards and honors
492:complexity theory
485:Phuong The Nguyen
461:Robert A. Reckhow
354:in 1961 from the
352:bachelor's degree
313:complexity theory
293:
292:
264:Doctoral students
206:Scientific career
82:December 14, 1939
2217:
2041:John L. Hennessy
2029:Whitfield Diffie
2003:Shafi Goldwasser
1958:E. Allen Emerson
1954:Edmund M. Clarke
1699:Michael O. Rabin
1693:Herbert A. Simon
1600:
1593:
1586:
1577:
1576:
1509:Robert K. Thomas
1404:Ken Freeman
1289:
1282:
1275:
1266:
1265:
1261:
1246:
1202:
1201:
1194:
1188:
1187:
1185:
1183:
1177:www.saltwire.com
1169:
1163:
1162:
1161:. June 28, 2016.
1155:
1149:
1148:
1146:
1144:
1132:
1126:
1125:
1114:
1108:
1107:
1105:
1103:
1093:
1087:
1086:
1084:
1082:
1072:"Stephen A Cook"
1067:
1061:
1060:
1058:
1056:
1041:
1035:
1034:
1027:
1021:
1020:
1009:
1003:
1002:
991:
985:
984:'s official page
979:
973:
972:
928:
922:
921:
883:
877:
861:
855:
835:
829:
828:
826:
824:
814:
812:
801:
795:
794:
792:
790:
772:
766:
765:
763:
761:
746:
740:
731:
657:Order of Ontario
636:in 2008 for his
496:proof complexity
473:proof complexity
428:P vs. NP problem
317:proof complexity
306:
253:Doctoral advisor
247:
216:Computer Science
197:
189:
181:
173:
165:
157:
149:
141:
120:proof complexity
85:
81:
79:
60:
50:
35:
34:
2225:
2224:
2220:
2219:
2218:
2216:
2215:
2214:
2120:
2119:
2118:
2113:
2102:Robert Metcalfe
2074:
2055:Geoffrey Hinton
2045:David Patterson
2035:Tim Berners-Lee
1979:
1920:Leonard Adleman
1906:Kristen Nygaard
1884:
1835:Juris Hartmanis
1805:
1794:Ivan Sutherland
1726:
1715:Robert W. Floyd
1677:Charles Bachman
1647:
1636:Richard Hamming
1612:
1604:
1574:
1569:
1560:Oliver Smithies
1533:
1464:Alan Plumb
1414:J. Philip Grime
1409:Brian Greenwood
1330:Jean Beggs
1306:
1293:
1250:Stephen A. Cook
1211:
1206:
1205:
1196:
1195:
1191:
1181:
1179:
1171:
1170:
1166:
1157:
1156:
1152:
1142:
1140:
1133:
1129:
1116:
1115:
1111:
1101:
1099:
1095:
1094:
1090:
1080:
1078:
1068:
1064:
1054:
1052:
1043:
1042:
1038:
1029:
1028:
1024:
1011:
1010:
1006:
993:
992:
988:
980:
976:
945:10.2307/2273702
929:
925:
910:
884:
880:
871:Wayback Machine
862:
858:
845:Wayback Machine
836:
832:
822:
820:
810:
802:
798:
788:
786:
773:
769:
759:
757:
749:Kapron, Bruce.
747:
743:
732:
725:
720:
708:
692:
579:
536:
400:NP-completeness
394:(also known as
388:
340:
298:
282:
278:
274:
272:Toniann Pitassi
270:
245:
228:
200:
195:
187:
179:
171:
163:
155:
147:
139:
122:
117:
115:NP-completeness
103:
97:Alma mater
92:
86:
83:
77:
75:
74:
73:
63:
51:
42:
40:
31:
24:
17:
12:
11:
5:
2223:
2213:
2212:
2207:
2202:
2197:
2192:
2187:
2182:
2177:
2172:
2167:
2162:
2157:
2152:
2147:
2142:
2137:
2132:
2115:
2114:
2112:
2111:
2105:
2099:
2093:
2090:Jeffrey Ullman
2082:
2080:
2076:
2075:
2073:
2072:
2062:
2048:
2038:
2032:
2025:Martin Hellman
2022:
2016:
2013:Leslie Lamport
2010:
2000:
1994:
1987:
1985:
1981:
1980:
1978:
1977:
1971:
1968:Barbara Liskov
1965:
1962:Joseph Sifakis
1951:
1945:
1939:
1929:
1923:
1909:
1902:Ole-Johan Dahl
1899:
1892:
1890:
1886:
1885:
1883:
1882:
1876:
1870:
1864:
1858:
1852:
1842:
1832:
1829:Butler Lampson
1826:
1820:
1813:
1811:
1807:
1806:
1804:
1803:
1797:
1791:
1785:
1775:
1769:
1763:
1760:Dennis Ritchie
1753:
1747:
1741:
1734:
1732:
1728:
1727:
1725:
1724:
1718:
1712:
1706:
1696:
1686:
1680:
1674:
1668:
1662:
1655:
1653:
1649:
1648:
1646:
1645:
1639:
1633:
1627:
1620:
1618:
1614:
1613:
1603:
1602:
1595:
1588:
1580:
1571:
1570:
1568:
1567:
1562:
1557:
1552:
1547:
1545:John E. Casida
1541:
1539:
1535:
1534:
1532:
1531:
1526:
1521:
1516:
1514:Cheryll Tickle
1511:
1506:
1499:
1492:
1487:
1482:
1477:
1475:Philip Ruffles
1472:
1467:
1460:
1455:
1450:
1443:
1438:
1433:
1426:
1421:
1419:David C. Hanna
1416:
1411:
1406:
1401:
1396:
1391:
1386:
1384:Richard Denton
1381:
1376:
1371:
1366:
1359:
1354:
1349:
1347:Roger Cashmore
1344:
1337:
1332:
1327:
1322:
1314:
1312:
1308:
1307:
1292:
1291:
1284:
1277:
1269:
1263:
1262:
1247:
1233:
1223:
1217:
1210:
1209:External links
1207:
1204:
1203:
1189:
1164:
1150:
1127:
1109:
1088:
1076:awards.acm.org
1062:
1036:
1022:
1004:
986:
974:
923:
908:
878:
856:
830:
796:
767:
741:
722:
721:
719:
716:
715:
714:
707:
704:
691:
688:
578:
575:
544:Nick Pippenger
535:
532:
467:and efficient
396:Cook reduction
387:
384:
339:
336:
291:
290:
287:
286:
276:Walter Savitch
268:Mark Braverman
265:
261:
260:
255:
249:
248:
239:
233:
232:
223:
219:
218:
213:
209:
208:
202:
201:
199:
198:
190:
182:
174:
166:
158:
150:
142:
133:
131:
127:
126:
118:Propositional
112:
111:Known for
108:
107:
98:
94:
93:
87:
71:
69:
65:
64:
61:
53:
52:
41:
38:
15:
9:
6:
4:
3:
2:
2222:
2211:
2208:
2206:
2203:
2201:
2198:
2196:
2193:
2191:
2188:
2186:
2183:
2181:
2178:
2176:
2173:
2171:
2168:
2166:
2163:
2161:
2158:
2156:
2153:
2151:
2148:
2146:
2143:
2141:
2138:
2136:
2133:
2131:
2130:Living people
2128:
2127:
2125:
2109:
2108:Avi Wigderson
2106:
2103:
2100:
2097:
2096:Jack Dongarra
2094:
2091:
2087:
2084:
2083:
2081:
2077:
2070:
2066:
2063:
2060:
2056:
2052:
2051:Yoshua Bengio
2049:
2046:
2042:
2039:
2036:
2033:
2030:
2026:
2023:
2020:
2017:
2014:
2011:
2008:
2007:Silvio Micali
2004:
2001:
1998:
1995:
1992:
1989:
1988:
1986:
1982:
1975:
1972:
1969:
1966:
1963:
1959:
1955:
1952:
1949:
1948:Frances Allen
1946:
1943:
1940:
1937:
1933:
1930:
1927:
1924:
1921:
1917:
1913:
1910:
1907:
1903:
1900:
1897:
1894:
1893:
1891:
1887:
1880:
1877:
1874:
1871:
1868:
1865:
1862:
1859:
1856:
1853:
1850:
1846:
1843:
1840:
1836:
1833:
1830:
1827:
1824:
1821:
1818:
1815:
1814:
1812:
1808:
1801:
1800:William Kahan
1798:
1795:
1792:
1789:
1786:
1783:
1782:Robert Tarjan
1779:
1778:John Hopcroft
1776:
1773:
1770:
1767:
1766:Niklaus Wirth
1764:
1761:
1757:
1754:
1751:
1748:
1745:
1744:Edgar F. Codd
1742:
1739:
1736:
1735:
1733:
1729:
1722:
1719:
1716:
1713:
1710:
1707:
1704:
1700:
1697:
1694:
1690:
1687:
1684:
1681:
1678:
1675:
1672:
1669:
1666:
1665:John McCarthy
1663:
1660:
1657:
1656:
1654:
1650:
1643:
1642:Marvin Minsky
1640:
1637:
1634:
1631:
1628:
1625:
1622:
1621:
1619:
1615:
1611:
1608:
1601:
1596:
1594:
1589:
1587:
1582:
1581:
1578:
1566:
1563:
1561:
1558:
1556:
1553:
1551:
1548:
1546:
1543:
1542:
1540:
1536:
1530:
1527:
1525:
1522:
1520:
1517:
1515:
1512:
1510:
1507:
1505:
1504:
1500:
1498:
1497:
1493:
1491:
1488:
1486:
1483:
1481:
1480:Anthony Segal
1478:
1476:
1473:
1471:
1468:
1466:
1465:
1461:
1459:
1456:
1454:
1451:
1449:
1448:
1444:
1442:
1439:
1437:
1434:
1432:
1431:
1427:
1425:
1422:
1420:
1417:
1415:
1412:
1410:
1407:
1405:
1402:
1400:
1397:
1395:
1392:
1390:
1387:
1385:
1382:
1380:
1377:
1375:
1372:
1370:
1367:
1365:
1364:
1360:
1358:
1355:
1353:
1352:Andrew Casson
1350:
1348:
1345:
1343:
1342:
1338:
1336:
1333:
1331:
1328:
1326:
1323:
1321:
1320:
1316:
1315:
1313:
1309:
1305:
1301:
1300:Royal Society
1297:
1290:
1285:
1283:
1278:
1276:
1271:
1270:
1267:
1260:
1255:
1251:
1248:
1245:
1241:
1237:
1234:
1231:
1227:
1224:
1221:
1218:
1216:
1213:
1212:
1199:
1193:
1178:
1174:
1168:
1160:
1154:
1138:
1131:
1123:
1119:
1113:
1098:
1092:
1077:
1073:
1066:
1050:
1046:
1040:
1032:
1026:
1018:
1014:
1008:
1000:
996:
990:
983:
978:
970:
966:
962:
958:
954:
950:
946:
942:
938:
934:
927:
919:
915:
911:
905:
901:
897:
893:
889:
882:
876:
872:
868:
865:
860:
854:
850:
846:
842:
839:
834:
819:
809:
808:
800:
785:
781:
777:
771:
756:
752:
745:
739:
735:
730:
728:
723:
713:
710:
709:
703:
701:
697:
690:Personal life
687:
684:
681:
676:
674:
670:
666:
662:
658:
654:
649:
647:
646:Gödel Lecture
643:
639:
635:
631:
627:
622:
620:
616:
612:
608:
604:
600:
596:
592:
588:
584:
574:
572:
568:
567:KMP algorithm
564:
561:According to
559:
557:
553:
549:
545:
541:
531:
529:
528:proof systems
525:
521:
517:
513:
509:
505:
501:
497:
493:
488:
486:
482:
478:
474:
470:
466:
462:
455:
452:
446:
443:
441:
437:
431:
429:
425:
421:
417:
413:
409:
405:
401:
397:
393:
383:
381:
377:
373:
369:
365:
361:
357:
353:
344:
335:
333:
328:
326:
322:
318:
314:
310:
305:
301:
297:
288:
285:
281:
277:
273:
269:
266:
262:
259:
256:
254:
250:
243:
240:
238:
234:
231:
227:
224:
220:
217:
214:
210:
207:
203:
194:
191:
186:
183:
178:
175:
170:
167:
162:
159:
154:
151:
146:
145:Gödel Lecture
143:
138:
135:
134:
132:
128:
125:
121:
116:
113:
109:
106:
102:
99:
95:
90:
84:(age 84)
70:
66:
59:
54:
49:
45:
36:
33:
29:
22:
2069:Pat Hanrahan
1823:Robin Milner
1772:Richard Karp
1756:Ken Thompson
1750:Stephen Cook
1749:
1689:Allen Newell
1683:Donald Knuth
1524:Bernard Wood
1501:
1494:
1462:
1445:
1441:Yoshio Masui
1428:
1389:Raymond Dwek
1374:Stephen Cook
1373:
1361:
1339:
1317:
1192:
1182:February 12,
1180:. Retrieved
1176:
1167:
1153:
1143:February 27,
1141:. Retrieved
1130:
1121:
1112:
1100:. Retrieved
1091:
1081:February 12,
1079:. Retrieved
1075:
1065:
1053:. Retrieved
1048:
1039:
1025:
1016:
1007:
998:
989:
977:
939:(1): 36–50.
936:
932:
926:
891:
881:
859:
833:
823:February 12,
821:. Retrieved
806:
799:
789:February 12,
787:. Retrieved
783:
776:Richard Karp
770:
758:. Retrieved
754:
744:
734:Stephen Cook
693:
685:
677:
650:
644:to give the
637:
626:Turing Award
623:
580:
560:
537:
489:
465:p-simulation
457:
450:
448:
444:
432:
420:Soviet Union
416:Leonid Levin
389:
372:Richard Karp
368:Turing Award
349:
346:Cook in 1968
329:
295:
294:
280:Arvind Gupta
241:
222:Institutions
205:
137:Turing Award
62:Cook in 2008
39:Stephen Cook
32:
2135:1939 births
1997:Judea Pearl
1879:Fred Brooks
1861:Amir Pnueli
1855:Manuel Blum
1709:John Backus
1624:Alan Perlis
1555:Walter Kohn
1379:Peter Crane
1369:Enrico Coen
1102:November 8,
847:problem on
760:October 23,
700:Gordon Cook
571:linear time
412:NP-complete
404:NP-complete
21:Steven Cook
2124:Categories
2086:Alfred Aho
2065:Ed Catmull
2059:Yann LeCun
1942:Peter Naur
1916:Adi Shamir
1912:Ron Rivest
1896:Andrew Yao
1788:John Cocke
1738:Tony Hoare
1703:Dana Scott
1485:Ashoke Sen
1453:Mark Pepys
718:References
628:in 1982.
514:, bounded
284:Anna Lubiw
91:, New York
78:1939-12-14
1932:Vint Cerf
1849:Raj Reddy
1610:laureates
1055:April 13,
953:0022-4812
675:in 2015.
648:in 1999.
563:Don Knuth
382:in 1985.
338:Biography
1936:Bob Kahn
1926:Alan Kay
1873:Jim Gray
1302:elected
1139:. cbc.ca
918:13309619
867:Archived
864:P vs. NP
841:Archived
838:P vs. NP
778:(2003).
706:See also
386:Research
258:Hao Wang
1538:Foreign
1311:Fellows
1304:in 1998
1298:of the
1296:Fellows
1238:at the
969:2187041
961:2273702
851:page –
736:at the
696:Toronto
661:Ontario
597:of the
418:in the
89:Buffalo
2110:(2023)
2104:(2022)
2098:(2021)
2092:(2020)
2071:(2019)
2061:(2018)
2047:(2017)
2037:(2016)
2031:(2015)
2021:(2014)
2015:(2013)
2009:(2012)
1999:(2011)
1993:(2010)
1976:(2009)
1970:(2008)
1964:(2007)
1950:(2006)
1944:(2005)
1938:(2004)
1928:(2003)
1922:(2002)
1908:(2001)
1898:(2000)
1881:(1999)
1875:(1998)
1869:(1997)
1863:(1996)
1857:(1995)
1851:(1994)
1841:(1993)
1831:(1992)
1825:(1991)
1819:(1990)
1802:(1989)
1796:(1988)
1790:(1987)
1784:(1986)
1774:(1985)
1768:(1984)
1762:(1983)
1752:(1982)
1746:(1981)
1740:(1980)
1723:(1979)
1717:(1978)
1711:(1977)
1705:(1976)
1695:(1975)
1685:(1974)
1679:(1973)
1673:(1972)
1667:(1971)
1661:(1970)
1644:(1969)
1638:(1968)
1632:(1967)
1626:(1966)
967:
959:
951:
916:
906:
542:after
506:, and
398:) and
246:(1966)
244:
237:Thesis
212:Fields
196:(2015)
188:(2015)
180:(2012)
172:(2008)
164:(2006)
156:(1999)
148:(1999)
140:(1982)
130:Awards
2079:2020s
1984:2010s
1889:2000s
1810:1990s
1731:1980s
1652:1970s
1617:1960s
965:S2CID
957:JSTOR
914:S2CID
811:(PDF)
669:NSERC
583:NSERC
302:
46:
1254:DBLP
1184:2023
1145:2013
1104:2021
1083:2023
1057:2024
949:ISSN
904:ISBN
825:2023
791:2023
762:2018
651:The
605:and
593:and
565:the
494:and
481:coNP
315:and
304:OOnt
68:Born
48:OOnt
1252:at
1228:at
941:doi
896:doi
634:ACM
2126::
2088:;
2067:;
2057:;
2053:;
2043:;
2027:;
2005:;
1960:;
1956:;
1934:;
1918:;
1914:;
1904:;
1847:;
1837:;
1780:;
1758:;
1701:;
1691:;
1175:.
1120:.
1074:.
1047:.
1015:.
997:.
963:.
955:.
947:.
937:44
935:.
912:.
902:.
890:.
782:.
753:.
726:^
702:.
621:.
573:.
556:AC
552:AC
548:SC
540:NC
530:.
522:,
518:,
502:,
479:=
477:NP
442:.
334:.
327:.
300:OC
80:)
44:OC
1599:e
1592:t
1585:v
1288:e
1281:t
1274:v
1200:.
1186:.
1147:.
1124:.
1106:.
1085:.
1059:.
1033:.
1019:.
1001:.
971:.
943::
920:.
898::
827:.
793:.
764:.
76:(
30:.
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
