스티븐 쿡은 누구인지에 대해서 이야기해봅시다.
스티븐 쿡은 누구?
스티븐 쿡(Stephen Cook)은 NP 완전 문제의 존재를 증명한 사람입니다.
스티븐쿡은 1939년 미국 뉴욕에서 태어났습니다. 논리식의 충족 가능성 문제가 NP 완전이라는 것을 증명함으로써 NP 완전 문제의 존재를 증명하였습니다.
NP 완전 문제를 풀 수 있으면 컴퓨터의 역사를 크게 바꿀 수 있게 되는데 NP 완전 문제의 존재를 증명한 것만으로도 그 가치를 인정 받고 있습니다. 해당 증명은 쿡-레빈(Cook-Levin) 정리라고 합니다. NP 완전 문제는 컴퓨터가 문제를 풀 때 걸리는 시간을 P와 NP라는 클래스로 분류할 수 있는데 NP 중에서 가장 어려운 문제를 의미합니다.
스티븐쿡은 1971년에 “정리 증명 절차의 복잡성” 논문을 발표하였고 여기에서 NP-완전 개념을 최초로 제시하였습니다. 해당 논문에서는 NP-완전에 해당하는 3개의 문제를 제시하였고 이후 다른 사람들에 의해 계속 추가되고 있습니다.
스티븐 쿡에 대한 설명
스티븐 쿡(Stephen Cook)은 NP-완전의 개념을 확립한 사람입니다.
스티븐쿡의 “The Complexity of Theorem Proving Procedures” 논문에 포함되어 있는 쿡의 정리는 충족 가능성 문제가 NP-완전이라는 것을 증명하는 것이었습니다. 해당 논문에서는 P와 NP가 동일한지 여부에 대한 질문이 있는데 이를 P-NP 문제라고 부르고 이는 컴퓨터 과학의 가장 중요한 문제로 알려져 있습니다.
P와 NP는 같지 않다고 예상하는 것에 대해서 많은 수학자들이 논문을 만들었지만 해당 검증 결과는 아직 제시되지 않았습니다. P와 NP가 같지 않다고 예상하는 것은 클래스 P와 클래스 NP의 두 집합이 다르다고 스티븐 쿡에 의해서 제안된 예상이며 이는 미 해결 밀레니엄 현상 문제의 하나가 되고 있습니다.
클래스 SC는 스티븐쿡의 이름을 따서 만든 클래스 이름입니다. 또한 클래스 P는 클래스 PolyL에 속하는 결정성 튜링 머신으로 해결 가능한 문제 클래스를 의미합니다.
[스티븐쿡 프로필]
| 구분 | 내용 |
| 성명 | 스티븐 쿡(Stephen Arthur Cook) |
| 출생일 | 1939년 12월 14일 |
| 출생지 | 미국 뉴욕주 버펄로 |
| 국적 | 미국(United State of America) |
| 성별 | 남자 |
| 학력 | 하버드 대학교 미시간 대학교 |
| 경력 | NP-완전 문제의 존재 증명 명제 논리 증명 복잡도 쿡-레빈 정리 튜링상 수상(1982년) CRM-Fields-PIMS 상(1999년) 존 L. 싱 상(2006년) 캐나다 훈장 수상(2015년) BBVA 재단 지식 프론티어 상 수상(2015년) 토론토 대학교 수학과 교수 |
스티븐쿡은 병렬 처리 회로, 프로그래밍 언어 의미 검증 분야에서도 의미 있는 연구 결과들을 많이 발표하였습니다. 토론토 대학교의 수학과 교수이며 요트를 좋아하여 로열 캐나다 요트 클럽 회원으로도 활동하고 있습니다.