P-NP문제란?

문제는 크게 2가지, 쉬운 문제와 어려운 문제가 있다. 문제를 해결하는 사람의 입장이라면, 아마도 쉬운 문제를 푸는 것이 시간, 비용 측면에서 효율적이다. 만약에 모든 어려운 문제를 쉬운 문제로 바꿀 수 있는 방법이 있다면, 당연하게도 어려운 문제를 쉬운 문제로 바꿔서 풀면 된다. 이러한 방법이 과연 존재하는가? 이것이 P-NP문제의 핵심이다.

 

알기 쉽게 쉬운 문제를 P문제, 어려운 문제를 NP문제라고 생각하자.

P-NP 문제가 중요한 이유는?

만약 열쇠가 존재하는 것이 증명된다면, 열쇠를 찾는 일이 어렵지만 찾으려고 노력하는 것은 의미있는 일이 된다.

만약 열쇠가 존재하지 않는 것이 증명된다면, 찾으려고 노력하지 않아도 된다.

알고리즘을 찾아야하는지에 대한 해답을 제공하므로 P-NP문제의 해결은 문제 해결에 있어 중요하다. 물론 그러한 열쇠가 존재한다고 증명된다해도 그 열쇠를 찾기란 쉽지 않을 것이다.

P-NP 문제는 2000년 클레이 수학연구소가 100만달러를 건 밀레니엄 문제 중 하나이다.

이 문제는 1956년 쿠르트 괴델(Kurt Godel)이 존 폰 노이만(John von Neumann) 에게 쓴 편지에서 처음 언급되었다.

여기서 쿠릍느 괴델은 불완전성 정리를 증명한 미국의 수학자이고, 존 폰 노이만은 컴퓨터 중앙처리장치의 내장형 프로그램을 처음 고안한 미국의 수학자이다.

괴델은 어떤 완전 NP문제가 2차 혹은 선형 시간 안에 풀릴 수 있을지 노이만에게 물었다고 한다.

다항시간

공식적인 논문으로 P-NP 문제를 제기한 학자는 스티븐 아서 쿡(Stephen Arthur Cook) 이다. 스티븐 아서 쿡은 토론토 대학의 수학과 교수로 ACM(SIGACT Symposium on the Theorey of Computing) 에 기재된 논문 <정리 증명 절차의 복잡성> <The Complexity of Theorem Proving Produres> 에서 P-NP문제를 제기했다.

P문제는 무엇인가?

P문제란 결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합을 말한다. 즉, 이미 결정되어 있는 숫자를 찾는 결정론적 다항시간문제(Deterministic Polynomial Time Problem) 이다.

결정론적 튜링기계

NP문제란 비결정론적 튜링 기계를 사용해 다항시간 내에 답을 구할 수 있는 문제의 집합을 말한다. 즉, 결정되지 않은 숫자의 패턴을 찾는 비결정론적 다항시간문제9?Non-Deterministic Polynomial Time Problem) 이다.

비결정론적 튜링기계

여기서 말하는 튜링 기계(Turing Machine) 이란? 앨런 튜링(Alan Turing) 이 소개한 가상 기계로 메모리가 무한대인 컴퓨터라 생각하자.

 

* 결정론적 튜링기계 : 어떤 상태에서 다음 행동이 1개로 정해진 기계

* 비결정론적 튜링기계 : 어떤 상태에서 다음 행동이 1개 이상인 기계

 

이제 P문제, NP문제의 예를 살펴보면

※ P문제의 예시

 

1. n개의 사탕 중 특정한 사탕 2개를 뽑는 경우

특정사탕 2개를 뽑는 경우

2. n개의 숫자를 오름차순으로 정렬하는 경우

오름차순 정렬

※ NP문제의 예시

1. 어떤 정수 집합에서 부분집합의 원소의 합이 0인지 묻는 문제

NP문제

이 문제는 여러가지 행동이 가능하다.

 

P문제와 NP문제의 결정적인 차이점은 시간복잡도이다. 시간복잡도(Time Complexity)란? 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 말한다. 이 시간 복잡도를 표현하는 방법은 빅O 표기법(Big-O)이다.

빅O의 대소관계

P-NP 문제는 P문제가 NP문제와 같은지 묻는 문제로 복잡하고 어려운 문제들도 알고리즘에 맞혀 다항시간에 반드시 풀 수 있는 것이다. 하지만, NP를 P로 바꾸는 알고리즘이 존재한다는 것만을 알게 되는 것이고 그 알고리즘을 찾는 일은 어려울 수 있다. 만약, 그 알고리즘을 찾아낸다면, 비결정론적 튜링 기계의 엄청난 과정들이 결정론적 튜링 기계의 과정들만 거치게 되는 것이다.

P문제-NP문제