알고리즘(10) : NP-완전 이론 - 결정, P, NP, NP-완전, NP-hard 문제
NP-완전 이론이란?
NP-완전이론은 어떤 문제를 현실적인 시간 안에 해결할 수 있는가에 관한 이론이다.
이 의문점에서 시작하여, 문제의 종류, 파생되는 여러 개념들에 대해 알아볼 것이다.
먼저 우리는 문제를 얼마나 다루기 힘드냐(해결가능성)에 따라서 분류해볼 수 있다.
여기서 '다루기 힘들다'라는 말은 다항식으로 시간복잡도를 나타낼 수있는 알고리즘을 찾을 수 없는 경우를 이야기한다.
우선 다루기 힘든 문제를 정의하기 전에, 풀 수 있는 문제와 풀 수 없는 문제를 정의해야 한다.
풀 수 있는가 없는가는 기존에 아는 정의와 같다. 실제로 해결할 수 있는가(해 자체를 시간이 걸려도 찾을 수 있는가)이다.
이런 문제들은 보통 모순이 발생해서 풀지 못하는 경우로, 대표적인 예시는 '종료 문제'와 '힐베르트의 10번째 문제'이다.
이후 종료 문제에 대해 간략하게 설명할 것이다.
풀 수 있는 문제는 당연히 해를 찾을 수 있는 문제를 이야기한다. 시간이 빨리 걸리든 늦게 걸리든, 해를 찾을 수 있는 방법이 있다면 그 문제는 풀 수 있는 문제에 속한다.
그리고 여기서 풀 수 없는 문제는 다루기 힘든 문제이다. 문제를 풀 수 없으니 당연히 알고리즘도 찾을 수 없기 때문이다.
그럼 반대로 다루기 쉬운 문제는 다항식 시간으로 표현되는 문제 해결 알고리즘이 존재하는 문제들로, 우리가 앞에서 배운
정렬문제($O(nlogn)$), 행렬곱($O(n^3)$) 등이 있다.
이런 시간복잡도를 '현실적인 시간'이라고 부르기도 한다. 반대로 비현실적 시간은 지수, 팩토리얼 시간이 이에 해당한다.
그럼 마지막으로 남은 부분은 바로 풀 수는 있지만 다루기 쉽지 않은 문제들이 있다.
정확하게 이야기하면 다루기 힘들다고 증명되지도 않았고, 다항식 시간 알고리즘도 발견하지 못한 문제가 여기에 속한다.
풀 수는 있지만 현실적인 시간 내에 푸는 것이 불가능할 것으로 판단되는 문제들로, NP-완전 문제가 여기에 속해있다.
이런 문제들에 대해 연구해서 나오게된 이론이 NP-완전 이론이라고 생각하면 되겠다.
결정 문제(Decision Problem, 판정 문제)
결정 문제는 질문에 대해서 대답이 '예' 혹은 '아니오'로 이루어지는 문제이다.
예를 들어, 질문이 'x와 y가 있을 때, y는 x로 나누어 떨어지는가?'에 대한 대답은 예와 아니오뿐일 것이다.
이런 결정 문제를 푸는 알고리즘이 있으면, 그 문제는 결정 가능하다고 하고, 없으면 결정 불가능하다고 한다.
결정 불가능한 문제의 대표적인 예시가 바로 위에서 언급한 '종료 문제'이다.
다루기 힘들다고 증명된 문제이기도 하며, 풀 수 없는 문제이기도 하다. 여러 복잡한 용어 정리를 잘 해두자...
종료 문제는 어떤 프로그램 P가 정상적으로 수행되어서 종료하는지를 결정하는 문제이다.
앨런 튜링이 해당 문제가 결정 불가능함을 증명했는데, 과정은 다음과 같다.
먼저 종료 문제를 풀 수 있는 알고리즘 Halt()가 존재한다고 가정하자.
이 알고리즘은 프로그램을 입력으로 받아 종료한다면 '예', 아니면 '아니오'라는 결과를 반환해줄 것이다.
이를 사용해 nonsense() 알고리즘을 만들 수 있는데, 구성은
nonsense() {
if(Halt(nonsense()) while(true) do something;
}
이렇다. 만약 nonsense 알고리즘이 정상적으로 종료된다면, Halt는 true를 반환하므로 nonsense가 종료되지 않는다.
nonsense 알고리즘이 종료되지 않는다면, Halt는 false를 반환하므로 nonsense가 종료된다.
두 경우에 모두 모순이 발생하므로, Halt라는 알고리즘은 존재할 수 없다. 따라서, 종료 문제는 풀 수 없다.
결정 문제와 주로 비교되는 것이 최적화 문제인데, 최적화 문제는 앞에서 배운 최적의 해를 찾는 문제이다.
이때 한 개념이 나오는데, 최적화 문제를 푸는 다항시간 알고리즘이 있다면, 그 알고리즘으로부터 해당 최적화 문제를
결정 문제처럼 형태를 변환할 경우 그 결정 문제에 대한 다항시간 알고리즘도 쉽게 구해낼 수 있다는 것이다.
최적화 문제를 결정 문제로 바꾸는 예시를 들자면, 인접한 두 정점의 색을 다르게 칠하는 그래프 색칠하기 문제의 경우,
최적화 : 인접한 두 정점이 같은 색이 아니도록 색칠하는 데 필요한 색의 최소 가지수를 구하는 문제
결정 : m가지의 색을 사용해서 인접한 두 정점이 같은 색이 되지 않도록 그래프를 색칠할 수 있는지를 대답하는 문제
이후 서술할 내용부터는 설명하기도 쉽고, 이해하기도 더 쉬운 결정문제로 다루도록 하겠다.
결정론적 알고리즘(Deterministic Algorithm)
결정론적 알고리즘은 내가 예측한 그대로 동작하는 알고리즘이다.
즉, 같은 입력이 들어오면 항상 같은 과정을 거쳐 똑같은 결과를 내는 알고리즘을 이야기한다.
수학의 함수가 이런 알고리즘에 해당한다. 특정한 입력이 들어오면 언제나 동일한 과정을 거쳐 동일한 결과가 나온다.
$f(x) = x+1, f(1)=2, f(2)=3, f(k)=k+1$과 같다.
이런 알고리즘의 특징은, 그 다음 단계의 결과를 정확하게 예측할 수 있다는 것이다.
그렇다면 반대로 비결정론적 알고리즘(Non-deterministic algorithm)도 존재한다.
결정론적 알고리즘과 반대로 같은 입력이 주어지더라도 매 실행마다 다른 결과를 내놓는 알고리즘이다.
알고리즘을 수행하는 내부, 외부환경이 변수로 알고리즘 동작에 영향을 주게 된다.
특히 시간과 같은 값이 변수로 사용될 때 비결정론적 알고리즘이 되는 경우가 많다.
당연하게도, 모든 문제가 결정론적 알고리즘을 찾아낼 수가 있는 것은 아니다.
문제의 분류(P와 NP문제)
NP-완전 문제에 대해 알려면 가장 먼저 문제를 구분할 수 있어야한다.
P문제는 다항식 시간복잡도를 가진 알고리즘으로 해결되는 문제 집합(Polynomial)을 이야기한다.
다루기 쉬운 문제로도 정의할 수 있으며, 결정 문제 기준으로는 다항시간안에 '예' 혹은 '아니오'를 내놓는 문제이다.
$O(n^k)$의 시간복잡도에 해당하는 문제들이 P문제에 속한다.
그럼 NP문제도 쉽게 정의할 수 있다. 다항시간 알고리즘이 없는 문제를 이야기한다.
그러나 정의는 쉽지만 어려운 것은 NP인지 판단하는 것이다. 다항시간 알고리즘이 없다는 것을 증명할 수 있을까?
아무리 알고리즘을 찾고 찾아도 새로운 알고리즘이 나올 '가능성'이 있다.
그래서 이 문제가 어려운 문제인지 쉬운 문제인지 판단하기가 거의 불가능하다.
어려운 문제의 경계를 판단하기 위해서는, 그 경계에 가까이 가야 한다.
그 경계에 있는 문제들이 NP-완전 문제에 속하는 것이다.
'다루기 힘들다고 증명되지도 않았고, 다항시간 알고리즘도 발견하지 못한 문제'를 의미한다.
NP문제에 대해 조금 더 이야기하자면, Non-poly가 아니다. Nondeterministic Polynomial이다.
P문제 집합과 NP-완전 문제 집합을 모두 포함하는 집합을 NP문제라고 한다. 즉, P문제는 NP문제 안에 있다.
비결정론적 다항식 시간 알고리즘을 가진 문제를 NP문제라고 하며, 결정 문제 관점에서 살펴보면 다음과 같다.
결정 문제들 중 적어도 검산은 쉽게 할 수 있는 문제를 모아 놓은 집합이라고도 볼 수 있다.
조금 더 풀어서 말하면, 어떤 결정 문제의 답이 '예'일때, 답이 '예'가 나오는 증거가 주어지면,
그 문제의 답이 정말로 '예'임을 다항식 시간 안에 보일 수 있는 문제들을 이야기한다.
NP문제들 중 어떤 문제들은 다항시간 안에 해를 찾을 수 있는 방법이 알려져있지 않다(NP-완전). 그치만,
해가 무엇인지를 알 수있는 정보가 주어지면 이를 기반으로 다항시간 안에 해를 확인할 수 있는 문제들이라는 것이다.
이를 기반으로 NP문제에 대한 NP 알고리즘을 만들 수 있는데, 이 정의는 다음과 같다.
1. 추측 : 주어진 입력에 대해 하나의 해를 '추측한다'
2. 검증 : 주어진 입력과 추측한 해를 입력으로 받아, 다항식 시간에 해를 검증한다.
즉, NP 알고리즘은 해를 찾는 것이 아니라, 해를 다항시간 안에 검증하는 알고리즘인 것이다.
예시 문제를 하나 들어보면, {-3, 1, 2, -8, -7, 13....} 과 같이 n개의 정수로 이루어진 집합이 주어졌다고 가정해보자.
이 집합의 부분집합 중에서 원소의 합이 0이되는 부분 집합이 존재하는가? 라는 결정 문제가 주어지면,
모든 부분집합에 대해서 테스트하지 않는 이상은 '예'와 '아니오'를 결정 짓기 힘들다.
그러나 {-3, 1, 2}라는 힌트가 주어진다면, 이 집합이 부분 집합인지 확인하고, 합이 0인지 확인하면
결정 문제의 답이 '예'라는 것을 다항시간 안에 알아낼 수 있다.
따라서 이 문제가 적어도 NP문제인 것은 확실하지만, P문제인지는 알 수 없다.
이런 예시들은 찾아보면 매우 많이 나오므로, 한 번쯤 찾아보는 것을 추천한다. 매우 어렵고 헷갈리는 개념이므로,
여러번 보면서 확실하게 기억해두자.
위에서도 계속 이야기하지만, 어떤 문제가 쉽다는 것을 보이는 것은 매우 간단하다. 다항시간 알고리즘이 있으면 된다.
그러나, 어렵다는 것을 보이는 것은 매우 힘들다. 어떠한 알고리즘도 다항시간에 해결할 수 없음을 보여야하기 때문.
추가로, P문제는 NP문제에 속해있다고 했는데, 그 이유는
P문제를 위한 NP알고리즘은 해를 추측할 필요가 없이 바로 다항시간에 해를 찾아내서 '예'라고 대답하면 되기 때문이다.
NP-완전 문제
앞선 개념들을 이해했다면 드디어 NP-완전 문제에 대해서 이야기해볼 수 있는데,
NP-완전 문제는 다루기 어려운 문제 중에서 가장 중요한 문제 집합이다. 아직까지는 결정 문제에 국한되어있지만,
사실 따지고보면 최적화 문제와 굉장히 관련되어 있다.
현재까지 학문적으로는 다항식 시간에 풀기 어렵다고 판단되면서, 서로 밀접한 논리 관계를 가진 문제 집합으로 정의한다.
이 논리 관계는 무엇이냐면, NP-완전 문제끼리는 서로 거대한 군을 형성한다는 것이다.
어느 하나의 NP-완전 문제가 현실적인 시간에 풀리면, 모든 다른 NP-완전 문제도 다항식 시간에 해를 구할 수 있게 된다.
그렇다면 NP-완전 문제는 어디에 속해있는 문제일까? 이를 위해 해당 포스트는 $P\neq NP$라고 가정하고 작성하겠다.
우선 당연히 NP문제 집합에는 속해있다. 하지만 P문제는 아니다. 그럼 NP-P 집합에 속한 문제들도 존재할 것이다.
그러면 P문제는 아니므로, 어려운 문제라고 생각할 수 있다. 그럼 해당 문제가 NP-P에 속하는지 판단하는 방법이 있을까?
놀랍게도 존재하긴 한다. 그러나 항상 성립하는 방법은 아니다. 그 방법이 바로 NP-완전 문제가 있다고 가정하는 것이다.
NP문제들 중 가장 어려운 문제를 NP-완전 문제라고 하고, 그럼 나머지 NP문제는 모두 이 문제보다 쉽게 된다.
그래서 NP-P집합에 NP-완전 문제가 있다고 가정하고, 어떤 문제가 NP-완전 문제만큼 어렵다고 보일 수 있다면,
그 문제가 P 바깥(NP-P)에 있는 문제가 되는 것이다.
이는 후에 변환/환원 특성을 이용해 푸는 법을 설명할 것이다.
따라서 NP-완전 문제임을 보이는 것은, 풀 수 없다는 것을 보이는 것이 아니라 이 문제가 아무도 풀지 못한 어려운 문제라는 것을 증명하는 과정이다. 반드시 기억하도록 하자. 즉, NP-완전 문제는 어려운 문제의 판별 기준으로 쓸 수 있다.
어떤 문제가 NP-완전 문제만큼 어렵기만 하다면, 그 문제는 P 바깥의 문제라고 할 수 있다.
따라서 어떤 문제가 주어졌을 때, 다항시간 알고리즘을 못찾고 있다면 해당 문제가 NP완전인지, 아니면 알려진
NP-완전 문제를 그 문제로 변환/환원하여 풀 수 있는지를 확인해야 한다.
NP-완전 문제의 특성(변환/환원, Reduction)
위에서 NP-완전 문제는 거대한 군을 형성한다고 이야기 했다. 이것이 NP-완전 이론의 논리체계를 구성하는 핵심 원리로,
이를 더 잘 이해하기 위해서는 한 문제를 다른 문제로 변환 혹은 환원하는 과정을 이해해야 한다.
이 과정은 서로 다른 두 문제의 난이도를 비교하기 위해 사용되는 것으로, 예시를 들어보자면
문제 1 : n개 숫자의 중간값을 계산하는 문제
문제 2 : n개 숫자를 내림차순 정렬하는 문제 라고 해보자.
만약에 내가 문제 2를 다항시간 안에 풀 수 있다면, 나는 문제 1또한 다항시간 안에 풀 수 있다.
문제 2를 풀기 위해 숫자를 내림차순 정렬하면, 그 중 가운데 있는 숫자를 뽑으면 자연스레 중간값이 되기 때문이다.
이렇다면 문제 1을 문제 2로 환원시킬 수 있다고 표현하고, 문제 1은 문제 2보다 어려울 수 없음을 알 수 있다.
즉 문제의 환원/변환이란 문제 A를 해결하기 위해서 문제 B를 해결하는 알고리즘을 이용하는 것을 이야기한다.
이를 위해 먼저 문제 A의 입력을 문제 B의 입력 형태로 변환시키고, 변한된 입력으로 문제 B를 해결하는
알고리즘을 수행한다. 마지막으로 수행 결과로 얻는 해를 문제 A의 해의 형태로 변환시킨다.
아까 문제의 분류에서 예시를 든 부분 집합의 합(Subset Sum) 문제과 분할 문제를 이용해 더 설명해보겠다.
부분 집합의 합 문제는 정수의 집합 S에 대해, S의 부분 집합들 중에서 원소의 합이 K가 되는 부분 집합을 찾는 문제이다.
예를 들어 $S = \{20, 35, 45, 70, 80\}이고, $K =105$라면, {35, 70}인 부분 집합이 그 해가 될 것이다.
이 문제를 문제 A라고 하고, 문제 B를 분할 문제라 하자.
분할 문제는 정수의 집합 S에 대해, S를 분할하여 원소의 합이 같은 2개의 부분 집합을 갖게하는 문제이다.
아까와 같은 집합이 주어진다면, {20, 35, 70}과 {45, 80}으로 나누면 두 집합의 합이 125로 같게 된다.
이제 위의 그림처럼 부분 집합의 합 문제를 분할 문제를 이용해서 풀어보겠다.
먼저 A의 입력을 B의 입력의 형태로 바꾸어야한다. 위의 예시는 굳이 원소를 추가하지 않아도 되지만,
일반적인 상황을 위해 집합 S의 모든 원소의 합을 $s$라고 한다면, $s-2k$를 추가한 집합 $S^`$을 생성한다.
그렇다면 $S^`$의 모든 원소의 합은 $s + (s-2k) = 2s-2k$가 될 것이고, 이는 $(s-k)$인 집합 두 개로 나눌 수 있다.
그러면 문제 B의 형태로 바꾸어서 해를 구해낼 수 있고, 해로 얻은 두 개의 집합 중
$(s-2k)$을 가진 집합에서 이를 제거하면, 그 집합이 문제 A의 해가 된다. $(s-k)-(s-2k)=k$ 이기 때문이다.
이러한 과정을 변환/환원이라고 부르며, NP-완전 문제끼리는 서로 변환/환원할 수 있다는 특성을 가진다.
그렇다면 이런 변환/환원 과정의 시간복잡도를 어떻게 알아낼 수 있을까? 그 기준은 다음 세 가지이다.
1. A의 입력 형태를 B의 입력 형태로 변환하는 시간
2. 문제 B의 알고리즘이 수행되는 시간
3. 문제 B의 해를 문제 A의 해로 변환하는 시간
여기서 1, 3번은 단순 변환이므로 다항시간안에 가능하다. 결국 2번에 의해 결정되는 것이다.
2번이 다항시간이 걸리면 문제 A도 다항시간 안에 해결 가능한 것이다.
또 추이 관계도 만족하기 때문에, A->B->C->D.......와 같다. 따라서 NP-완전 문제 하나가 다항시간에 해결되면,
모든 NP-완전 문제가 다항시간에 해결될 수 있게 된다. 이러면 밀레니엄 문제 중 하나인 $P=NP$가 증명이 된다.
반대로, 하나라도 다항시간에 해결할 수 없음을 보이면, $P\neq NP$가 증명이 된다.
그러나 아직 아무것도 증명해내지 못했다. 이 포스트를 보는 누군가가 언젠가는 증명했으면 좋겠다.
NP-hard 문제
이런 변환을 이용해 또 다른 문제 집합 하나를 찾아낼 수가 있는데, 이것이 바로 NP-hard 문제 집합이다.
만약 어느 문제 A에 대해서, 모든 NP문제가 문제 A로 다항시간 안에 변환/환원이 가능하다면, 그 문제 A를
NP-hard 문제라고 한다.
NP-완전이랑 뭐가 다르냐? 라고 하면 NP-hard 문제는 NP문제에 속하지 않을 수도 있다는 것이다.
후에 더 얘기하겠지만, 정확하게 이야기하면 NP-hard 문제 집합 안에 NP-완전 문제 집합이 존재하는 구조이다.
추가로, 알려진 NP-hard 문제 A로부터, 어떤 문제 B로 다항시간 안에 변환이 가능하면 B도 NP-hard 문제가 된다.
NP-완전 문제간의 관계와 비슷하다. 이 개념으로부터 NP-완전 문제를 더 자세하게 정의할 수 있다.
NP의 모든 문제가 어떤 문제 A로 다항시간에 변환되고, A가 NP문제이면 A는 NP-완전 문제가 되는 것이다.
그림으로 도식화하면 다음과 같다.
앞서 수 많은 개념들에 대해 배웠다. 새로운 개념이라 익숙하지 않고 낯설지만, 반복해서 공부해 이해하길 바란다.
말장난하기도 쉽고, 개인적으로 알고리즘에 대해 공부하며 가장 힘든 부분이었다.
이후 대표적인 NP-완전 문제에 대해서 몇 개 살펴보고 마무리 하겠다.
알려진 NP-완전 문제들
SAT(Satisfiability) - 충족 가능성 문제
부울 변수(T, F 값이 저장되는 변수)들이 OR(논리합)으로 묶여있는 논리식이 여러개 주어질 때, 이 논리식을 모두 만족시키는 각 부울 변수의 값을 찾는 문제이다. 예를들어
$(x\vee y)$,$(\sim w\vee x\vee y)$ 라고 한다면, x = True, y = True, w = True는 이 문제의 해 중 하나가 된다.
이런 식의 문제들에 대해 푸는 것인데, 일반적으로 직접 다 대입해보면 $O(2^n)$이 소요된다.
이 문제가 NP-완전 문제임을 미국의 스티븐 아서 쿡이 증명했다.
앞서 예시로 든 부분 집합의 합, 분할 문제도 NP-완전 문제에 속한다. 더불어, 배낭 문제도(0-1 배낭 문제)라는 이름으로
NP-완전 문제의 예시에 존재한다.
정점 커버 문제(Vertex Cover)
정점 커버 문제는 그래프 G = (V, E)가 주어졌을 때, 각 선분의 양 끝점들 중 적어도 1개의 점을 포함하는 정점을 모은 집합을 찾아내는 문제이다. 이때 집합의 크기는 최소가 되어야한다. 말로 해서는 이해가 안되니 사진을 첨부하자면,
죽, 다음 그래프에서 어떤 점들을 골라야 다른 모든 점이 골라진 정점중 하나에는 항상 연결되어있음을 보장하는가?
를 푸는 문제이다. 이 경우는 {1, 5, 6}이 정점 커버가 된다. 그래프의 모든 정점은 1, 5, 6중 하나와 연결되어있다는 이야기.
반대인 문제로 독립 집합(Independence Set)이 있는데, 해집합에 포함된 정점들은 절대 서로 연결되어 있지 않아야한다.
그런 조건을 만족하는 최대 크기의 집합을 찾는 문제이다. 해당 그래프 기준 {2, 3, 4, 7, 8}이 독립 집합이 된다.
또 비슷하게 클리크(Clique)라는 문제가 있는데, 이는 독립 집합의 반대로 해집합에 포함된 정점끼리 항상 연결되어있다.
이 문제는 최대 크기의 클리크 집합을 찾으면 된다.
이외에도 그리디 알고리즘이나 DP에서 배운 집합 커버, 작업 스케줄링, 통 채우기 문제 등이 NP-완전 문제에 해당한다.
많은 문제들이 존재하니, 궁금하다면 직접 찾아보는 것도 재밌는 경험이 될 것이다.
찾아보며 이건 왜 NP-완전인지, 변환이 가능한지 혹은 브루트 포스의 경우 시간복잡도를 구해보는 등을 해보자!
이상으로 NP-완전 이론에 대한 포스트를 마치겠다. 이제 알고리즘 포스트도 거의 막바지가 다가오고 있다.
다음 포스트는 NP-완전 문제의 최적해는 아니지만 근사해를 찾는 근사 알고리즘에 대해서 다룰 것이다.
이 알고리즘을 마지막으로 내가 작성하는 알고리즘 포스트는 끝이 날 예정이다.