( http://geomblog.blogspot.com/2008/03/joys-of-nae-sat.html 이 글을 보면서 생각난 김에 정리해 두는 중임)   어려운 문제임을 증명할 때, 그 문제를 풀 수 있다면, 3SAT도 풀 수 있음을 보이면 된다. 3SAT은 어려운 문제이므로, 그 증명하고자 하는 문제가 적어도 어려운 3SAT만큼이나 어렵다는 것을 보이는 것이다. 즉, 3SAT의 어떤 문제를 요령껏 바꾸어 어렵다고 증명하고 싶은 문제로 바꾸는 데 성공한다면, 증명하고 싶은 […]