전 포스팅에서 언급한 P-NP 문제를 들고 왔습니다. P-NP 문제는 밀레니엄 문제 중 가장 간단하고 명료한 문장으로 설명됩니다.
'P 집합과 NP 집합은 같은가?'
P는 Polynomial의 NP는 Non-deterministic Polynomial의 약자입니다. 문장만 간단하지 P 집합과 NP 집합이 대체 뭐냐!라고 물으시는 분들이 계실 겁니다. 전 포스트에서 소개했던 시간 복잡도라는 개념이 여기서 등장합니다.
100자리 숫자를 더하는 데 컴퓨터는 얼마나 걸릴까?
두 100자리 숫자를 더하는 데에 걸리는 시간을 O(100)라고 합시다. 500자리 숫자를 더하는 데에는 O(500)이 됩니다. n자리 숫자의 경우 O(n)이 되죠. O(n)이 바로 시간 복잡도입니다. 더하기는 고작 n의 1승에서 노는 거죠. 곱셈의 경우는 O(n^2)이 됩니다. 여기까지도 다항식이기에 간단히 풀 수 있습니다. 하지만 n자리의 패스워드를 구하는 방법은 O 안에 들어가는 숫자가 몇일까요? 영어로만 해도 26개의 알파벳이 있습니다. 즉, O(26^n)이 됩니다. 지수함수적으로 증가하는 난이도는 컴퓨터가 풀 수 없습니다. 이런 문제들은 알고리즘적인 가치가 없고 따라서 우리는 Polynomial, 즉 다항 시간 해법을 가지는 문제들에만 집중합니다.
문제의 난이도를 비교하는 것은 두 문제 중 한 문제를 풀면 다른 문제를 풀 수 있는가로 알 수 있습니다. 5개의 숫자를 크기 순으로 배열하는 문제와 5개의 숫자 중 가장 작은 값을 찾는 문제 중 어떤 문제가 더 쉬울까요? 직관적으로 후자가 더 쉽습니다. 그를 수학적으로 설명하면 1번 문제를 풀면 2번 문제는 자동으로 풀 수 있지만 2번 문제를 풀어도 1번 문제를 풀 수는 없습니다.
그래서! P 문제와 NP 문제는 무엇이냐!
P 문제와 NP 문제는 모두 결정 문제입니다. YES or NO죠. P문제는 다항식 시간 내에 풀 수 있는 알고리즘이 존재하는 문제입니다. 위에 예로 들었던 숫자를 크기 순으로 정렬하는 문제는 P 문제죠. NP 문제는 조금 까다롭습니다. 비결정적 다항 시간 알고리즘이 존재한다고 표현합니다. 이를 쉽게 풀어 설명하면 답을 알려주면 그 답을 다항식 시간내에 검산할 수 있는 문제가 NP 문제입니다. NP 문제의 예로는 한붓그리기와 RSA 암호가 존재합니다. 한붓그리기의 해법을 다항 시간 내에 푸는 방법은 알려져있지 않습니다. 그러나 그 경로가 주어지면 그게 맞는지는 다항 시간 내에 확인할 수 있죠. RSA 암호 또한 암호를 알면 풀 수 있지만 암호를 다항 시간 내에 구할 수는 없습니다.
이제 P 문제와 NP 문제가 무엇인지까지는 설명이 된 것 같습니다. P 문제는 당연하게도 NP 문제의 부분 집합입니다. 애초에 해법을 아는데 검산을 못할 리가 없죠. 그렇다면 과연 P=NP인가? P=NP라는 명제는 너무나 유혹적입니다. '검산할 수 있는 문제라면 풀 수 있다!'라는 것이죠. 그래서 대부분의 학자는 P=NP일리 없다고 생각합니다. 그러나, P와 NP가 같지 않음을 아무도 증명하지 못했고 못하고 있습니다.
비결정적 튜링 머신인 양자 컴퓨터가 NP 문제 중 일부를 다항 시간 내에 해결할 가능성이 있다고 합니다. 찍어서 맞추는 것이죠. 다만 엄청나게 빠르게 찍어서 다항시간 내에 맞춘다는 것입니다. 결국 P=NP, P≠NP 중 어느 것이 맞을지는 모릅니다. P=NP가 맞다면 어마어마한 파장이 일어날 것이고 개인적으로는 드라마같은 그런 결말을 기대하기도 합니다. P≠NP가 맞다면 저같은 일부 사람은 실망하겠지만 세상은 흘러가던대로 흘러갈 것입니다. 과연 이 밀레니엄 문제들이 이번 밀레니엄에 해결이 될지 그 귀추가 기대됩니다.
