[CM301] 14. NP-hard: 최적화 문제 I (Optimization problem I)

결정 문제와 최적화 문제

 P와 NP에 대해 소개하면서 결정 문제에 대한 이야기를 했었습니다. 이때까지 다루었던 문제 대부분은 주어진 조건에서 최댓값 혹은 최솟값을 구하는 최적화 문제^{Optimization Problem} 문제였는데, 이런 문제들은 직접 복잡도를 비교하기 어렵습니다. 그래서 계산 복잡도 이론에서는 최적화 문제를 예/아니오로만 답할 수 있는 결정 문제^{Decision Problem}로 바꾸어 복잡도를 계산하게 되었고요.

 원본이 되는 최적화 문제를 풀 수 있다면, 그에 대한 결정 문제도 자연스럽게 풀리게 됩니다. 문제 상황에서 가능한 최솟값/최댓값을 알게 된다면, 결정 문제에서 물어보는 ‘상한/하한을 넘을 수 있는지’도 바로 답할 수 있게 되니까요.

 즉, 결정 문제는 최적화 문제로 환원할 수 있습니다.

\[\text{결정문제(DEC)} \leq_p \text{최적화문제(OPT)}\]

 이는 두 가지 중요한 사실을 알려줍니다. 첫째는 결정 문제가 최적화 문제보다 어렵지 않다는 것입니다. 최적화 문제를 풀 수 있다면, 반드시 결정 문제도 풀 수 있기 때문입니다. 둘째는 만약 결정 문제가 NP-hard라면, 최적화문제도 NP-hard라고 할 수 있다는 것입니다.

 앞서 최적화 문제는 직접 복잡도를 비교하기 어려워 결정문제로 바꾸어 해결한다고 했었죠. 이 두 번째 사실이 그 방법을 알려줍니다. 최적화 문제를 결정 문제로 바꾸고, 그 결정 문제가 NP-hard임을 보인다면 우리는 그 최적화 문제가 NP-hard 임을 보일 수 있게 되는 것이죠.

최적화 문제는 NP-complete인 것까지 보이지 않습니다. 최소/최대를 출력하는 최적화 문제에서 NP의 정의에 따라 출력값이 ‘예/아니오’임을 검증하는 것은 적절하지 않기 때문입니다.

 이제부터 결정문제의 NP-completeness를 이용해 최적화 문제들이 왜 ‘어려운지’를 증명해보도록 합시다.

독립 집합 (Independent Set)

  방향이 없는 그래프 $G=(V, E)$를 생각해봅시다. 만약 정점의 부분집합 $W \subseteq V$에 대해 어느 점도 서로 연결되어 있지 않다면, $W$를 독립 집합^{Independent Set}이라고 합니다.

 임의의 그래프가 주어졌을 때, 가장 큰 독립집합을 구하는 문제를 독립 집합 문제^IND-SET라고 하겠습니다.

결정 문제

 이 최적화 문제는 다음과 같은 결정 문제로 바꿀 수 있습니다.

DEC(IND-SET): 주어진 그래프 $G=(E, V)$에서 크기 $k$ 이상인 독립 집합이 존재하는가?

 이 문제는 NP입니다. 크기 $k$ 이상이 되는 정점의 집합 $W$를 준다면, 정말로 그 집합이 독립 집합인지는 다항 시간 안에 쉽게 확인할 수 있기 때문입니다.

NP-hard임을 보이기

 이 결정 문제가 NP-hard임을 보이기 위해, 이전 절에서 NP-complete임을 보였던 3-SAT 문제를 써먹어 봅시다. 만약 3-SAT를 DEC(IND-SET)로 환원할 수 있다면, DEC(IND-SET)가 NP-hard임을 보일 수 있겠죠.

\[\text{3-SAT} \leq_p \text{DEC}(\text{IND-SET}) \; ?\]

 3-SAT는 3-CNF(세 개의 항이 OR 연산으로 묶인 논리항)로 이루어진 논리식을 다루고, DEC(IND-SET)는 그래프를 다룹니다. 그러니 논리식을 그래프로 바꾸는 작업을 해보겠습니다.

 목표는 논리식이 참이 되는 입력값이 있을 때, 그 입력값이 크기 k 이상인 독립집합을 나타내도록 하는 것입니다. 논리식에서 a의 값이 1(참)이면, 그래프에서 a가 독립 집합에 속하는 식인 것이죠.

 3-CNF는 세 개의 항이 OR 연산으로 묶인 논리항입니다. 그 말은 즉 세 개 중 하나만 참이어도 논리항 전체가 참이 될 수 있다는 뜻입니다. 그러니 세 항을 모두 연결한 그래프를 만들어봅시다. 이렇게 되면 하나의 항만 참(1)일 때, 그에 해당하는 점과 이어지는 다른 점은 존재하지 않게 됩니다. 즉, 크기 1인 독립 집합이 만들어집니다.

 여기서 조건을 하나 더 추가해야 합니다. 어떤 항 $a$와 그 항의 부정 $\neg a$는 동시에 참이 될 수 없기 때문입니다. 그러니 이 둘을 선으로 연결해주면, 독립 집합의 규칙에 어긋나게 되므로 동시에 선택되는 일은 없을 것입니다.

 논리항은 n개(예시에서는 4개)의 3-CNF가 AND 연산으로 묶인 상태입니다. 즉, 논리항 전체가 참이 되기 위해서는 각 3-CNF가 모두 참(1)이 되어야 합니다. 그렇기 때문에 각 3-CNF에 대응되는 그래프에서는 각각 하나의 점이 선택될 것입니다.

 따라서 이 방식대로 논리식을 그래프로 변환한다면, 그래프에서 크기 k=n인 독립집합을 선택함으로서 3-CNF가 n개인 논리식이 참이 되는 입력값을 찾을 수 있게 됩니다. 그래프에서 선택한 k의 크기에 따라 풀 수 있는 논리식의 3-CNF 개수가 결정되는 셈입니다. 이제 우리는 3-SAT 문제를 DEC(IND-SET) 문제로 환원할 수 있게 되었습니다!

\[\text{3-SAT} \leq_p \text{DEC}(\text{IND-SET})\]

 그래프를 변환하는 과정은 다항시간이 소요되며, 3-SAT는 NP-complete입니다. 따라서, DEC(IND-SET)은 NP-hard입니다.

결론

 결정문제 DEC(IND-SET)은 NP이고 NP-hard이므로 NP-complete입니다. 따라서, 최적화 문제 IND-SET은 NP-hard, 즉 어렵습니다.

클리크 (Clique)

 어떤 그래프 $G=(V, E)$의 하위 그래프 $G’=(V’,E’)$가 모든 점이 서로 연결되어 있는 완전 그래프^{Complete Graph}라면, $V’$를 클리크^Clique라고 부릅니다. 바로 전에 보았던 독립 집합과는 정반대의 개념이라고 볼 수 있습니다.

 임의의 그래프가 주어졌을 때, 점의 개수가 가장 많은 클리크를 찾는 문제를 클리크 문제^Clique라고 하겠습니다.

결정 문제

  이 최적화 문제는 다음과 같은 결정 문제로 바꿀 수 있습니다.

DEC(Clique): 주어진 그래프 $G=(V, E)$에서 점의 개수가 $k$ 이상인 클리크가 존재하는가?

 이 문제는 NP입니다. 점의 개수가 $k$ 이상이 되는 정점의 집합 $W$를 준다면, 정말로 그 그래프가 완전 그래프 인지는 다항 시간 안에 쉽게 확인할 수 있기 때문입니다.

NP-hard임을 보이기

 이 결정 문제가 NP-hard임을 보이기 위해, 다시 3-SAT 문제를 사용해봅시다. 독립 집합 문제와 마찬가지로 3-SAT를 DEC(Clique)로도 환원할 수 있다면, DEC(Clique)가 NP-hard임을 보일 수 있겠습니다.

\[\text{3-SAT} \leq_p \text{DEC}(\text{Clique}) \; ?\]

 클리크도 그래프와 관련된 문제이니, 역시 논리식을 그래프로 바꾸는 작업을 해보겠습니다. 이번에는 논리식에서 참(1)으로 선택한 항을 모으면 완전 그래프가 되도록 만들 것입니다.

 독립 집합 문제와는 반대로 그래프를 구성해주면 됩니다. 같은 3-CNF으로 묶인 항들은 서로 연결하지 않으며, 서로 부정인 관계($a$와 $\neg a$)또한 연결 해주지 않습니다. 그 외에 나머지 항들은 모두 연결 해줍니다.

 이제 이 그래프에서 점 $k$개로 이루어진 클리크를 찾으면, 3-CNF $k$개로 이루어진 논리식을 참으로 만드는 입력값을 찾을 수 있게 됩니다.

이제 우리는 3-SAT 문제를 DEC(Clique) 문제로도 환원할 수 있게 되었습니다!

\[\text{3-SAT} \leq_p \text{DEC}(\text{Clique})\]

 그래프를 변환하는 과정은 다항시간이 소요되며, 3-SAT는 NP-complete입니다. 따라서, DEC(Clique)는 NP-hard입니다.

결론

 결정문제 DEC(Clique)은 NP이고 NP-hard이므로 NP-complete입니다. 따라서, 최적화 문제 Clique는 NP-hard, 즉 어렵습니다.

독립집합과 클리크

 두 문제는 서로 반대되는 개념입니다. 독립집합은 서로 연결되어서는 안되고, 클리크는 서로 튼튼하게 연결되어 있죠. 그렇기 때문에, 두 문제는 서로 환원할 수도 있습니다.

 그래프 $G=(V, E)$에서 선을 반전시킨 상보적인 그래프 $\bar{G}=(V, \bar{E})$를 생각해봅시다. 그러면 $G$에서 클리크를 이루던 점들은 $\bar{G}$에서 독립집합을 이루게 됩니다.

 그 반대로 마찬가지입니다. 그래프의 선을 반전시킴으로 한 문제를 다른 문제로 환원시킬 수 있게 되는 것입니다.

 이번 절에서는 서로 정반대인 두 문제에 대한 최댓값 최적화 문제에 대해 다뤄보았습니다. 다음 절에서는 최솟값 최적화 문제들에 대해 다뤄보겠습니다.