P = NP

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

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

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

상황

2011년 현재 이 문제는 여전히 오리무중으로 남아 있다. 게다가 설상가상으로 계산 복잡도 분야에서 흔히 쓰이는 웬만한 증명 기법들이 이 문제에는 적용 불가능하다는 게 알려져 있어서, 문제를 풀면서 새로운 증명 기법을 만들어야 한다(!)는 무시무시한 상황이 되고 있다.1) 반대로 말하면 이 문제를 푸는 사람은 적어도 계산 복잡도 분야에 혁명을 불러 와야 하거나, 아니면 NP-완전 문제를 다항 시간에 풀어야 한다는 얘기가 되겠다. 그러니 어렵지

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

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

관련된 문제

P = NPFP = FNP 문제는 동치이다. 즉 결정문제함수문제로 바꿔도 상황은 똑같다.

좀 더 비직관적인(?) 예로는, P = NPBPP = P 중 많아봐야 하나만이 성립한다는 것이 알려져 있다.3) 이게 뭔 개소리인가 하니, 만약 흔히 생각하는 것대로 PNP랑 다르다면, 확률적인 방법("2/3 확률로 옳은 답을 낸다" 따위)으로 문제를 풀 수 있다면 이걸 정석으로 푸는 방법을 만들 수 있다는(derandomization) 어이 없는 결과가 나온다. (PBPP의 부분집합임은 자명하니까) 어느 쪽이든 상당히 어이 없는 결과인 건 분명하다.

1) 예를 들어서, 어떤 신탁기계를 써도 문제의 복잡도가 바뀌지 않는다면 그 문제는 신탁 기계 없이도 같은 복잡도를 가지게 된다. 이를 사용한 증명을 상대화(relativization)라 하는데, 문제는 신탁 기계 X를 줬을 때 PX = NPX인 놈도 있고 PXNPX인 놈도 있다는 거다.
2) Polymath 위키에 관련 페이지가 있다.

도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2016-07-05 10:56 | 작성자 lifthrasiir