이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.
쿡레빈정리 [2010-07-12 23:29] lifthrasiir +분류 |
쿡레빈정리 [2011-05-30 18:25] (현재) |
||
---|---|---|---|
줄 3: | 줄 3: | ||
[[en>Cook-Levin theorem]]. [[SAT]]가 [[NP-완전]]함을 증명한다. | [[en>Cook-Levin theorem]]. [[SAT]]가 [[NP-완전]]함을 증명한다. | ||
- | 기본적인 아이디어는 비결정적 [[튜링머신]](NTM)을 다항시간 안에 동형의 SAT 인스턴스로 변환할 수 있다는 것이다. (변환 과정은 사실 별로 어려운 건 아님) [[NP]]의 정의에 따라 모든 NP 문제는 다항시간 안에 문제를 푸는 NTM이 존재할테니 SAT는 NP보다 어렵지 않은데 SAT가 NP인 건 자명하니 결국 NP-완전이 된다. | + | 기본적인 아이디어는 비결정적 [[튜링기계]](NTM)를 [[다항시간]] 안에 동형의 SAT 인스턴스로 변환할 수 있다는 것이다. (변환 과정은 사실 별로 어려운 건 아님) [[NP복잡도|NP]]의 정의에 따라 모든 NP 문제는 다항시간 안에 문제를 푸는 NTM이 존재할테니 SAT는 NP보다 어렵지 않은데 SAT가 NP인 건 자명하니 결국 NP-완전이 된다. |
{{tag>전산학}} | {{tag>전산학}} |