![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/6/68/Prof.Cook.jpg/640px-Prof.Cook.jpg&w=640&q=50)
스티븐 쿡
From Wikipedia, the free encyclopedia
스티븐 아서 쿡(Stephen Arthur Cook, 1939년 12월 14일~ )은 미국의 전산학자이다.
간략 정보 출생, 출신 학교 ...
스티븐 쿡 Stephen Arthur Cook | |
![]() | |
출생 | 1939년 12월 14일(1939-12-14)(84세) 미국 뉴욕주 버펄로 |
---|---|
출신 학교 | 하버드 대학교 미시간 대학교 |
주요 업적 | NP-완전 명제 논리 증명 복잡도 쿡-레빈 정리 |
수상 | 튜링상 (1982) CRM-Fields-PIMS 상 (1999) 존 L. 싱 상 (2006) 베르나르트 볼차노 메달 게르하르트 허츠버그 과학과 공학 캐나다 금메달 (2012) 캐나다 훈장 (2015) BBVA 재단 지식 프론티어 상 (2015) |
분야 | 컴퓨터 과학 |
소속 | 토론토 대학교 캘리포니아 대학교 버클리 |
박사 지도교수 | 하오 왕 |
박사 지도학생 | Paul Beame Mark Braverman Valentine Kabanets 토니안 피타시(Toniann Pitassi) 로버트 A. 렉하우(Robert A. Reckhow) 월터 사비치((Walter Savitch) |
닫기
1971년 ACM 《SIGACT Symposium on the Theory of Computing》에 실린 논문 〈The Complexity of Theorem Proving Procedures〉에서 NP-완전의 개념을 확립한 것으로 유명하다. 이 논문에 들어있는 쿡의 정리는 충족 가능성 문제가 NP-완전임을 증명하는 것이다. 이 논문에서 P와 NP가 같은지를 질문했는데 이를 P-NP 문제라고 부르며, 컴퓨터 과학의 가장 중요한 문제로 밀레니엄 문제 중 하나이기도 하다.