Cook-Levin theorem. SAT가 NP-완전함을 증명한다.
기본적인 아이디어는 비결정적 튜링 기계(NTM)를 다항시간 안에 동형의 SAT 인스턴스로 변환할 수 있다는 것이다. (변환 과정은 사실 별로 어려운 건 아님) NP의 정의에 따라 모든 NP 문제는 다항시간 안에 문제를 푸는 NTM이 존재할테니 SAT는 NP보다 어렵지 않은데 SAT가 NP인 건 자명하니 결국 NP-완전이 된다.
메아리 풉;
9085d92e02
