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

알고리즘 최대의 난적 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문제임을 보여야한다. (더욱 좌절인 것은 참고서에서 말하는 증명의 과정 조차도..
개인적인 이야기/내 개인의 입장은... 2006. 6. 11. 17:00
1