[알고리즘] NP-Complete와 NP-Hard

 

 

 

 

🧐 NP-Hard(NP 난해)

Problem X가 다음 조건을 만족하면 이를 NP-Hard라 부릅니다.

어떠한 Y $\in$ NP 에 대해서도, Y $\leq_p$ X 가 성립니다.

즉 NP에 속한 어떠한 문제에 대해서도 X로의 Polynomial Time Reduction이 존재해야 합니다.

 

 

Halting Problem(정지 문제)은 NP-Hard에 속하는 대표적인 문제입니다.

 

 

 

 

 

 

 

 

🧐 NP-Complete(NP 완전)

Problem X가 다음 조건을 만족하면 이를 NP-Complete라고 부릅니다.

1) 어떠한 Y $\in$ NP 에 대해서도, Y $\leq_p$ X 가 성립니다.
2) X $\in$ NP 여야 합니다.

즉 NP-Complete는 NP-Hard이면서 NP인 문제들을 의미합니다.

 

Halting Problem(정지 문제)은 NP-Hard에 속하지만 NP 문제는 아닙니다.

따라서 NP-Complete가 아닙니다.

 

 

 

 

 

 

 

 

🧐 P = NP를 증명하는 방법

어떤 NP-Complete에 속한 Problem X에 대하여,

 

만약 P = NP라면, X 를 Polynomial time 안에 해결 가능합니다. 또한 역 역시 성립합니다.

 

즉 NP-Complete 에 속한 문제를 Polynomial time 안에 해결 가능하면, P = NP를 증명할 수 있습니다.

 

이에 대한 증명은 다음과 같습니다.

 

👉 증명

(1) X가 polynomial time 안에 해결 가능하다 하겠습니다.

X는 NP-Complete 이므로 NP에 속한 임의의 Problem Y에 대하여, Y $\leq_p$ X 가 성립합니다.

따라서 Y를 해결하는 polynomial time algorithm 또한 존재하므로, Y는 P에도 속합니다.

 

 

(2) X는 NP에 속해 있으므로, NP = P 라면 X는 P에도 속하게 됩니다.

즉 X를 해결하는 polynomial time algorithm이 존재하게 됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

🧐 Cook-Levin Theorem

모든 SAT 문제는 NP-complete라는 것을 증명한 정리입니다.

즉 이를 통해 3-SAT 역시 NP-Complete인 것을 증명할 수 있습니다.

 

 

 

 

 

 

 

 

 

🧐 NP - Complete를 증명하는 방법

일반적으로 어떤 Problem X가 NP-Complete 임을 증명하는 단계는 다음과 같습니다.

1. X가 NP에 속해 있음을 증명합니다. (매우 중요합니다.)

2. 어떤(이미 알려진) NP-Complete Problem Y에 대하여, Y $\leq_p$ X 를 증명합니다.

2를 증명할 경우, 임의의 NP에 속한 문제 Z에 대해서, Z $\leq_p$ Y $\leq_p$ X가 되고,

따라서 Z $\leq_p$ X 임을 알 수 있습니다.

 

 

Reduction에 대해 알아보는 글에서, 다음을 증명하였습니다.

(3-SAT) $\leq_p$ (Independent Set) $\leq_p$ (Vertex Cover) 
(3-SAT) $\leq_p$ (Independent Set) $\leq_p$ (Clique)

 

이때 3-SAT이 Cook-Levin Theorem에 의해 NP에 속하므로, Independent Set, Vertex Cover, Clique 모두 NP에 있음을 증명할 수 있습니다.