====== P = NP ======

**[[P복잡도|P]]** = **[[NP복잡도|NP]]**. <del>[[전산학]]의 초대형 [[떡밥]]</del> [[복잡도종류]] **P**와 **NP**의 관계에 대한 문제. [[밀레니엄문제]] 일곱 개 중 하나로, 이게 참이라는 결과가 만에 하나 나온다면 [[전산학]] 뿐만 아니라 온갖 엉뚱한 곳에서 폭풍이 몰아칠 것이 분명하다. 물론 거짓이라고 하더라도 드럽게 어려운 문제인 건 사실이다.

쉽게 설명하면, **P**와 **NP**가 같다는 말은 "문제의 해답을 쉽게 검증할 수 있다면 문제를 쉽게 푸는 방법도 존재한다"를 엄밀하게 써 놓은 것이다. 예를 들어서 [[부분집합합문제]](SUBSET-SUM)는 [[정수]]의 [[집합]]을 가져다 놓고 이 집합의 [[부분집합]] 중 그 합이 0이 되는 게 있는지 없는지를 알아 내는 건데, 집합 {-7, -3, -2, 5, 8}만 주고 여기서 합이 0이 되는 부분집합이 있냐고 물으면 삽질을 좀 해야 하지만, 부분집합 {-3, -2, 5}를 들고 와서 맞냐고 확인해 달라 하면 합을 계산해 보고 부분집합이 정말로 맞는지 확인하는 것으로 충분한 것이다. **P**와 **NP**가 만에 하나 같다면, 사실은 우리가 모르긴 하지만 이 문제를 답 검증하는 것만큼이나 쉽게 하는 방법이 존재한다는 얘기니 경천동지할 일이 아닐 수 없다. 이 때문에 증명은 안 되긴 했지만 많은 사람들이 **P**와 **NP**가 사실은 다를 거라는 생각을 많이 하고 있다.

좀 더 엄밀하게 말하면, **P**는 [[결정적튜링기계]]에서 다항 시간 안에 풀 수 있는 문제의 집합이고, **NP**는 [[비결정적튜링기계]]에서 다항 시간 안에 풀 수 있는 문제의 집합이다. 또한 NP가 결정적 튜링 기계에서 알고리즘의 입력, 출력 및 입력 길이의 다항식에 비례하는 크기의 추가 정보(certificate라고 부른다)만 가지고 다항 시간 안에 그 출력이 맞는지 검증할 수 있는 문제의 집합과 같다는 것도 잘 알려져 있다. 따라서 **P**가 **NP**의 부분집합임은 분명한데, 문제는 반대도 성립해서 사실 **P** = **NP**인지, 아니면 **P**가 **NP**의 [[진부분집합]]인지는 아무도 모른다는 것이다. 게다가 전산학에서 흥미로운 많은 문제들이 **NP**에 속하거나 적어도 **NP**만큼은 어렵다([[NP-난해]])는 게 알려져 있지만, 보통 **P**에 속하지 않는 문제는 손을 댈 만한(tractable) 문제가 아니라고 보기 때문이다. (그래서 **P**에 속하지 않는 것처럼 보이는 문제는 보통 [[근사문제]]가 활발하게 연구된다. 실용적으로 쓰려면 이러는 수 밖에 없다.)

===== 상황 =====

[[2011년 현재]] 이 문제는 여전히 오리무중으로 남아 있다. 게다가 설상가상으로 계산 복잡도 분야에서 흔히 쓰이는 웬만한 증명 기법들이 이 문제에는 적용 불가능하다는 게 알려져 있어서, 문제를 풀면서 새로운 증명 기법을 만들어야 한다(!)는 무시무시한 상황이 되고 있다.((예를 들어서, 어떤 [[신탁기계]]를 써도 문제의 복잡도가 바뀌지 않는다면 그 문제는 신탁 기계 없이도 같은 복잡도를 가지게 된다. 이를 사용한 증명을 상대화(relativization)라 하는데, 문제는 신탁 기계 **X**를 줬을 때 **P**<sup>**X**</sup> = **NP**<sup>**X**</sup>인 놈도 있고 **P**<sup>**X**</sup> ≠ **NP**<sup>**X**</sup>인 놈도 있다는 거다.)) 반대로 말하면 이 문제를 푸는 사람은 적어도 계산 복잡도 분야에 혁명을 불러 **와야** 하거나, 아니면 [[NP-완전]] 문제를 다항 시간에 풀어야 한다는 얘기가 되겠다. <del>그러니 어렵지</del>

이런 어려움과 더불어 밀레니엄 문제라는 유명세 때문에 온갖 잘못된 증명이 쏟아지고 있어서, 흡사 [[페르마의마지막정리]]가 증명되기 전의 모습을 보는 것 같다. [[김양곤]] 교수와 같이 거의 개뻥을 치고 있는 경우도 있으며, 비교적 최근(2010년)에는 [[휴렛패커드]] 연구소의 연구자인 Vinay Deolalikar가 진지한 증명을 시도하며 센세이션을 불러 일으켰으나 결정적인 오류가 발견되면서 해프닝으로 그치는 추세이다.((Polymath 위키에 [[http://michaelnielsen.org/polymath1/index.php?title=Deolalikar_P_vs_NP_paper|관련 페이지]]가 있다.)) 혹자는 이 센세이션 덕분에 수학계 및 전산학계 말고도 일반 대중이 얼마나 이 문제에 관심이 있었는가를 다시금 확인할 수 있었다고 할 정도.

한편으로는 단순히 **P** = **NP**인지의 여부를 떠나서 **NP**의 내부 구조를 알아 내려는 노력도 존재한다. 예를 들어서, **NP**에는 속하는데 **P**에 속하는지도 **NP**-완전인지도 알려지지 않은 문제들이 매우 드물게 존재하는데, 현재 이 목록에는 [[그래프동형사상문제]](GI)와 [[소인수분해]] 문제 **단 두 개**만 들어 있다. 이 때문에 사실은 **NP**보다 작고 **P**보다는 큰 복잡도 종류가 존재하는 거 아닌가 하는 의심도 있다. (이 상황을 대비하기 위해 그래프 동형사상 문제에는 아예 대놓고 별도의 복잡도 종류 **GI**가 할당되어 있다.)

===== 관련된 문제 ===== 

**P** = **NP**와 **[[FP복잡도|FP]]** = **[[FNP복잡도|FNP]]** 문제는 동치이다. 즉 [[결정문제]]를 [[함수문제]]로 바꿔도 상황은 똑같다.

좀 더 비직관적인(?) 예로는, **P** = **NP**와 **[[BPP복잡도|BPP]]** = **P** 중 많아봐야 하나만이 성립한다는 것이 알려져 있다.(([[http://terrytao.wordpress.com/2008/01/10/distinguished-lecture-series-i-avi-wigderson-the-power-and-weakness-of-randomness-in-computation/|Distinguished Lecture Series I: Avi Wigderson, “The power and weakness of randomness in computation”]])) 이게 뭔 개소리인가 하니, 만약 흔히 생각하는 것대로 **P**가 **NP**랑 다르다면, 확률적인 방법("2/3 확률로 옳은 답을 낸다" 따위)으로 문제를 풀 수 있다면 이걸 정석으로 푸는 방법을 만들 수 있다는(derandomization) 어이 없는 결과가 나온다. (**P**가 **BPP**의 부분집합임은 자명하니까) 어느 쪽이든 상당히 어이 없는 결과인 건 분명하다.

{{tag>수학 전산학 밀레니엄문제}}