[CM301] 12. NP-hard & NP-complete

 P와 NP에 대해 다시 한 번 짚고 넘어갑시다.

• P(Polynomial time) : 다항시간 안에 풀 수 있는 결정 문제의 분류

• NP(Nondeterministic Polynomial time) : 다항시간 안에 검증할 수 있는 결정 문제의 분류

 이 두 부류의 포함관계를 밝혀내는 것이 P=NP 문제였죠. P와 NP의 범위가 완전히 동일하거나, P가 NP에 포함되기만 하거나 결과는 둘 중 하나입니다.

 P=NP 문제에 대해 더 설명하려면 NP에 대해 자세히 다뤄볼 필요가 있습니다. 하지만 그 전에, 새로운 개념을 정의하는데 도움 될 만한 개념 하나를 먼저 살펴봅시다.

환원 (Reduction)

 9절 ‘동적 계획법(Dynamic Programming)’에서 등장한 가장 긴 증가 수열에 대한 문제를 기억하나요? 정수 수열이 주어져 있을 때, 순서관계를 지키며 증가하는 하위 수열 중 나올 수 있는 가장 긴 길이를 구하는 문제였습니다.

 우리는 이 수열을 방향이 있는 비대칭 그래프(DAG)로 나타내어 DAG 경로 중 가장 긴 길이를 구하는 문제로 바꾸어 풀었었죠.

 ‘가장 긴 증가 수열’과 ‘가장 긴 DAG 경로’는 엄연히 다른 문제지만, 우리가 수열을 DAG로 변환하는 과정을 거침으로서 동일한 문제가 된 셈입니다. 이렇게 문제를 약간 손 봄으로서 다른 문제로 바꾸는 것을 환원(Reduction)이라고 부릅니다. 위 예시에서는 ‘가장 긴 증가 수열’ 문제가 ‘가장 긴 DAG 경로’ 문제로 환원되었다고 말할 수 있습니다.

 간단한 예시를 하나 더 들어볼까요? ‘가장 긴 DAG 경로’ 문제는 ‘가장 짧은 DAG 경로’ 문제로도 환원할 수 있습니다. 그래프의 모든 가중치 부호를 반대로 역전하면 되니까요.

 우선 이 정도면 되었습니다. 이제 NP에 대해 좀 더 살펴봅시다!

NP-hard

 어떤 문제 $\Pi$에 대해 모든 NP 문제가 다항 시간 안에 $\Pi$로 환원될 수 있다면, $\Pi$는 NP-hard라고 합니다.

 네, 이렇게 이야기하면 한 번에 이해하기 어려우니 조금씩 풀어서 생각해봅시다. 모든 NP 문제가 NP-hard 문제 $\Pi$로 환원될 수 있다고 한다면, NP 문제들은 전부 $\Pi$를 푸는 것 처럼 생각할 수 있다는 말이 됩니다.

 $\Pi$는 다항시간 알고리즘이 있을 수도 있고, 없을 수도 있고, 심지어 풀 수 있는지도 모를 수 있습니다. 확실한 것은, $\Pi$를 풀 수 있으면 NP 문제들도 풀 수 있다는 것입니다. 반대로 $\Pi$를 풀 방법이 없다고 NP 문제들도 풀 수 없는 것은 아닙니다. NP 문제들은 어디까지나 $\Pi$로 환원 가능할 뿐이기 때문에, 다른 방법을 사용하면 풀 수 있을지도 모르니까요.

 결론적으로 말하자면, NP-hard는 ‘최소한 모든 NP 문제들 만큼 어려운 문제’의 집합이라고 생각할 수 있습니다.

NP-hard임을 보이기

 어떤 문제 A가 NP-hard임을 보이고 싶다면, 다른 NP-hard 문제 B를 가져와 증명할 수 있습니다.

 NP-hard인 문제 B를 A로 환원하여 푼다고 합시다. 만약 A가 다항시간의 알고리즘을 가지고 있다면, B 또한 다항시간의 알고리즘을 가지게 됩니다(문제를 A로 바꾸어 풀 수 있으니까요). B는 NP-hard 이므로, 다른 NP 문제들 또한 모두 다항시간의 알고리즘을 가지게 됩니다. 따라서 A가 다항시간의 알고리즘을 가지면 모든 NP 문제들도 다항시간의 알고리즘을 가지게 되는 셈입니다. 따라서 A는 NP-hard임을 보일 수 있습니다.

 답은 간단합니다. 그건 여러분이 직접 만들어야 합니다.

 즉, B를 A로 바꾸는 알고리즘을 직접 설계해서 보여줘야 하는 것이 해당 증명의 요지라고 할 수 있습니다. 앞으로도 다양한 문제에 대해 NP-hard임을 보이게 될텐데, 이들 모두 다른 NP-hard 문제로 환원하는 과정을 보임으로서 NP-hard임을 증명하게 될 것입니다.

NP-hard와 P=NP

 만약 NP-hard 문제중 다항시간 알고리즘을 가진 문제가 있다면 어떻게 될까요? 이말은 곧 모든 NP 문제들 또한 해당 다항 시간 알고리즘으로 해결할 수 있다는 뜻입니다. 즉, 모든 NP 문제가 P 문제(P=NP)가 되는 것이죠! 그렇기 때문에 ‘NP-hard 문제가 다항 시간 알고리즘을 가지는가’는 꽤나 중요한 지점이 됩니다.

 하지만 문제가 있다면… 너무 어렵습니다. 정의 자체가 ‘최소한’ NP 문제들 만큼 어려운 문제들이니, 그보다 더 어려운 문제들도 있다는 뜻입니다. 여기서 다항시간의 알고리즘의 존재 여부를 논하는 것은 상당히 힘든 일입니다. 그래서 우리는 좀 더 특수한 경우에 대해 다뤄볼 것입니다.

NP-complete

 어떤 문제 $\Pi$가 NP인 동시에 NP-hard이기도 하다면, $\Pi$는 NP-complete라고 합니다. NP-hard가 ‘적어도 모든 NP 만큼은 어려운 문제’라고 했으니, NP-complete는 ‘NP 중에서 가장 어려운 문제’가 되는 셈입니다.

NP-complete임을 보이기

 정의한 것 처럼 NP-complete의 증명은 총 두 가지를 보이면 됩니다.

• 문제가 NP이다

• 문제가 NP-hard이다

 NP를 보이는 경우 다항시간 안에 해당 문제를 검증할 수 있는 입력값이 존재함을 보이면 됩니다. NP-hard를 보이는 경우는 앞에서 이미 설명했으니, 그대로 증명과정을 수행하면 되겠죠.

NP-complete와 P=NP

 NP-hard와 동일하게 NP-complete 문제 중에서 다항 시간 알고리즘을 찾을 수 있다면, P=NP임을 증명할 수 있습니다. 단, NP-hard 보다는 문제들이 쉬우면 쉽지 더 여려워지지는 않을거에요.

 이때까지 살펴본 문제들의 범위를 정리해보면, 다음과 같이 나타낼 수 있습니다. NP-hard와 NP는 NP-complete라는 교집합을 가지며, NP는 P를 포함하고 있는 형태죠.

 만약 여기서 P=NP임이 밝혀진다면, 이렇게 바꿔 그릴 수 있게 됩니다. NP-complete에 다항 시간의 알고리즘이 존재한다면, NP-complete도 P가 될 수 있으니까요.

P=NP를 보이기 위해서

 이제 우리는 P=NP임을 판별하기 위해서 무엇을 해야 하는지 좀더 구체적으로 알게 되었습니다. 모든 NP 에 대해 P임을 확인하는 것은 너무 어려운 일입니다. 그래서 NP 중에서도 가장 어려운, 그래서 NP-hard라고 할 수 있는 NP-complete 문제에 한해서 다항시간의 알고리즘이 있는지 찾아보아야 할 것입니다.

 그러면 이제 다음으로 살펴봐야 할 주제가 무엇인지 알 수 있죠. 바로 어떤 문제가 NP-complete인지 판별하는 것입니다.