해당 글은 “컴퓨터가 풀기 쉬운 문제와 어려운 문제의 경계”라는 제목으로 제출한 “수학과 문명” 과목의 과제물을 수정한 것이다.
1. 서론
튜링 머신과 같이 작동하는 컴퓨터는 인간이 개발한 알고리즘에 맞추어 주어진 데이터를 빠르게 처리하여 결과를 얻어낼 수 있는 능력을 가지고 있다. 즉, 컴퓨터는 “계산 가능한 문제” 들을 해결할 수 있는 능력을 가지고 있다는 것이다. 일상 속에서도 목적지 까지의 최단 거리, 성적 순으로 정렬하기, 단어 검색하기 등의 문제를 빠르게 해결한다.
하지만 컴퓨터가 아무리 빠르다 해도 처리하기 어려운 문제들이 있다.
N개의 물건이 있고, 각 물건에는 무게와 가치가 정해져 있다. 담을 수 있는 최대 무게가 정해진 가방에 담을 수 있는 최대 가치는 몇인가?
이 문제를 해결하기 위해서는 각 물건을 담아봐야 한다. 물론 최대 가치를 가진 물건부터 담아 확인해 볼 수 있지만, 무게라는 제약 조건이 포함되기 때문에 가치가 작은 물건을 이용하여 최대 가치를 만들 수 있다. 따라서 가능한 경우를 모두 탐색해 봐야 하고, 각 물건 당 2가지 경우가 발생하여 최대 $2^N$가지의 경우를 확인해야 한다. 물건이 100개만 있어도 컴퓨터는 $10^{30}$만큼의 연산을 해야 한다. 현대 상용 컴퓨터가 1초에 1억번 정도의 연산을 한다는 점을 생각하면, 컴퓨터가 이 문제를 해결하기 위해서는 $10^{22}$초 즉 $3 \times 10^{12}$세기의 시간이 필요하다.
이 문제는 컴퓨터 과학에서 유명한 배낭 문제(Knapsack Problem)이다. 일반적인 경우 이 문제는 “현실적”으로 해결할 수 없는 문제다. 하지만, 적절한 조건을 만족하는 “운이 좋은”상황에서는 빠르게 해결할 수 있는 알고리즘이 존재한다.
그렇다면 운이 나쁜 상황에서도 빠르게 해결할 수 있는 방법이 존재할까?
이것이 유명한 난제, P-NP 문제이다. 풀기 어려운 문제의 경계는 어디인지를 묻는다.
2. 알고리즘의 성능 평가
내용에 들어가기 앞서, 컴퓨터 과학에서는 알고리즘의 성능을 어떻게 표현하는지 간단히 알고 넘어가자.
컴퓨터 과학에서는 알고리즘의 성능(속도)를 평가할 때, 시간 복잡도(Time complexity)를 이용한다. 시간 복잡도란, 입력 데이터의 크기에 대해 해당 알고리즘의 연산량이 얼마인지를 점근 표기법(Asymptotic notation)으로 나타낸 것이다.
점근 표기법 중 컴퓨터 과학에서 주로 사용하는 빅 오 표기법(Big O notation)은 다음과 같이 정의된다[1].
함수 $f(x)$, $g(x)$에 대해 $f(x)$가 $O(g(x))$라는 것은 상한 점근에 관한 다음의 동치인 정의와 같다.
- $x > x_0$를 만족하며 충분히 큰 모든 $x$에 대하여 $\left \vert f(x) \right \vert \le M \left \vert g(x) \right \vert$가 성립하도록 하는 양의 실수 $M$과 실수 $x_0$가 존재한다.
- $\lim_{n\rightarrow \infty } \left \vert \frac{f(n)}{g(n)} \right \vert < \infty$
이를 $f(x)=O(g(x))$ 혹은 $f(x) \in O(g(x))$로 표기하기로 한다.
예로 $f(x)=3x^3+12x^2+1$이라 하면 $f(x)=O(x^3)$이라 할 수 있다. 시간 복잡도는 이와 같은 점근 표기법으로 표현되며, 증가하는 꼴의 상한을 표현하는 가장 간단한 함수의 형태로 표현한다.
알고리즘의 시간 복잡도를 보고 데이터의 양이 얼마가 들어가면 어느 정도의 연산이 필요한지 가늠할 수 있고, 이런 연산량을 통해 시간 비용을 추정할 수 있다.
예를 들어 Algorithm. 1과 같은 알고리즘의 시간 복잡도를 계산해 보자.
Algorithm. 1. N을 M번 더하는 알고리즘
- 자연수 N과 M을 입력 받고 2번 과정으로 간다.
- 변수 A를 0으로 하고 3번 과정으로 간다.
- 4번 과정을 M번 반복한 뒤, 5번 과정으로 간다.
- 변수 A에 N을 더한다.
- 변수 A의 값을 결과로 반환하고 종료한다.
Algorithm. 1은 N을 M번 더한 값을 계산한다. 따라서 해당 알고리즘의 시간 복잡도는 M에 대한 시간 복잡도인 $O(M)$이 된다.
3. 풀기 어려운 문제
컴퓨터가 풀기 어려운 문제란, 서론에서 살펴본 배낭 문제와 같이, 해결하는데 필요한 비용이 현실적이지 않은 경우이다.
그렇다면 현실적인 비용이란 무엇일까?
현실적인 비용이란, 다항 시간(Polynomial complexity)이하로 치부된다[2]. 다항시간이 현실적인 이유는 컴퓨터 성능이 배로 빨라지면 처리 가능한 데이터 량도 배로 이득을 보기 때문이다[2].
데이터의 크기가 $n$인 상황에서 시간 복잡도가 $O(n^k)$인 알고리즘에 대해, 컴퓨터 성능이 $p$배 빨라지면 동일한 입력에 대한 비용이 $\frac{n^k}{p}$로 감소한다. 따라서 동일한 시간에 처리할 수 있는 크기가 $m$라면 $n^k=\frac{m^k}{p}$을 만족하기 때문에 $m=p^{\frac{1}{k}} \times n$이 된다. 결국 $p^{\frac{1}{k}}$배 큰 입력을 처리할 수 있다.
이러한 문제들을 P 문제(Polynomial problem) 라고 한다.
반면 비현실적인 문제들은 입력에 대해 연산량이 기하급수적(Exponential complexity)으로 증가한다. 즉, 입력 크기가 $n$인 상황에서 시간 복잡도가 $O(k^n)$인 경우이다. 이러한 경우 컴퓨터 성능이 배로 빨라져도 더한 정도 밖에 이득을 볼 수 없다. 대표적인 경우가 서론에서 본 배낭 문제이다. 복잡도가 $2^N$정도로, 성능이 2배 증가해도 입력이 1증가한 N + 1 정도밖에 처리할 수 없다.
4. P 문제와 P 문제가 아닌 문제
P 문제는 명확하게 알 수 있다. 다항 시간 안에 해결할 수 있는 문제는 P 문제이다. 반면에 P 문제가 아닌 문제는 알기 어렵다. P 문제가 아닌 것을 확인하려면 어떠한 경우에도 다항 시간 내에 해결할 수 없음을 증명해야 되기 때문이다. 대표적인 문제로 정지 문제(Halting problem) 을 들을 수 있다. 정지 문제는 다음과 같다.
프로그램을 설명한 것과 처음 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라 [3].
이 문제는 앨런 튜링(Alan Turing)에 의해 풀 수 없는 문제임이 증명되었다[3]. 이와 같은 경우 증명이 되었기 때문에 P 문제가 아니라는 것을 알 수 있다.
하지만 배낭 문제와 같은 많은 문제들은 일반적 상황에서는 풀기 어렵지만, 특정한 상황 즉, 운이 좋은 상황에서는 다항 시간 내에 해결할 수 있기 때문에 P 문제인지 아닌지 판단하기 어렵다.
이러한 문제를 NP(Non-deterministic Polynomial)문제 라 한다. NP문제는 P문제인지 결정하기 어렵다. 이름에 숨겨져 있는 Non-deterministic은 비결정론적 튜링 머신(Nondeterministic Turing Machine)으로 부터 온것인듯 하다.
일상속에서 NP문제들을 많이 발견할 수 있다. 인수분해를 할 경우, 운이 좋으면 한번에 성공할 수 있지만 대부분의 경우 거의 모든 경우를 탐색해야 한다. N가지 요소를 선택해서 성공적인 제품을 만드는 경우도 운이 좋으면 단번에 제품을 많이 팔아 성공할 수 있지만 대부분 그런 경우를 찾기 어렵다.
그렇다면 이런 많은 문제들 중 어디 까지가 P문제일까? 이것이 P = NP문제이다.
5. P = NP 문제
NP문제들의 존재는 NP문제들이 결국 P문제들인지, 아니면 결국 운에 의해서만 해결될 수 있는 문제들인지에 대한 의문을 가져온다.
P = NP문제를 해결할 수 있는 방법은 NP-완전(NP-Complete)이 P문제임을 보이는 것이다. NP문제를 다항시간 안에 NP-난해(NP-Hard)문제로 환원할 수 있는데, 이는 NP-난해가 가장 어려운 문제임을 말한다. NP문제인 동시에 NP-난해인 문제가 NP-완전문제이다. 따라서 NP-완전 문제들은 NP문제들 중 가장 어려운 NP문제로, 모든 문제들을 NP-완전 문제를 통해 해결할 수 있다. 이를 모든 NP문제를 다항시간 안에 NP-완전 문제로 환원할 수 있다고 한다. 예를 들어, 앞서 살펴본 알고리즘인 N을 M번 더하는 알고리즘 Algorithm. 1을 생각해 보자. N을 M번 더하는 알고리즘의 시간 복잡도는 $O(M)$으로 다항시간 안에 해결할 수 있다. 그렇다면 $N \times M$도 다항시간에 해결할 수 있다. 왜냐하면 $N \times M$는 N을 M번 더하는 알고리즘으로 빠르게 환원하여 해결할 수 있기 때문이다.
하지만 NP에 속하지 않는 NP-난해(NP-Hard)는 NP에 속하지 않으므로 어떤 경우에도 P로 해결될 수 없음이 증명된 문제들이다. 따라서 NP-난해는 NP가 될 수 없다. 앞서 예를 든 정지 문제가 NP-난해 문제이다.
Fig. 1. P, NP, NP-완전, NP-난해 들에 대한 오일러 다이어그램[4]
P, NP, NP-완전, NP-난해 이 4가지 부류를 나타내면 Fig. 1과 같다. 왼쪽은 $P \ne NP$인 경우이고 오른쪽은 $P = NP$인 경우이다. $P \ne NP$인 경우, P가 아닌 문제와 P인 문제 사이에 운에 의존해야만 해결할 수 있는 NP부류가 존재하게 된다. 반면 $P = NP$인 경우, 모든 NP문제는 다항 시간 내에 해결할 수 있다.
6. P = NP 문제의 의미
P = NP문제가 참이면 계산 가능한 문제들은 모두 쉽게 해결할 수 있음을 뜻한다. 언뜻 보면 무엇이든 해결할 수 있는 완벽한 세상처럼 보이지만, 이면에는 정해진 연산 만으로 답을 찾아낼 수 있는 재미없어 보이고 계산적인 세상으로 보인다. 완벽한 제품을 만들기 위한 요소를 계산하고, 완벽한 소설을 만들기 위한 요소를 계산하는 의미 없어 보이는 세상.
그래서인지 2012년 이론전산학자 150명을 대상으로 조사한 결과, 81퍼센트의 비율로 거짓일 것이라 답했다[4]. 하지만 필자는 이 문제가 참으로 밝혀져도 다음의 쿠르트 괴텔(Kurt Gödel)의 불완전성의 정리(incompleteness theorem) 가 있기에 여전히 의미 있는 세상일 것이라 생각한다.
“기계적인 방식만으로는 수학의 모든 사실을 구성할 수 없다.”[5]
즉, 아무리 P = NP일지라도 계산 가능한 문제에 대해서만 해당되기 때문에 계산 불가능한 문제인 수학에 대해서는 적용되지 않는다.
참고문헌
[1] Wikipedia contributors, "Big O notation", Wikipedia, The Free Encyclopedia, https://bit.ly/2mmsSY1 (accessed September 20, 2019).
[2] 이광근, 컴퓨터과학이 여는 세계, 인사이트, 2017.
[3] 위키백과 기여자, "정지 문제", 위키백과, https://bit.ly/2kpTHdi (2019년 9월 20일에 접근).
[4] Wikipedia contributors, "P versus NP problem", Wikipedia, The Free Encyclopedia, https://bit.ly/2kKQTrA (accessed September 20, 2019).
[5] Graves, Alex, Greg Wayne, and Ivo Danihelka. "Neural turing machines." arXiv preprint arXiv:1410.5401 (2014).