P-NP problem

P-NP problem

P-NP문제를 이해하기 위해 차근차근 기초지식부터 공부해보자.

 

알고리즘과 시간 복잡도

컴퓨터를 사용하여 특정한 계산 문제를 풀기 위해서는, 바로 그 문제에 해당되는 알고리즘을 컴퓨터에게 알려주어야 한다. 그리고 컴퓨터공학자들의 주된 관심사는 그 알고리즘이 문제를 얼마나 빨리 해결할 수 있느냐는 것이다.

시간복잡도 점근적 표기법은 아래와 같다. (Worst case)

$ O(1) < O(\log N) < O(N) < O(N \log N) < O(N^2) < O(N^3) < O(2^N) < O(N!) $

다들 알다시피 어떤 문제를 해결함에 있어 입력의 크기가 N개 일 때, 연산을 해야하는 대략적인 횟수를 가리키는 것이 시간복잡도의 O 표현이다.

 

컴퓨터에게 쉬운 문제와 어려운 문제를 나누는 기준은 O의 괄호 안에 들어있는 식이 n에 대한 다항식인가, n에 대한 지수함수가 들어있다는 것이 중요한 차이점이다.

$ O(1), O(\log N), O(N), O(N \log N), O(N^2), O(N^3) , O(N^k), .... $ 까지 n에 대한 다항식 시간복잡도라고 하고

$ O(2^N), O(N!) ...$ 이상을 비다항식 시간복잡도라고 한다.

다항식 시간 알고리즘이 존재하는 문제는 쉬운(tractable) 문제이고, 다항식 시간 알고리즘이 존재하지 않는 문제는 풀기 어려운(intractable) 문제이다.

 

다행히도 수학/과학적으로 중요한 많은 문제들이 다항식 시간 알고리즘을 가지는 것으로 확인되었다.

• 정렬 문제: n개의 숫자를 입력 받고, 그들을 크기순으로 정렬하는 문제
• 최단경로 문제: 주어진 출발지와 목적지 사이의 최단경로 문제를 구하는 문제

 

그러나 어떤 n자리 자연수를 소인수분해하는 다항식 시간 알고리즘은 아직까지 아무도 찾아내지 못하였다.

 

 

 

P 문제와 NP 문제

• 결정문제: 답이 YES 아니면 NO로 딱 떨어지는 문제. 예를 들어, 'a는 b의 배수인가?'와 같은 질문은 결정 문제이다.

P와 NP 모두 결정 문제에 해당한다.

 

P 문제

결정 문제들 중에서 쉽게 풀리는 것을 모아 놓은 집합이다. 어떤 결정 문제가 주어졌을 때, 다항식 (Polynomial) 시간 이내에 그 문제의 답을 YES와 NO 중의 하나로 계산해낼 수 있는 알고리즘이 존재한다면, 그 문제는 P 문제에 해당된다.

 

n자리 이하의 수 a와 b가 주어졌을 때, a가 b의 배수인지를 판정하는 것은 유클리드 호제법을 사용하면 n에 대한 다항식 시간에 계산할 수 있으므로, 'a는 b의 배수인가?'하는 문제는 P 문제에 해당된다.

위의 정의는 결정적 알고리즘(deterministic algorithm), 즉 계산의 각 단계에서 단 한가지의 가능성만을 고려할 수 있는 알고리즘이 다항시간이 걸리는 문제가 P 문제라는 뜻이다.

 

NP 문제

NP 문제는 결정 문제들 중에서 적어도 검산은 쉽게 할 수 있는 것을 모아 놓은 집합으로도 정의할 수 있다. 다항식 시간 이내에 그 문제의 답을 YES/NO 로 계산해낼 수 있는 알고리즘은 발견되지 않았지만 어떤 결정 문제의 답이 YES일 때, 그 문제의 답이 YES라는 것을 입증하는 힌트가 주어지면, 그 힌트를 사용해서 그 문제의 답이 정말로 YES라는 것을 다항식 시간 이내에 확인할 수 있는 문제가 NP 문제이다.

 

부분 집합의 합

{-5, 6, 1, 2, -10, -7, 13}과 같이 정수 n개로 이루어진 집합이 주어졌다고 할 때, '이 집합의 부분집합들 중에서 원소의 합이 0이 되는 집합이 존재하는가?'라는 문제는 아직까지 다항식 시간 알고리즘이 알려져 있지않다. 누군가가 우리에게 {6, 1, −7}이라는 힌트를 제공하였다면, 이 집합이 원래 집합의 부분집합이라는 사실을 확인하고, 이 집합의 원소의 합이 0이라는 사실을 확인함으로써 원래 문제의 답이 YES라는 것을 어렵지 않게 확인할 수 있다.

따라서 '크기가 n인 어떤 정수 집합이 주어졌을 때, 이 집합의 부분집합들 중에서 원소의 합이 0이 되는 집합이 존재하는가?' 라는 문제는 적어도 NP 문제인 것은 확실하지만, 이것이 P 문제인지 아닌지는 아직 모르는 상황이라고 할 수 있다.

 

해밀턴 경로문제

어떤 그래프가 주어졌을 때, "그래프의 모든 점을 정확하게 한 번씩만 지나는 경로가 존재하는가?"

만약 답이 Yes이고 모범답안으로서 그 그래프상의 모든 점을 정확하게 한 번씩만 지나는 경로가 주어진다면, '그런 경로가 존재한다'는 것을 확인할 수 있을 것이다. 즉, 적절한 모범답안이 주어진 경우 Yes라는 대답은 확인할 수 있다. 따라서 해밀턴 경로 문제는 NP 문제라고 할 수 있다.

 

 

P-NP 문제의 정의

만약 어떤 P 문제가 주어졌고, 그 문제의 답이 YES라면, 우리는 그 문제의 답에 관한 힌트가 주어지면 곧바로 그 문제의 답이 YES라는 것을 쉽게 확인할 수 있을 것이므로, 모든 P 문제는 저절로 NP 문제도 된다. 즉, P⊂NP임을 알 수 있다.

하지만 그 역방향인 NP⊂P에 대해서는 참인지 거짓인지 아직 알려져 있지 않다. 만약 모든 NP 문제가 P 문제인 경우, 즉 모든 NP 문제가 다항 시간에 풀 수 있는 알고리즘이 존재함을 증명할 경우 P=NP라는 결론이 된다. 그래서 P=NP인지, 아니면 P≠NP인지를 묻는 것이 바로 P-NP 문제이다.

조금 더 쉽게 말하면 "쉽게 검산할 수 있는 모든 문제들은 모두 쉽게 풀리는가?" 라고 할 수 있다.

• P=NP: 쉽게 검산할 수 있는 풀기 어려운 공식은 풀기 쉬운 공식으로 변형될 수 있다.
• P≠NP: 풀기 쉬운 공식으로 변형될 수 없는 어려운 문제가 존재한다.
• 증명할 수 없다.

 

 

많은 컴퓨터공학자들 및 수학자들은 절대로 P=NP일 리가 없다고 믿고 있다. 왜냐하면, P=NP라면 어떤 문제가 주어졌을 때 그 문제의 답안을 쉽게 검산할 수 있다면 그 문제 자체도 쉽게 풀 수 있다는, 너무나도 강력한 주장이기 때문이다. 또한, 수많은 학자들이 여러 NP 문제들에 대해서 '다항식 시간 내에 풀 수 있는 알고리즘'을 찾으려고 노력해 왔지만 전혀 성과가 없었기 때문이다. 또 다른 이유로는, 임의의 명제를 증명하는 문제는 NP이고, 검증하는 문제는 P인데, 증명은 검증보다 본질적으로 어려운 문제일 것이므로 NP와 P가 같을 수 없다는 믿음이 있다.

 

 

 

NP 문제에 대해 더 알아보기

1. co-NP문제

다시 해밀턴 경로 문제로 돌아와서 답이 No라고하고 그 증거(답안)로 한 점을 두 번 지나는 경로를 제시한다면 No라고 확신할 수 가 없다. (한 점을 두 번 지나는 경로가 있다고 해서 모든 점을 한 번씩 지나는 경로가 없다는 것은 모순이다.)

즉, No라는 답을 다항시간 안에 확인 할 수 있게 해주는 적당한 모범답안이 존재하지 않고 Yes라는 답만 다항시간 안에 확인 할 수 있게 해주는 적당한 모범답안이 존재한다면 이는 NP 문제이면서 co-NP문제는 아니다.

하지만 No라는 답을 다항시간 안에 확인할 수 있게 해주는 “적당한 모범답안”도 존재한다면, 즉, 그래프의 모든 점을 정확하게 한번 씩만 지나는 경로는 없는가? 라는 문제에 대한 답을 다항시간 안에 확인할 수 있게 해주는 “적당한 모범답안”도 존재한다면, 이는 co-NP 문제이다.

 

종종 NP 문제에 대해서 "P 문제가 아닌 것"으로 설명하는 경향이 있지만, P 문제는 다항식 시간 동안 '답을 찾을 수 있는' 문제이고 NP 문제는 다항식 시간 동안 '주어진 답이 맞는지 확인할 수 있는' 문제이므로 이 둘은 상호배타적인 관계가 아니다. 다항식 시간 내에 직접 답을 구할 수 있다면 당연히 주어진 답이 맞는지 역시 확인할 수 있으므로, '모든 P 문제는 NP 문제이며 그와 동시에 co-NP 문제'이기도 하다.

 

'검산'은 하나의 경우에 대해서 옳은지 그른지 보는 것이고, '해결'은 해답이 되는 경우를 찾을 때까지 모든 경우에 대해 옳고 그름을 따지는 것이다. 따라서 이 문제의 초점을 '문제에서 조합 가능한 경우의 수'로 맞춰서 보면, 문제를 푸는 시간은 최악으로 어림잡아 (중복되지 않는 모든 경우의 개수) × (경우 하나를 검증하는 데 걸리는 최악의 시간)으로 볼 수 있다. 여기서 '중복'이라 하는 것은 부분적인 중복도 포함하는 것이으로, 결국 P-NP 문제의 가장 중요한 쟁점은 이 수학적 귀납법으로 경우의 수를 P의 영역으로 넣을 수 있는지의 여부를 묻는 것으로 볼 수 있다.

대표적인 예로, 정렬 문제의 경우 경우의 수가 n!이지만, 이미 수학적 귀납법으로 $ O(n^2) $, 나아가 $O(n \log n)$으로 수렴된다.

 

 

2. NP-Hard 문제

문제의 난이도 환원

서로 다른 두 문제의 난이도를 비교하는 데에는 환원(reduction)이라고 불리는 기법이 자주 사용된다. 예를 들어, 다음의 두 가지의 문제가 주어졌다고 생각하자.

• 문제 A: 주어진 n개의 숫자를 크기 순서로 정렬하는 문제
• 문제 B: 주어진 n개 숫자의 중간값을 계산하는 문제

어떤 사람이 문제 A를 쉽게 풀 수 있다면, 그 사람은 문제 B도 쉽게 풀 수 있는 것이 당연하다. 왜냐하면 주어진 숫자들을 정렬하고 나면, 그 중 정가운데에 있는 수를 뽑기만 하면 그것이 중간값이 될 것이기 때문이다. 이와 같은 일이 벌어진다면, 문제 B를 문제 A로 환원시킬 수 있다고 표현하며, 문제 B의 난이도는 문제 A의 난이도보다 어려울 수 없다는 것을 알 수 있다.

 

모든 NP 문제를 다항식 시간 내에 A문제로 환원(reduction)할 수 있는 경우, 이 A문제를 NP-난해(NP-hard) 문제라고 부른다. 물론 NP-난해 문제 중에는 NP 문제가 아닌 것도 있다. 즉, NP보다 풀기 어려운 문제도 NP-난해 문제일 수도 있다. 2016년 MIT 연구진이 슈퍼마리오 브라더스가 NP-난해 문제임을 증명해냈다.

 

 

3. NP-Complete 문제

NP-hard임과 동시에 NP인 문제, 즉 모든 NP 문제를 환원시킨 문제가 다시 NP가 될 때, 그 문제를 'NP-완전(NP-complete) 문제'라고 부른다. NP-완전 문제를 풀 수 있으면 모든 NP 문제를 풀 수 있게 되는 셈이므로 NP 문제들 중에서는 가장 핵심이 되는 문제들인 셈이다. 위에서 예로 든 해밀턴 경로 문제도 대표적인 NP-완전 문제들 중 하나이다.

만약 NP-완전 문제가 P 문제라면 '모든 NP 문제가 P 문제'라는 것이 증명되는 셈이다. 바로 이것이 포인트이다. "모든 NP 문제가 사실은 P인데 우리가 변환법을 찾지 못하는 것인가?"라는 명제, 즉 NP=P가 옳으냐 그르냐에 대한 답을 찾는 것. 만약 NP=P라고 증명되면 그 동안의 알고리즘에 대한 연구가 완전히 바뀌는 대격변이 일어나므로, 이 증명은 수학계 뿐만이 아닌 여러 학술 계열의 주목을 받고 있다.

참고로 '어떤 문제를 다항식 시간 내에 해결할 수 있는가 아닌가'는 '그 문제를 해결하는데 평균적으로 얼마나 시간이 걸리는가?'가 아니라 '최악의 경우(worst case)에 시간이 얼마나 걸리는가?'를 기준으로 한다. 즉, '다항식 시간 내에 해결할 수 없는 경우'가 하나라도 있으면 그것은 P 문제가 아니며, P 문제가 아니라고 생각되는 NP 문제라고 하더라도 평균적으로는 다항식 시간 내에 해결할 수도 있다.

 

 

NP 문제의 예시

i. 큰 자연수의 약수를 찾는 문제

그 자연수가 거대한 두 소수의 곱인 경우는 소인수분해를 할 방법이 알려져 있지 않다. 그러나 만약 자연수를 무작위로 뽑는 경우라면 높은 확률로 그 자연수의 약수를 적어도 하나는 찾을 수 있다. 우선 '2로 나누어질 확률'부터가 1/2이며, '2, 3, 5, 7 중 적어도 하나로 나누어질 확률'은 3/4이 넘기 때문이다. 즉, 대부분의 경우에는 약수를 찾을 수 있지만, 그 자연수가 거대한 두 소수의 곱인 경우에는 약수를 찾을 수 없기 때문에 (즉, 약수를 찾을 수 없는 경우가 '존재'하기 때문에) 이 문제는 (현재로서는) P 문제가 아닌 것이다.

 

ii. 외판원 순환 문제 (Travelling Salesman Problem, TSP)

NP-완전 문제'이지만, '무작위 알고리즘'을 이용하면 많은 경우에 비교적 높은 확률로 최적의 해답이나 그에 가까운 것을 찾을 수 있다. 그러나 무작위 알고리즘으로는 모든 경우에 항상 최적의 해답을 찾을 수 있는 것은 아니기 때문에 이 문제는 P 문제가 아니다.

 

iii. 스도쿠

풀이법 자체는 초등학생도 이해할 수 있을 만큼 직관적이나, 다항 시간 내에 풀 수 있는 풀이법이 없다.

 

iv. N-Queen 문제

8-Queen 문제를 일반화한 'N-퀸 완전 문제'가 NP-완전에 속한다고 발표하면서 무려 10억 원의 상금이 걸린 체스 문제가 탄생했다. N-퀸 문제는 크기 n×n 체스판에 n개의 퀸을 서로 공격하지 않는 위치에 배치하는 문제다. 규칙은 간단하지만 8x8부터는 풀기가 만만치 않다.

 

 

---

Example

• Graph coloring - no one knows
• Euler tour - typical
• Hamiliton cycle - intractable, classic NP-complete problem
• Graph isomorphism - no one knows

 

how difficult?

• any programmer could do it
• typical diligent alogrithms student could do it
• hire an expert
• intractable.
• no one knows.
• Impossible