NP-COMPLETE 증명 질문.
글쓴이: Nadia85 / 작성시간: 일, 2006/12/17 - 2:43오후
알고리즘 공부 중에 도무지 모르겠어서 여기다 질문 올리네요 ㅠ,.ㅠ
np-complete 쳅터인데,
MIT 알고리즘 책 보면 subset sum 문제를 3 cnf로 리덕션 하는 부분 있잖아요....
이부분이 도대체 이해가 되질 않네요 ㅠ,.ㅠ
합으로 표현되는 subset sum을 어떻게 3cnf로 리덕션 시킨다는 것인지 ㅠ,.ㅠ
혹시 기본적인 아디리어라도 아시는분 계시면
가르침 부탁 드립니다.
Forums: