어떠한 문제가 답을 하기 쉬운 문제이고, 어떠한 문제가 답을 하기 어려운 문제인가? 답을 구하는 데 걸리는 시간이 짧은 문제가 쉬운 문제이고, 그렇지 않은 문제는 어려운 문제이다.
7을 100번 더하는 문제를 생각해 보자
어떤 사람 구구셈을 모른다면 처음부터 7을 한번씩 100번에 걸쳐 더하여 답을 낼 것이다. 하지만 구구셈을 배운 사람은 7x100=700이라고 금방 답을 구한다. 구구셈을 이용하는 경우 그냥 더하는 방식보다 쉬운 문제가 된다
또 다른 보기를 들어,두 자연수 70 과 1106 의 최대공약수를 구하여 보자.
어떤 사람은 이 문제를 다음과 같이 풀려고 할 것이다: 우선 70의 약수를 모두 구하고 1106의 약수를 모두 구한 다음 이 두 약수 집합의 공통 부분을 구하고, 그 중에서 가장 큰 것을 답으로 한다. 하지만 유클리드의 호제법을 "배운 사람"은 그렇게 오랜 시간을 써가며 구하지 않아도 된다: 먼저 1106 을 70 으로 나눈 나머지 56 을 얻고 70 을 56 으로 나눈 나머지 14 를 얻은 다음 56 이 14 로 나누어 떨어짐을 알고 14 를 답으로 내 놓는다:
1106 ≡ 56 (mod 70)
70 ≡ 14 (mod 56)
56 ≡ 0 (mod 14).
P문제와 NP 문제
답을 구하기 위하여 시행하는 연산의 수가 입력 길이에 대한 다항식에 지배되는 알고리듬을 다항시간 알고리듬(Polynomial Time Algorithm)이라 부르고, 다항시간 알고리듬이 존재하는 집단문제---즉, 풀기 쉬운 집단문제 전체집합을 ‘P문제’로 나타낸다.
정렬문제: 1 부터 n 까지의 자연수가 순서 없이 한 자씩 적혀 있는 n 장의 카드를 순서대로 정렬하는데 얼마나 시간이 걸리는 지 살펴보자.
특별한 기교를 부리지 않고, 우선 1 이 어디에 있는지 살펴보는데 n 이하의 시간이 걸리고, 그 다음 2 가 어디에 있는지를 살펴 보는데 n-1 이하의 시간이 걸리고, 최악의 경우라도 n(n+1)/2 시간이 주어지면, 카드를 정렬할 수 있다. 그러므로 정렬문제는 쉬운 집단문제이다.
실제로 좋은 알고리듬으로 정렬하면 걸리는 시간은 O(n log n) 정도로 단축할 수 있다. 정렬을 위한 알고리듬은 비단 이러한 카드뿐 아니라, 50명의 수학 답안지를 성적순으로 정렬하여야 하기도 하고, 문서 편집기에서 잘못 사용한 단어를 찾아 고치는 search-replace 기능을 위하여도 필요하고, 도서관의 백만권 자료 중에서 원하는 것을 실시간에 찾고, 전화교환원이 원하는 곳의 전화번호를 재빨리 알려주며, 인터넷을 빠른 시간 안에 뒤지는 것을 가능하게 한다.
어떤 집단문제들은 어려워 보이기는 하지만, 그 답을 보면 옳다는 것을 검증하기가 쉬운 그러한 집단문제들이 있다. 마치 평범한 고등학생들이 ``수학의 정석''과 낑낑대고 씨름하다가 포기하고는 해답을 보고 나서 "아! 바로 그것이구나" 하듯이. 이러한 집단문제---미정다항시간집단문제(Nondeterministic Polynomial time problem)들의 집합을 ‘NP문제’라 한다.
따라서 NP문제는 풀기에는 쉽지 않을 수 있지만 답이 맞는지 확인하기는 쉬운 문제이다. 어떤 문제가 풀기는 쉽지 않다고 하는 경우에도 어떤 머리좋은 사람이 적당한 알고리즘을 만들어내면 다항식만큼의 시간에 풀 수 있지는 않을까?
합성수판정: 명제 "4,003,997 는 합성수이다"가 참이라는 것을 확신하려면 제법 생각해야 한다. 하지만 이 수가 1999 과 2003 의 곱이라는 것을 보이는 것은 쉽다
1999 ×2003 = (2000 -1) ×(2000 + 3) = 4,000,000 + 4,000 - 3 = 4,003,997
수학자들은 "소인수 분해가 어렵다"는 점을 인정하지만 이에 대한 보편적인 증명이 나오기 전까지는 그것이 옳다고 말하지 않는다.
다항식 시간 안에 답을 구하는 알고리듬이 있는 문제가 바로 NP 에 속하는 문제이다.
이 정의는 ``쉽게 검증할 수 있는 증명서(certificate)를 가진 문제''로 정의하는 것과 동치임이 알려져 있다.
--------------------------------------------------
NP문제의 예시 ~ <제로존이론>
'자연을 이루는 기본은 무엇이며 몇개인가?'라는 화두는 NP문제이 면서 <제로존이론>에 의해 학술적인 논문으로 그 해법이 밝혀진 셈이다.
위의 질문을 'NP 문제'로 보는 이유는 다음과 같은 두가지 NP문제의 핵심적인 특징을 잘 나타내고 있기 때문이다
1. 노벨물리학상을 받은 과학자들까지 가세하여 '자연을 이루는 기본이 무엇이며 몇개인가?'라는 질문에 대한 답을 찾고자 했으나,
그 토록 오랜 과거 세월을 지나면서도 아무도 찾지 못한 어려운 문제로 남아 있었다.
=> 이는 NP문제가 되기 위한 첫번 째 조건에 해당한다.
(처음부터 쉬운 문제는 NP문제가 아니라 P문제가 된다)
2. CODATA의 학술지 Data Science Journal에 심사를 통해 게재된 <제로존이론> 논문을 통해 '자연을 이루는 기본은 한 개이며, 그 것은 무차원수 '1'이다'라는 새로운 이론을 과학적인 방법으로 찾았다.
또한 논문을 통해 밝힌 이론적인 방법과 답을 '알고 보니 쉬운 문제'라는 것이다.
=> 이는 NP문제가 되기 위한 두번 째 조건에 해당합니다.
(쉬운 해답을 찾지 못하면, NP문제가 아니라 '진짜 어려운 문제' 또는 '풀 수 없는 문제'에 해당한다)
---------------------------------------------
물론 P 가 NP 의 부분집합이기는 하지만, NP 가 P 와 다르다는 것이 증명된 것은 아니다.
Clay 수학연구소에서 현상금을 건 밀레니엄 문제가 바로
‘NP문제와 P문제는 동일하다는 것을 증명할 수 있는가?("P = NP ?") 하는 문제이다.
이 문제는 다른 말로
'P문제가 NP문제가 다르다는 것을 증명할 수 있는가?("P ≠ NP ?")' 하는 문제와 마찬가지이다.
이것은 어떤 문제를 해결하는 알고리즘에서 답을 알고 있을 때와 없을 때 풀이에 시간 차이가 있는지에 관한 것이다.
가령 모임에 참석했을 때, 참석할 사람이 자신 친구라는 것을 미리 알면 그것을 모를 때보다 '참석인원이 모두 아는 사람'이라는 사실을 빨리 알 수 있는지를 증명하는 것이다. (NP 문제 예)
어느 토요일 저녁 당신이 규모가 큰 파티에 참석했다고 가정하자.
아는 사람이 혹시 있는지 두리 번 거리고 있을 때, 파티의 주인공이 와서 저쪽 구석에 당신이 아는 사람이 참석해 있다고 알려 준다면 그 쪽을 처다 보는 순간 그렇구나 하고 고개를 끄덕일 것이다.
그렇지 않다면 당신은 아는 사람을 찾기 위하여 참석자 얼굴을 일일이 처다 보며 파티장 안을 돌아 다녀야 할 것이다.
이것은 문제에 대한 해결을 찾는 일이 주어진 해결책이 맞는가를 확인하는 것보다 더 많은 시간이 걸린다는 일반적 현상을 말해주는 좋은 예가 될 것이다
어려운 문제
물론 모든 집단문제가 다 쉬운 것은 아니다. 어려운 집단문제의 보기로는 하노이 탑 문제라고 부르는 것이 있다. 이 문제는 1883년에 Lucas 라는 오락 수학자가 만든 문제로 다음과 같다.
티벳의 한 고원에 n 층 탑이 있는데, 이 탑의 위치를 다른 곳으로 옮겨야 한다. 이 때 맨 위층부터 차례로 옮겨야 하고, 각 층들을 놓아 둘 수 있는 곳은 현재 자리, 옮길 자리, 여분의 한 자리뿐이다. 그리고 낮은 층을 높은 층 위에 쌓아서는 안된다. 과연 몇번 만에 이 탑을 다 옮길 수 있을까?
n 층 탑을 옮기는 데 걸리는 시간을 T(n) 이라 하면 점화식
T(n) = 2 T(n-1) + 1, T(1) = 1
을 쉽게 얻고, 따라서 T(n) = 2n -1 임을 안다. 이 문제는 탑의 층수가 증가함에 따라 해결하는데 걸리는 시간이 기하급수적으로 증가하고, 따라서 어려운 문제이다. 만약 63 빌딩을 1초에 한 층씩 옮긴다면 3천억년 이상이 걸린다.
어떤 집단문제가 쉽다는 것을 보이는 것은 쉽다: 그 집단문제를 해결하는 다항식 알고리듬을 보여주기만 하면 된다.
그러나 어떤 집단문제가 어렵다는 것을 보이는 것은 어려운 일이다. 왜냐하면 어떠한 알고리듬도 쉬운 것이 없다는 것을 증명하는 것이 어렵기 때문이다
풀 수 없는 문제
어떤 문제는 너무나 어려워서 풀리지 않는 것도 있다. 보기로는 타일링 문제: 임의의 다각형 집합이 평면 타일링을 하는가를 판정하는 문제 를 들 수 있다. 다각형의 종류가 불가산수이기 때문에 가산수의 기계들로 해결할 수 없는 것은 당연하다. 그러나 다각형을 "동서남북 각변에 색을 칠한 정사각형" 또는 "폴리요미노"로 한정하더라도 판정불가능하다.
판정 문제 중에서 가장 유명한 것 중의 하나가
Hilbert 의 열번째 문제라고 부르는 Diophantus 방정식에 관한 것이다.
Hilbert 의 열번째 문제: 일반 정수방정식 p(x1, ... , xn) = 0 이 정수해를 가지는 지를 판정할 수 있는 알고리듬이 존재하는가?
1970년에 Matiyahsevich 는 이 문제에 대한 부정적인 답을 하였다.
또 다른 보기로는 1914년 A. Thue 가 질문한 문제
단어 문제(word problem): 일반 자유군의 원소 a0, a1, ... , an 에 대하여 a0 은 a1, ... , an 이 생성하는 부분군의 원소인가? 이다.
이 문제도 1947년에 E. Post 와 A. Markov 에 의하여 판정 불가능하다는 것이 밝혀졌다 .
댓글 없음:
댓글 쓰기