[알고리즘 - 이론] Intractability Algorithm (다루기 힘든 알고리즘)

새로운 알고리즘을 개발할 때, 이 알고리즘이 다루기 어렵다는 것은 무엇을 의미할까요?

 

현실에서 다루기 어렵다는 것은 취급하기 또는 작업하기 어렵다로 정의하지만,

컴퓨터 과학에서 다루기 어렵다는 것은 "해당 문제를 다항시간(Polynomial-time)에 풀 수 없다"를 의미합니다.

즉 알고리즘의 Worst Case W(n) = O(p(n)) 만족하는 다항식 p(n)이 없다는 뜻입니다.

 

다항 시간안에 풀 수 있는 알고리즘은 2n, 3n^3, n lg n등이 있습니다.

n lg n은 n에 대한 다항식은 아니지만, n lg n < n^2에 의하여 다항시간 알고리즘으로 분류합니다.

 

따라서 컴퓨터 과학에서 문제가 다루가 힘들다는 것은 특정 알고리즘의 성질이 아니라 문제의 성질이 되어야 합니다.

 

사실 최악 시간 복잡도가 다항식이 아님에도 실제로는 효율적으로 실행되는 알고리즘이 꽤 많이 있을뿐더러, 경우에 따라 다항 시간 알고리즘이 있는 문제가 다항 시간 알고리즘이 없는 문제보다 실 상황에서 더 다루기 힘든 경우가 있을 수도 있습니다.

따라서 다루기 힘들다는 것은 실제로는 다루기 힘들 가능성이 있다 정도로만 보면 될 것 같습니다.

 

아무튼 다루기 힘든 정도에 대해 세 가지 종류로 문제를 분류할 수 있습니다.

• 다항시간 알고리즘을 찾은 문제
• 다루기 힘들다고 증명된 문제
• 다루기 힘들다고 증명되지 않았지만, 다항시간 알고리즘도 찾지 못한 문제 (called NP-complete)

슬픈 사실은 대부분의 문제가 첫째 또는 셋째 종류에 속한다는 현실입니다.

 

TSP 문제 같은 경우에는 아무도 다항 시간 알고리즘을 찾지 못했지만, 또한 다항 시간 알고리즘 내에 풀 수 없다고 증명하지도 못했습니다.

 

이때 알고리즘이 다항시간인지 결정할 때, 입력 크기에 주의를 기울여야 합니다.

0-1 KnapSack 문제의 경우 DP의 최악의 시간 복잡도가 \(\Theta(nW)\)였기 때문에, 다항 시간이라고 착각할 수 있지만,

실제로 W가 n의 거듭제곱이라면 시간 복잡도는 지수 시간을 가지게 됩니다.

 

따라서 우리는 입력 크기에 대해 좀 더 자세히 알아볼 필요성이 있습니다.

---

1. Input Size 재고

 

 

지금까지는 n을 입력 크기로 보았습니다. 왜냐면 n은 입력 데이터의 크기를 나타내는 척도로서 적당했기 때문입니다.

정렬 알고리즘에서는 n은 입력 데이터의 크기를 나타내는 좋은 척도입니다.

하지만 n이 무조건 알고리즘의 입력 크기가 되는 것은 아닙니다.

 

큰 정수의 곱셈의 경우를 생각해봅시다. n이 입력이긴 하지만, 우리는 n의 각 자릿수를 배열에 담아서 처리했습니다.

n이 너무나 큰 숫자이기 때문에 over flow가 날 가능성이 있기 때문에 말입니다.

이처럼 우리는 input size를 다시 한 번 생각해봐야 합니다.

과연 n이 시간 복잡도를 표현하기에 적합한 숫자인가에 대해서 생각해야 합니다.

 

소수 판별 문제를 생각해봅시다.

소수 판별 문제는 효율적이게 짠다면 \(\Theta(\sqrt{n})\)입니다.

 

이 또한 다항 시간 알고리즘이라고 할 수 있을까요?

n이 알고리즘의 입력이긴 하지만, 입력 크기라고 할 수는 없습니다.

왜일까요?

n이 무한히 커질수록 n을 표현해야 하는 비트 수가 늘어나기 때문입니다.

비트 수가 늘어난다는 것은 이를 위한 정보량이 늘어난다는 것이고, n에 대해서 시간 복잡도를 측정한 게 과연 정확할까요?

 

하지만 정렬 알고리즘과는 다릅니다. 정렬 알고리즘에서 n은 아이템의 개수이고, 입력 크기입니다.

그러면 소수 문제에 n은 과연 무엇일까요?

n이 입력이지만 입력 크기로 볼 수 없다면, 입력 크기는 무엇일까요?

---

2. 입력 크기란?

 

 

입력크기란 주어진 알고리즘의 입력 크기(input size)는 입력을 작성하는데 필요한 문자의 개수로 정의한다.라고 나와있습니다.

 

입력을 작성하는데 필요한 문자?

입력을 작성하는데 필요한 문자를 세기 위해 입력이 어떻게 encode 되는지 알 필요가 있습니다.

만약 2진수로 변환된다면, 양의 정수를 비트로 표현하기 위해 필요한 문자의 개수는 \(\left \lfloor \log x\right \rfloor + 1\)이 됩니다.

31은 비트로 표현하면 11111이고, 이는 lg 31 + 1 이므로 5입니다.

따라서 이진으로 된 양의 정수를 encode하기 위해서는 대략 lg n개의 비트가  필요하다고 간단하게 말할 수 있습니다.

따라서 n이라는 숫자가 입력된다면, 이를 위해 필요한 문자의 개수는 대략 lg n이 됩니다.

 

그렇다면 과연 입력 크기에 대한 정의에 따라

다항 시간 알고리즘에 대해 입력 크기를 정확하게 따져도 다항 시간으로 남아 있을까요?

이제 입력 크기를 정확하게 따지기로 했으니까, Worst-Case Time Complexity에 대해 다시 정의해야 합니다.

---

3. 정확한 시간 복잡도에 대한 정의

 

 

Worst-Case Time Complexity W(s)는 입력 크기 s에 대하여 그 알고리즘이 실행한 '단위 연산의 최대 개수'이다.

 

이때 단위 연산을 정해야 하는데, 단위 연산은 비트의 비교 연산 혹은 비트의 저장 연산을 단위 연산으로 정합니다.

입력 크기를 n 대신 s로 정한 이유는 다음과 같습니다.

• 알고리즘의 파라미터 n이 항상 입력 크기를 재는 척도는 아니다.
• n으로 입력 크기를 잰다면, 이는 보통 입력 크기의 정확한 척도가 아니다.
  • 바로 위의 정의에 따르면, 알고리즘이 실행한 단위 연산의 개수를 모두 세어야 하기 때문입니다.
  • 비트로 계산을 해야 하는데, n으로 계산한다면 정확한 척도가 아니겠죠?
  • 또한 위에서 입력 크기에 대한 정의를 했을 때, n이 아닌 lg n를 입력 크기로 봐야 하기 때문입니다.

따라서 입력 크기에 대한 정의와 최악 시간 복잡도에 대한 정의 때문에

n대신 n을 비트로 표현한 s를 기준으로 시간 복잡도를 재정의 해야 합니다.

 

그렇다면 s = lg n이라고 표현할 수 있습니다.

입력이 n이라면 정확한 입력 크기는 n을 부호화한 s = lg n이 입력 크기가 됩니다.

---

4. 다시 한 번 최악 시간 복잡도를 측정해보자!

 

 

정렬 알고리즘의 경우를 생각해봅시다.

L이 가장 큰 정수라면, 정수를 한 번 비교하거나 저장하는데 최대 lg L 번의 비교 연산을 거쳐야 합니다.

그렇다면 n개의 입력이 있을 때, 입력 크기 s = n lg L으로 생각해야 합니다.

 

이런저런 연산을 통해 결론부터 말하자면,

정렬 알고리즘은 (c + 4)s^2가 나옵니다!

 

즉, 정렬 알고리즘에서는 n이 입력 데이터 크기를 재는 척도일 때, 단순히 n을 입력 크기로 해도 믿을만한 시간 복잡도를 알아낼 수 있음을 의미합니다.

따라서 정렬 문제에서 n을 그대로 입력 크기로 사용해도 문제는 없습니다.

 

이제 소수 알고리즘으로 돌아가 봅시다.

n으로 시간 복잡도를 구했을 때, \(\Theta(\sqrt{n})\)이 나왔었습니다.

하지만 이제 제대로 구해야 하므로, s = lg n이라고 봐야 합니다.

어랏, 그러면 n = \(2^s\)이지 않나요?

 

그러면 시간 복잡도를 다시 표현하면, \(2^{s/2}\)이 됩니다.

따라서 시간 복잡도가 다항 시간이 아니게 됩니다.

 

비트 수, s로 보면, 이 문제는 지수 시간 복잡도의 형태를 가지게 되므로, 다항 시간 문제가 아닙니다.

소수 검사 알고리즘 같은 알고리즘에서 우리는 n을 입력의 절대 크기(magnitude)라고 부릅니다.

n은 절대적인 수 하나를 의미하지만, 입력 크기는 이 숫자의 비트 크기를 의미합니다.

 

절대 크기로 봤을 때는 시간 복잡도가 다항 시간이지만, 크기로는 다항 시간이 아닌 알고리즘을 뜻할 때 표현합니다.

 

만약에 최악 시간 복잡도의 상한이 크기와 절대 크기로 모두 다항 시간이 되는 알고리즘을

의사 다항 시간(pseudo polynomial-time)이라고 합니다.

---

5. 다루기 힘듦과 관련된 세 가지 카테고리

 

 

5.1 다항 시간 알고리즘을 찾은 문제

 

n이 알고리즘의 입력 데이터 크기를 나타낼 수 있는 알고리즘은 n으로 시간 복잡도를 표현했을 때, 다항 시간이라면 그냥 다항시간 알고리즘이 맞습니다.

예를 들면, 정렬된 배열(n lg n)을 검색하거나, 행렬을 곱셈(n^2.38)하거나, 연쇄 행렬을 곱셈(n^3)하는 알고리즘이 대표적입니다.

 

 

---

5.2 다루기 힘들다고 증명된 문제

 

5.2.1 문제 자체의 해답으로 지수 이상의 크기를 요구하는 문제

 

만약 모든 정점에서 다른 모든 정점으로 간선이 있는 회로에서는 해밀턴 회로가 (n - 1)!개 존재할 것입니다.

이 문제를 푸는 알고리즘은 모든 해밀턴 회로를 출력해야 하는데, 이러한 요구는 현실적이지 않습니다.

 

만약 단 하나의 회로만 출력하라고 한다면, 이는 당연히 다루기 힘든 문제가 아닙니다.

 

하지만 모든 회로를 출력하라는 것은 지수 이상 크기의 출력을 요구하는 것이고,

이는 알아차리기도 쉽고, 일단 알아냈다면 필요 이상으로 정보를 요구한 경우가 많습니다.

 

즉. 문제 자체가 현실적이지 못합니다.

 

그렇다면 문제가 현실적이면서도, 다항 시간 내에 풀 수 없는 문제에 대해 알아봐야 합니다.

 

---

5.2.3 문제가 현실적이면서(즉, 지수 시간 이상의 크기의 출력을 요구하지 않고), 문제를 다항 시간 내에 풀 수 없다고 증명할 수 있는 경우

 

신기하게도 이러한 문제는 상대적으로 별로 없습니다.

 

우선 진위 판별 불가능(undecidable)문제가 이에 속합니다.

푸는 알고리즘이 없다고 증명할 수 있는 문제가 이에 속합니다.

 

이때 진위 판별 불가능으로 널리 알려진 Halting Problem(정지 문제)에 대해서 알아보겠습니다.

Halting Problem은 정지 문제로, 진위 판별 불가능 문제는 풀기 어려운 문제라고 증명했습니다.

구글에 검색하면 저보다 더 자세하게 설명한 내용들이 많으므로, 자세한 내용은 생략하고 간단하게 적어보겠습니다.

 

여기 halt라는 함수가 있습니다. 이 함수는 func라는 파라미터를 받는데, func이 멈출 수 있다면 true를, 멈출 수 없다면 false를 반환합니다.

 

또한 verify라는 함수가 있는데, 이 함수는 파라미터로 func을 받습니다.

verify 함수 내에는 if halt(func)이 있고, if true 라면 멈출 수 없는 함수를 호출하고, if false라면 멈출 수 있는 함수를 호출합니다.

 

이제 verify(verify) 명령어를 입력합시다.

음..

verify는 일단 들어오는 함수에 의해 멈출지 말지 결정합니다.

근데 위 처럼 vefify(verify)를 한다면, 안으로 들어오는 함수가 멈출지 안 멈출지도 모릅니다.

 

만약에, verify가 멈춘다고 가정해봅시다.

그러면 verify 함수 내에 있는 if halt(verify)가 if true가 되고, 멈출 수 없는 함수를 호출합니다.

이러면 verify는 멈출 수 없게 되네요.

 

분명 verify는 멈춘다고 가정했는데, 결론은 멈출 수 없게 되었으므로 이는 모순입니다.

 

다시 verify가 멈추지 않는다고 가정해봅시다.

그러면 verify 함수 내에 있는 if halt(verify)가 if false가 되고, 멈출 수 있는 함수를 호출합니다.

그러면 verify는 멈추게 됩니다.

 

이 또한 verify는 멈추지 않는다고 가정했는데, 멈추게 되므로 모순입니다.

 

이해가 되시나요?

 

이렇게 진위를 판별할 수 없는 문제를 진위 판별 불가능 문제라고 합니다.

 

 

추가적으로 지금까지 다루기 힘들다고 증명된 문제는 모두 NP 집합에 속하지 않는다고 증명되었습니다.

그러나 다루기 힘들 "것처럼 보이는" 문제는 대부분 NP 집합에 속합니다.

 

다음 글에선 NP 집합에 대해서 알아봅니다.

---

5.3 다루기 힘들다고 증명되지도 않았고, 다차 시간 알고리즘도 찾지 못한 문제

 

 

다항 시간 알고리즘을 찾지 못했지만, 그렇다고 다항 시간 알고리즘이 불가능하다고 증명하지도 못한 문제는 모두 이 카테고리에 속합니다.

 

예를 들어 하나의 해답만 요구하는 0-1 KnapSack, TSP, Sum of Subset, m-Coloring 등 이러한 문제들이 모두 이 카테고리에 들어갑니다.

 

즉, 입력되는 instance를 제한된 부분 집합에서 취할 때, 다항식이 존재하지만,

모든 instance에 대해서 다항식이 존재하는 것은 아닙니다.

 

 

 

 

이러한 카테고리들은 많이 밀접하고, 흥미롭게 엮여 있습니다.

이에 대해 알아보는 것이 바로 다음 글의 목표입니다.

 

 

감사합니다.

 

 

지적 환영합니다.