티스토리 뷰

개인적인 이야기/내 개인의 입장은...

교과서에 제시된 NP-Complete 문제 6종 시리즈

JOHNPARK82 2006. 6. 11. 17:00
알고리즘 최대의 난적 NP 단원에 도달했습니다. -_-;;;
교재에 나오는 NP-C 문제를 종류별로 나열해봄. 증명은 계속 봐도 잘모르겠음;;;

Circuit SAT ->p SAT ->p Clique ->p Hamilton Cycle ->p Vertex Covering ->p TSP
Circuit SAT ->p SAT ->p Subset Sum


단지 알아낸 것은 이 순서로 증명해 나간다는 사실뿐 -_-;; 역시 내 머린 평범하다.

Circuit Satisfiability (NP-hard)

C-SAT 문제가 NP-Hard 이기 때문에 이를 이용해서 하부의 증명을 해서 NP-Complete 을 밝히는 경우에는 반드시 해당문제가 NP문제임을 보여야한다.
(더욱 좌절인 것은 참고서에서 말하는 증명의 과정 조차도 formal 증명의 과정이 너무 어렵기 때문에 informal 한 방식으로 증명한 것이라는 사실이다. -_-;;;)




SAT Problem (so-called Cook's Theorem)

3-CNF-SAT Problem ( Boolean satisfiability problem )

Clique Problem

Hamilton Cycle Problem ( != Hamilton Path Problem )

Vertex Covering

TSP (Travelling Salesman Problem)

Subset Sum Problem

※ 예제로 증명하라고 한문제가 대충 10개 정도 더있음;;;