질문, 건의, 요청 사항은 방명록(guest)에 올려 주십시오.

개요

SAT problem이 NP-complete class에 속함을 밝힌 Cook-Levin의 정리의 증명을 다룬다. 이를 통해, 모든 NP problem들이 SAT problem으로 polynomial time reducible하고, 또한 SAT problem이 모든 NP problem으로 polynomial time reducible함을 알 수 있다.

목차

- NP
- NP-complete
- SAT Problem
- A Characteristic of NP-complete
- Cook-Levin Theorem
- Proof of Cook-Levin Theorem
- Illustration
- Corollary: 3SAT∈NPC
신고
Posted by AALab

티스토리 툴바