.png)
학부 알고리즘 수업에서 Problem의 분류에 대해서 자세히 배운 바 있다. 해당 수업에서는 NP-Easy, Reduction과 관련된 각 종 Theorem과 그 proofs들에 대해서도 자세히 다루었지만, 본인의 앞으로의 커리어에 있어서 P와 NP에 대한 명확한 이해만 유지되어도 충분하다 느껴 이 부분에 대해서만 간단히 정리해놓고자 한다.
P
P는 명확하다. Polynomial Time Algorithm으로 Problem Solving이 가능한 문제들의 집합이다. 조금 더 엄밀히 정의하면, Deterministic Algorithm으로 Polynomial Time 내에 해결할 수 있는 문제들의 집합이다.
NP
NP의 정의는 주의해야한다. 단순히 P의 반대가 아니기 때문이다. NP란, Polynomial Time에 Problem에 대한 특정한 Solution이 실제 정답에 해당하는지 판단할 수 있는 문제들의 집합이다. 역시나 위에서처럼 엄밀히 정의하면, Non-Deterministic Algorithm으로 Polynomial Time 내에 해결할 수 있는 문제들의 집합이다.
Decision Problem의 범주 내에 NP라는 부분집합이 있으면, P는 NP 내에 속해있는 부분집합이라고 그 관계를 인지할 수 있다.
NP-Hard
임의의(모든) NP문제가 어떠한 문제 x로 Polynomial Time Reduction이 가능하면 그러한 문제 x를 NP-Hard라고 한다. 아래에서 설명하는 SAT 문제가 아주 대표적인 NP-Hard이다. NP-Hard에 해당하는 문제 중 단 하나라도 P에 속함을 증명하면 P = NP라는 밀레니엄 문제를 해결할 수 있게 된다.
※ Polynomial Time Reduction : 해결하는데 어려움을 겪고 있는 문제 A를 Polynomial Time Algorithm을 거쳐 (해결 방법이 알려진) 문제 B로 변환할 수 있으면 이를 Polynomial Time Reduction 했다고 볼 수 있고, 이 관계에서 문제 B가 문제 A보다 더 (계산적으로) 어렵다고 볼 수 있다.
SAT
SAT는 충족가능성 문제, 즉, Satisfiability Problem을 의미한다. 주어진 논리식을 참으로 만드는 변수의 진리값 조합이 존재하는지 안하는지에 대한 문제이다. NP Class의 모든 문제 이상으로 SAT가 (계산이) 어려움이 알려져 있다(Cook-Levin Theorem). 즉, 위의 정의들에 따라 SAT는 NP-Hard이다. 한편, 충족가능성 문제는 결정 문제이고, 다항시간 내에 그 답의 유무를 판단할 수 있음이 명백하므로 NP이기도 하며, 이 말은 즉슨, 아래의 정의에 따라 NPC이기도 하다.
NPC
NP이면서 NP-Hard이면 NP-Complete, 즉, NPC에 해당한다. 즉, 다른 모든 NP 문제들이 다항 시간 내에 Reduce할 수 있는 NP 문제가 곧 NP-Hard인 것이다.
앞서 SAT는 왜 배운 것일까? 바로, 이 SAT로부터 다양한 NPC를 도출할 수 있기 때문이다. 이러한 과정을 통해 다음과 같은 대표적인 NPC들이 알려져 있다. ex) TSP(Travelling Salesperson Problem), HC(Hamiltonian Cycle Problem), VC(Vertex Cover Problem), Graph-Coloring, Knapsack Problem, Clique Problem, Subset Sum Problem, Isomorphism Problem 등등
~> 모두 학부 알고리즘 수업에서 한 두 차례 이상 보거나 학습했던 문제들임을 알 수 있다. 이들에 대해 학부 수준의 수업을 이미 해봤으므로, 이제는 이들을 손에 익힐 수 있도록 노력하자.
