0. 서론
2003년 12월 국내 한 수학 교수가 'P : NP 문제'를 해결했다고 하여 신문에 크게 난 적이 있다. 이것은 지난 2000년 미국 클레이 수학재단이 한 문제에 100만 달러씩 걸고 발표한 7가지 난제 중 첫 번째 것으로, 현대 컴퓨터 과학의 미해결 문제 중에서 가장 중요한 것으로 손꼽히고 있다. 몇 년을 두고 그에 대한 검증을 한다고 기사에 나왔는데 현재 어떻게 되었는지는 모르겠다.
당시 기사를 읽고 던진 물음이 "P : NP 문제가 도대체 무엇인가?"였다. 페르마의 마지막 정리, 골드바흐의 추측, 사색문제 등이 일반인도 쉽게 이해할 수 있는 난제인데 반하여, P : NP 문제는 그것이 어떤 문제인지 이해하는 데만 해도 알아야 할 배경 지식이 만만치 않게 많다.
이 컨텐츠는 P : NP 문제가 무엇인지를 알기 위해 배워야 하는 개념들의 정의와 그에 대한 설명이 주된 내용이다. 중간중간에는 이해를 돕기 위한 예제들이 있다. 예제 코드는 주로 파이선 문법에 따라 작성하였다.
덧붙여, 본문에서 중요한 키워드는 '굵은 글씨'로 강조하거나 영문 용어를 함께 표기하였다. 더 깊게 공부하고 싶은 내용이 있으면 해당 용어를 인터넷으로 검색하면 다양한 참고자료를 구할 수 있을 것이다.
1. 알고리즘과 복잡도
1.1. 알고리즘
어떤 수학적인 문제 problem 를 유한한 단계 안에 해결하기 위한 방법 혹은 절차를 알고리즘algorithm이라고 한다. '문제'와 '알고리즘'은 확실히 구분해야 하는 개념이다. 한 문제에는 그것을 계산하기 위한 서로 다른 알고리즘이 여럿 있을 수 있다.
두 자연수가 주어졌을 때 둘의 최대공약수를 구하는 문제를 생각해보자. 이 문제에 대한 알고리즘으로 다음의 두 가지를 생각할 수 있다.
첫째는 두 수 중의 작은 것으로부터 시작해서 1씩 빼가면서 주어진 두 수를 나눈 나머지가 각각 0이 될 때까지, 즉 둘의 공약수가 나올 때까지 반복하는 것이다. 이렇게 하면 분명히 최대의 공약수를 찾을 수 있다.
둘째 방법은 유클리드 호제법Euclidean algorithm을 이용한 것이다. 유클리드 호제법은 둘 중의 작은 수로 큰 수를 나누었을 때 나온 나머지를 이용한다. 이전 단계의 작은 수를 큰 수로 취하고, 나눗셈에서 나온 나머지를 작은 주로 취하여 나머지가 0이 될 때까지 이것을 반복한다.
다음은 두 알고리즘을 파이선 문법으로 구현한 것이다.
첫 번째 방법 | 두 번째 방법 |
def gcd1(x,y): d = min(x,y) while(x%d!=0 or y%d!=0): d -= 1 return d | def gcd2(x,y): a, b = max(x,y), min(x,y) while(a%b != 0): a, b = b, a%b return b |
직접 손으로 해보면 두 번째 방법이 첫 번째에 비해 훨씬 쉽고 시간도 적게 걸린다. 다시 말해, 유클리드 호제법이 하나씩 나누어 보는 것보다 더 우수한 알고리즘이라 할 수 있다.
1.2. 복잡도
여러 알고리즘이 있을 때 어떤 것이 더 우수하냐를 가리기 위한 기준이 바로 알고리즘의 복잡도complexity이다. 알고리즘의 복잡도란 쉽게 말해 그 방법의 효율성, 즉 계산을 하는데 얼마나 많은 비용cost을 필요로 하는가를 뜻한다. 복잡도의 척도가 되는 비용에는 컴퓨터로 돌렸을 때 걸리는 시간, 총 연산 수, 사용된 메모리의 양, 사용된 하드웨어의 양 등이 올 수 있다.
비록 어떤 문제가 계산 가능하다 할지라도 알고리즘의 복잡도가 너무 크다면 계산하기가 어려울 것이다. 예컨대, 이론적으로는 모든 경우의 수를 따져보면 바둑의 최선 전략을 계산할 수 있을 테지만, 그 경우의 수는 천문학적으로 많은 수치이므로 이것은 현실적으로 아주 힘든 문제이다.
알고리즘 복잡도의 기준으로 가장 흔히 쓰이는 것은 계산 시간과 총 연산 회수이다. 계산 시간은 기본 연산을 한번 하는데 걸리는 시간에 그 연산이 등장하는 회수를 곱한 것과 같으므로, 이 둘은 거의 같게 볼 수 있다. 이를 알고리즘의 시간 복잡도time complexity 라고 한다. 기본 연산을 무엇으로 두느냐는 문제나 알고리즘에 따라 달라질 수 있는데, 보통 두 수의 덧셈이나 곱셈, 논리 연산, 메모리 할당 등을 기본 연산으로 둔다.
최대공약수 문제로 돌아가자. 둘 중의 작은 수를 
어떤 결정형 문제가 주어졌을 때, 그것을 계산할 수 있는 알고리즘의 시간 복잡도에 따라 그 문제는 P 혹은 NP로 분류될 수 있다. ( P와 NP 둘 다 아닐 수도 있다.)
다음 장에서는 P와 NP가 무엇인지 본격적으로 알아보자.
2. P와 NP
2.1. 결정형 문제
P와 NP는 결정형 문제에 한해서 정의된다. 여기서 결정형 문제decision problem란 그 답이 '예yes' 와 '아니오no' 둘 중의 하나로 결정되는 문제를 뜻한다. 이와 대조되는 개념으로 답에 셋 이상의 경우의 수가 있는 문제를 함수형 문제function problem라고 한다.
결정형 문제의 예:
, 
, 
가 주어졌을 때, 
과 
의 최대공약수가 
인가?
이 주어졌을 때, 
이 소수(素數)인가?
에 대해, 
을 만족하는 자연수 쌍 
가 존재하는가?
와 입력 
가 주어졌을 때, 
가 정지하는가?
함수형 문제의 예:
, 
이 주어졌을 때, 
과 
의 최대공약수를 구하여라.
이 주어졌을 때, 
의 약수는 몇 개인가?
에 대해, 
을 만족하는 자연수 쌍 
를 모두 나열하라.
위의 예에서 볼 수 있듯 함수형 문제는 결정형 문제보다 더 포괄적이지만, 많은 함수형 문제는 그와 상응하는 결정형 문제로 변형시킬 수 있다.
어떤 결정형 문제에 대해 유한한 시간 내에 답이 '예'인 경우와 '아니오'인 경우 모두를 답할 수 있으면 그 문제는 결정 가능하다decidable라고 한다. ①, ②, ③은 모두 결정 가능한 문제의 예이다.
유한한 시간 내에 답이 '예'인 경우를 답할 수 있으면 그 문제는 해결 가능하다solvable라고 한다. 다른 말로, 부분적으로 결정 가능하다partially decidable, 반 결정 가능하다semidecidable, 증명 가능하다provable 등으로 쓰기도 한다. ④는 결정 가능하지는 않지만 해결 가능한 문제의 대표적인 예로, 정지 문제halting problem로 잘 알려져 있다.
해결 가능하지 않은 문제도 존재한다. 대각화 언어diagonalization language가 그 예이다.
2.2. 결정성 / 비결정성 알고리즘
결정성 알고리즘deterministic algorithm은 '각 단계에서 그 다음 단계가 유일하게 결정되는 알고리즘'을 말한다. 우리가 여러 프로그래밍 언어로 작성하는 코드는 모두 결정성 알고리즘에 의한 것이다.
비결정성 알고리즘non-deterministic algorithm은 '각 단계에서 그 다음 단계가 유일하게 결정되지 않는 알고리즘'을 말한다.
구체적인 예를 통해 비결정성 알고리즘이 무엇인지 알아보자. 다음은 주어진 자연수 
코드는 파이선 문법을 기반으로 작성되어있다. 하지만 파이선은 비결정성 알고리즘을 지원하지 않으므로, 붉고 굵은 글씨 OR를 통해 이를 표현하였다. 예컨대 'A OR B OR C'는 'A', 'B', 'C' 중의 한 가지를 '임의로 선택'해서 실행시킨다는 의미이다.
# 예제: 합성수 판별 문제에 대한 비결정성 알고리즘 def isComposite(n): a, b = 2, n-1 while b-a > 0: # 2 ≤ a ≤ n-1인 a를 선택하는 과정 m = (a+b)/2 a = m OR b = m if b-a == 1: a = b OR b = a if n%a == 0: return True else: return False |
while 문 안에 있는 두 개의 OR 가 가장 중요한 부분이다. while 문 안에서는 두 수 a와 b의 차를 한번에 반씩 줄여나간다. 'a = m OR b = m'에서 'a = m' 을 실행시키면 뒤의 반을 취하게 되고, 'b = m'을 실행시키면 앞의 반을 취하게 된다.
n=12라고 하자. 이 경우 우리가 얻어야 하는 답은 True이다. 만약 while문에서 a=5가 선택되었다면, n%a != 0이므로 False가 출력될 것이다. 만약 while문에서 a=4가 선택되었다면, n%a == 0이므로 True가 출력될 것이다. 이렇듯 비결정성 알고리즘은 같은 입력에 대해서도 출력이 여러 가지일 수 있다.
때문에 입력 x에 대한 비결정성 알고리즘 P의 출력을 이렇게 정의한다.
- 결과가 True로 나오는 경우의 수가 하나라도 존재하면, 'P(x) = True'이다.
- 모든 경우에 대해 결과가 False로 나오면, 'P(x) = False'이다.
각 단계에서 이어질 수 있는 다음 단계의 경우의 수가 최대 
# 예제 def f(A): t = 0 for x in A: t += x OR t -= x OR pass for x in A: t *= x OR t *= x+1 OR t *= x+2 OR pass if t > 100: return True else: return False |
바로 위의 예는 코드 자체에는 별 의미가 없으므로 형태에만 주목하도록 하자. 첫 번째 for문의 비결정도는 3이고 두 번째 for문에서는 4이므로, 전체 알고리즘의 비결정도는 4이다.
결정성 알고리즘과 비결정성 알고리즘의 계산 능력이 동일함은 증명되어있다. 즉, 비결정성 알고리즘에 의해 해결 가능한 문제는 결정성 알고리즘에 의해서도 해결 가능하다. (그 역은 당연히 성립한다.)
2.3. P 문제
P 문제 는 '결정성 알고리즘으로 다항식 시간 내에 해결 가능한 결정형 문제'이다. 다항식 시간polynomial time이라는 것은 입력의 크기를 
이때 다음의 세 가지 연산을 기본 연산으로 허용한다.
- 변수의 값을 1만 증가시키거나 감소시키는 대입문 (++, --)
- 값이 0인 경우에 계산의 흐름을 변화시키는 조건문 (if)
- 반복을 위한 점프문 (goto)
아래 예제는 점프문을 지원하는 C 문법을 채용하였다.
// 예제: 세 가지 기본 연산을 사용하여 구현한 두 자연수의 덧셈 int plus(int a, int b){ L1: if(b==0) goto L2; a++; b--; goto L1; L2: return(a); } |
위의 세 연산을 사용하면 우리가 쓰는 프로그래밍 언어에 내장되어있는 for문, while문 등을 모두 구현할 수 있다. 따라서 앞으로 보게 될 예제에서는 위의 세 가지 기본 연산 외에 파이선에서 제공하는 함수나 연산을 자유롭게 이용할 것이다.
P 문제들의 모임을 P클래스P-class라 한다. 그래프의 최단 경로 탐색 등 수많은 결정형 문제가 P클래스에 속한다.
2.4. NP 문제
NP 문제는 '비결정성 알고리즘으로 다항식 시간 내에 해결 가능한 결정형 문제'이다. P 문제와 다른 점이라면 알고리즘이 결정성이냐 비결정성이냐의 차이이다.
다음은 부분집합 합 문제subset sum problem에 대한 비결정성 알고리즘이다. 부분집합 합 문제는 유한집합 
# 예제: 부분집합 합 문제에 대한 비결정성 알고리즘 def ssp(A): S = [] for x in A: # A의 부분집합 S를 구하는 과정 S.append(x) OR pass # A의 각 원소에 대해 그것을 S에 추가할지 '선택' if sum(S) == 0: return True else: return False |
부분집합 합 문제에 대한 예제 알고리즘의 경우, 집합 
NP 문제들의 모임을 NP클래스NP-class라 한다.
3. P = NP ?
3.1. P와 NP의 상관관계
결정성 알고리즘은 비결정성 알고리즘에서 비결정도가 
그럼 역으로 NP클래스는 P클래스에 포함될까? 다른 말로 하면, 모든 NP 문제는 P 문제일까? 이것이 바로 대망의 P : NP 문제이다.
여기서 잠깐! 앞에서 결정성 알고리즘과 비결정성 알고리즘의 계산 능력이 동일하다고 한 적이 있지 않던가?
하지만 이것은 단순히 해결 가능성에 대한 이야기이지, 복잡도에 대한 것이 아니다. 일반적으로 한 문제에 대해 
이 문제의 답은 아직 확실히 밝혀진 바가 없다.
3.2. NP-완전성
사람들은 P : NP문제의 답에 다가가기 위해 NP-완전성NP-completeness이라는 개념을 도입하였다. 어떤 문제가 NP-완전 문제라는 것은
- 그 자체가 NP 문제이며,
- 다른 모든 NP 문제를 그것으로 다항식 시간 환원시킬 수 있다
는 것을 뜻한다. 여기서 환원reduction은 한 문제를 이용해서 다른 문제를 푸는 것이다. 아래 그림은 문제 A를 문제 B로 환원시킨 것을 도식화 한 것이다. 문제 A와 B의 입출력을 맞추어주기 위한 함수 f, g가 다항식 시간 내에 계산 가능할 때, 이를 다항식 시간 환원polynomial-time reduction이라 한다.
따라서 만약에 우리가 NP-완전 문제들 중 하나에 대한 다항식 시간 결정성 알고리즘을 찾는다면, 모든 NP 문제가 다항식 시간 안에 풀리게 되는 셈이다. 즉, P : NP 문제가 해결된다.
부분집합 합 문제는 NP-완전 문제이다. 다른 NP-완전 문제로는 다음과 같은 것들이 있다.
- 충족 가능성 문제satisfiability problem (SAT)
논리식이 주어졌을 때, 논리값을 참으로 만드는 변수 대입이 존재하는가.
- 해밀턴 경로Hamiltonian path
그래프가 주어졌을 때, 각 꼭지점을 한번씩만 지나는 경로가 존재하는가.
- 순회 세일즈맨 문제traveling salesman problem (TSP)
각 변에 가중치가 주어진 그래프와
가 주어졌을 때, 길이가
보다 작은 해밀톤 회로가 존재하는가.
3.3. P : NP 문제의 의의
P : NP 문제가 풀린다면 그 답이 P = NP이든 P ≠ NP이든 엄청난 일이다.
만약 P = NP임이 증명되면, 지금까지 효율적으로 풀 수 없다고 생각했던 수많은 문제들이 한꺼번에 해결되는 것이다. 물론 다항함수가 지수함수나 기타 비(非) 다항함수보다 항상 작다고만은 할 수 없다. 
반대로 P ≠ NP임이 증명되면, 어떤 문제에 대해서는 명백한 한계가 있음이 밝혀지는 셈이다. 그다지 행복한 결과는 아니지만, 대부분의 컴퓨터 과학자들은 'P ≠ NP'일 것으로 추측하고 있다. 어디까지나 추측일 뿐이지 증명된 바는 전혀 없기 때문에 여기에 너무 얽매일 필요는 없다.
지금까지 P : NP 문제에 대한 웬만한 배경지식은 다 익혔다. 이제 100만 달러가 걸린 문제에 한번 도전해보는 건 어떨까?
