[알고리즘 - 이론] NP-Complete, NP-Hard

P = NP임을 증명하려면 NP에 속한 각각의 문제에 대해 문제를 풀 수 있는 다항 시간 알고리즘을 찾아야 합니다.

하지만 이 작업은 단순화할 수 있습니다.
즉, 많은 문제 중에서 하나만 다항 시간 알고리즘을 찾으면 됩니다.

하나만 다항 시간 알고리즘을 찾으면, 나머지 문제들도 마찬가지로 P에 속하게 되는 NP-Complete에 대해 알아보겠습니다.

우선 알아보기 전에 이론의 기초가 되는 CNF-Satisfiability에 대해 알아봐야 합니다.

그리고 마지막으로 지금까지 결정 문제에 대해서만 NP, P를 따졌는데, 이제는 최적화 문제까지 확장한 NP-Hard에 대해서도 알아보겠습니다.

---

1. CNF-Satisfiability

CNF ~ 는 Conjunctive Normal Form의 약자로, 논리식 사이에 논리 연산자를 끼운 절의 나열입니다.
(A and B) or C 같은 경우가 CNF의 예시가 됩니다.

이때 CNF 논리식과 변수에 대입할 참 값을 입력으로 받아서 그 대입에 대해 그 논리식이 true인지 검증하는 다항 시간 알고리즘은 쉽게 작성할 수 있습니다.
고로 이 알고리즘은 필연적으로 NP입니다.

그러나 이 문제를 푸는 다차시간 알고리즘을 아직 아무도 찾지 못했고, 또 풀 수 없다고 아무도 증명하지 못했습니다.
우선 위의 경우 변수가 A, B, C이므로 2^3개의 변수가 들어가야 하고, 결과가 True가 되는 조합을 찾아라 라는 문제라면 이는 필연적으로 지수 시간을 가지기 때문입니다.

하지만 어떤 값을 주고 논리식의 결과가 뭔지 알아내라 하는 것은 다항 시간이 맞습니다.
따라서 이 문제가 P에 속할지도 모릅니다.

아무튼 CNF를 이해했다면, 이제 Transformation Algorithm에 대해 알아봐야 합니다.

---

2. Transformation Algorithm (변환 알고리즘)

결정 문제 A를 풀려고 하고, 결정 문제 B를 푸는 알고리즘이 있다고 가정합시다.
그리고 문제 B를 푸는 알고리즘이 y에 대해서 "예'라고 답하면,
문제 A에 대한 답도 "예"가 되도록 문제 A의 모든 사례 x에서 문제 B의 사례 y를 만들어내는 알고리즘을 작성할 수 있다고 가정합시다.

변환 알고리즘이라고 하는 이 알고리즘은 문제 A의 모든 사레를 문제 B의 사례로 매핑하는 함수입니다.

간단하게 말해서 문제 B를 푸는 알고리즘을 가지고, 변환 알고리즘을 적용하여 문제 A를 푸는 알고리즘을 만들어내는 것이, 바로 Transformation Algorithm이라고 할 수 있습니다.

---

3. CNF와 Transformation Algorithm, NP-Complete

3 CNF라는 것은 3개의 논리 변수를 이용하여 논리식을 만든 것을 의미합니다.
참고로 3 CNF 문제는 NP에 속합니다.
근데 이게 변환 알고리즘과 무슨 관련이 있을까요?

바로 3 CNF를 변환하면 해밀턴 회로, 부분 집합의 합, 0-1 Knapsack 문제를 만들 수 있기 때문입니다.
왜냐고요?
간단하게 부분 집합의 합으로 생각해봅시다.

{a, b, c, d}라는 집합이 있다고 가정해봅시다.
이때 a가 속할지 안 속할지는 true, false로 나눌 수 있습니다.
감이 오시죠?
나머지 원소도 모두 true, false로 나눌 수 있습니다.

즉 3 CNF 문제를 sum of subset의 문제로 변환한 것입니다.

근데 sum of subset의 원소는 3개가 넘을 수도 있는데 왜 변환이 가능하다는 걸까요
만약 원소가 6개라면 2개씩 묶어서 3개의 원소로 표현할 수 있기 때문입니다.

또 부분 집합의 합 문제를 변환하여 0-1 knapsack 문제를 만들 수도 있습니다.

이렇게 서로 얽혀있고, 서로 변환이 가능한 문제들의 집합을 NP-Complete라고 합니다.

고로 P = NP를 만족하는 문제 하나만 찾아도, 같은 NP-Complete에 속하는 다른 문제들도 다항 시간 내에 풀 수 있습니다.

즉 NP-Complete는 하나의 NP 문제에서 변환하여 만들 수 있는 다른 문제들의 모든 집합이라고 보면 될 것 같습니다.

참고로 2 CNF SAT는 P입니다.

---

4. NP-Hard

지금까지 우리는 결정 문제에 대해서만 P, NP를 생각했었습니다.
즉 최적화 문제 -> 결정 문제로 변경하여 생각했었으므로, 이제는 최적화 문제에 대해서도 알아볼 필요성이 있습니다.

NP-Hard란 것은 최적화 문제를 결정 문제로 변경했을 때, NP-Complete한 문제들을 말합니다.

즉 최적화 문제의 집합이긴 한데, 결정 문제로 변환하면 NP-Complete한 문제들을 뜻합니다.

따라서 다항 시간 알고리즘이 있는 문제를 NP-Hard라고 증명할 수 있다면, P = NP를 증명한 것과 다름이 없습니다.

즉, NP-Complete는 Guessing에선 비결정적이면서, Verify 할 때는 다항 시간 내에 결정이 가능하면서, 다른 문제들로 변환이 가능한 문제들을 말합니다.

따라서 이 문제가 NP-Hard 하다는 것은 다항 시간 내에 해결 가능한 방법을 아직 못 찾은 문제라고 말할 수 있겠습니다.

---

5. 그렇다면 NP-Hard 문제는 어떻게 풀까?

NP-Hard 문제를 푸는 다항 시간 알고리즘이 없는데 어떻게 해야 할까요?
만약 지금까지 찾은 알고리즘이 지수 시간 알고리즘이라면 어떻게 해야 할까요?

답은 간단합니다.
정확한 해답은 그냥 포기해버리고, 근사치, approximation을 찾는 겁니다.

따라서 n이 너무 크면 오래 걸리니까 그냥 휴리스틱하게 찾는 방법이라고 볼 수 있습니다.

하지만 휴리스틱으로 풀 때는 해당 근사치가 얼마나 정답에 근사한지를 알 수 있어야 하므로, 아무 휴리스틱 알고리즘을 쓸 수는 없습니다.

예를 들어 TSP를 근사하게 풀어봅시다.

우선 기준을 정해야 하므로,
우리가 구한 minapprox < 2 * mindist 라고 합시다.

삼각형 부등식을 이용해야 합니다.
삼각형이 있을 때, 가장 긴 간선은 다른 두 간선의 합보다 작거나 같아야 합니다.

물론 같다면 일직선이 되겠죠

아무튼 이 방식을 이용하여 TSP의 근사치를 찾아봅시다.

기본적인 방법은 아래와 같습니다.

• 해당 그래프의 MST를 구한다
• 이 MST를 Directed로 변경하여 트리를 두 번 횡단하여 모든 도시를 방문하는 경로를 구축한다.
• 지름길을 택하여 마디를 두 번 방문하지 않는 경로를 구축한다.

가 되겠습니다.

얘가 왜 삼각 부등식이랑 기준에 들어맞는지를 알아봅시다.

a -> c = 2이고,
c -> b = 2라고 가정해봅시다.

그러면 mindist는 4가 됩니다.

이때 a -> b = 3라고 한다면 이는 지름길이 되고, 삼각 부등식도 성립하므로 가능한 경로 중에 가장 최적에 근사한 경로가 됩니다.

만약 a -> b가 5라면 이는 지름길이 되지 않고, 삼각 부등식도 성립하지 않습니다.


이를 연장하여

유클리드 좌표계에서 점이 있을 때의 TSP 문제를 근사하게 풀어보면,

• 모든 점이 연결된 완전 그래프를 생성한다.
• 여기서 MST를 생성한다.
• 이 MST를 Directed 그래프로 변경한다.
• 해당 시작점으로부터 시작하여, 마디를 중복으로 방문하는 경로들은 없애고, 지름길을 찾아서 연결한다.

끝 ......