차이점

이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.

--- 쿡레빈정리 [2010-07-12 23:29]
lifthrasiir +분류
+++ 쿡레빈정리 [2011-05-30 18:25] (현재)
@@ 줄 3: / 줄 3: @@
 [[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>전산학}}

도쿠위키와 DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-05-30 18:25 | 외부 편집기