P = NP임을 증명하려면 NP에 속한 각각의 문제에 대해 문제를 풀 수 있는 다항 시간 알고리즘을 찾아야 합니다. 하지만 이 작업은 단순화할 수 있습니다. 즉, 많은 문제 중에서 하나만 다항 시간 알고리즘을 찾으면 됩니다. 하나만 다항 시간 알고리즘을 찾으면, 나머지 문제들도 마찬가지로 P에 속하게 되는 NP-Complete에 대해 알아보겠습니다. 우선 알아보기 전에 이론의 기초가 되는 CNF-Satisfiability에 대해 알아봐야 합니다. 그리고 마지막으로 지금까지 결정 문제에 대해서만 NP, P를 따졌는데, 이제는 최적화 문제까지 확장한 NP-Hard에 대해서도 알아보겠습니다. 1. CNF-Satisfiability CNF ~ 는 Conjunctive Normal Form의 약자로, 논리식 사이..