P-NP문제

 

P는 np에 속하지만, np가 p에 속하는지는 밝혀지지 않았다.

P는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이다.
NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합

비결정론적 튜링 기계(nondeterministic Turing machine, NTM)는 튜링 기계에서 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말한다. 이것은 비결정론적 유한 오토마타와 유사한 개념이다.
이동 가능성이 하나로 정해져 있는 결정론적 튜링 기계와는 반대로, 이 기계에서 이동할 수 있는 상태의 개수는 상황에 따라 다르며, 여러 개가 되거나 아예 없을 수도 있다.

 

NTM으로, TM을 나타낼 수 있다. NTM의 무수한 상태이동 경로중 TM의 상태이동경로가 있을 것이기 때문에, TM으로 NTM의 이동경로를 나타낼 수 있는가?

NTM중에는 확률적 튜링 기계(Probabilistic Turing machine, 비결정론적 튜링 기계의 하나로, 기계의 다음 상태가 확률적으로 정해지는 성질을 가진다.)도 있다.

PTM에서 A상태에서 B,C,D로 갈 확률이 각각 30%라고 하자, 이것을 TM으로 구현해 내는 것이 가능한가? TM에서는 A의 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있다. 원천적으로 이동하는 하나의 상태가 정해진 이상 나머지 상태로 갈 가능성은 차단된다. 이렇게만 판단하면, TM으로 PTM를 구현할 수 없다.

PTM로 TM을 구현할 수는 있나?, A상태에서 다른상태로 이동하는 TM의 경로를 A상태에서 확률적으로 포함시키면 되기에, PTM은 TM을 포함시킨다. 즉 비결정론적 튜링기계는 결정론적 튜링기계를 자신의 내부에 포함시킨다.

TM으로 다항시간 안에 풀 수 있는 판정문제는, NTM으로도 다항시간 안에 풀 수 있다고 증명이 되었다고 한다. 문제는 NTM으로 다항시간 안에 풀 수 있는 모든 문제들이, TM으로 다항시간 안에 풀 수 있느냐 하는 것. 단순히 생각을 해보았을 떄, TM으로 NTM을 구현해내지 못해내니, TM으로 다항시간안에 못풀어 내는 NTM이 있을 것 같다.

언뜻 단순해 보이는데, 이게 단순하다면 왜 그렇게 많은 사람들이 NP=P가 아니라는 것을 증명해내지 못한걸까? 그것은 단 하나의 Np complete문제도 P problem에 포함되거나, 포함되지 않는 것을 증명해내지 못했기 때문이다.

왜 어려울 수 밖에 없는가? P problem과는 달리, NP complete는 비결정론적 튜링머신으로 판정하는 문제이므로 일반적인 해법이 있을 수가 없기 때문이다. 퍼지이론과 같이 애매한 것을 정량화 시키는, 즉, 일반적이지 않은 것을 일반적으로 다루려는 기법들이 있으나, NTM의 본질적인 특성상 일반적인 해법을 찾는 것은 역시 불가능한 시도 같다.

NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있다. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P=NP의 형태로 풀리게 된다. 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어 P-NP 문제는 P≠NP의 형태로 풀리게 된다.

P는 NP에 속하기에 P를, NP로 환원할 수 있으며, 모든 NP문제는 NP complete로 환원될 수 있다,즉 모든P는 NP complete로 환원되어 진다. 다시 말해 문제의 키 포인트는 NP complete가 P로 환원될 수 있느냐 없느냐 하는 것, NP complete가 P로 환원되어 진다면, NP complete도, TM으로 다항시간안에 풀어 낼 수 있게된다. 즉, NP가 complete가 P로 환원되어지기 위해서는 NTM으로 다뤄지는 문제가 TM의 문제로 환원되어져야 한다는 것이고, 이것은 NP문제에 일반적인 해법이 있음을 의미한다.

소수를 찾는 일반적인 해법이 존재한다면, NTM문제가, TM문제로 환원되고, 다항시간안에 답이 도출된다는 것을 의미한다. 결국 NP complete은 P에 속하게 되어 NP=P가 성립하게 된다. 소수의 일반적인 해법을 찾으려는 시도는 전부 NP=P임을 증명하기 위한 시도와 같다.

 

-reference

https://ko.wikipedia.org/wiki/P-NP_%EB%AC%B8%EC%A0%9C

https://ko.wikipedia.org/wiki/NP-%EC%99%84%EC%A0%84

-연관 키워드

복잡도, 결정문제, 오토마타, 리만가설, 해석적 정수론, 휴리스틱, 리만제타함수, 원자론, 양자역학