P문제와 NP문제(NP-hard)

답이 YES 아니면 NO로 반환되는 문제를 결정 문제라고 한다. 예를 들어, 'a는 b의 배수인가?'와 같은 질문은 결정 문제이다. P와 NP 모두 결정 문제의 분류에 해당한다.


P 문제는 결정 문제들 중에서 쉽게 풀리는 것을 모아 놓은 집합이다. 어떤 결정 문제가 주어졌을 때, 다항식(Polynomial) 시간 이내에 그 문제의 답을 YES와 NO 중의 하나로 계산해낼 수 있는 알고리즘이 존재한다면, 그 문제는 P 문제에 해당된다. n자리 이하의 수 a와 b가 주어졌을 때, a가 b의 배수인지를 판정하는 것은 유클리드 호제법을 사용하면 n에 대한 다항식 시간에 계산할 수 있으므로, 'a는 b의 배수인가?'하는 문제는 P 문제에 해당된다.


위의 정의는 결정적 알고리즘(deterministic algorithm), 즉 계산의 각 단계에서 단 한가지의 가능성만을 고려할 수 있는 알고리즘이 다항시간이 걸리는 문제가 P문제라는 뜻이다. NP 문제는 형식적으로는, 문제를 푸는 각 단계에서 여러가지의 가능성을 동시에 고려할 수 있는 비결정적 알고리즘(non-deterministic algorithm)으로 다항시간내에 문제를 해결할 수 있는 문제라고 정의한다. 즉 NP는 Non-deterministic Polynomial의 약자이다. 하지만 인간의 머리는 비결정적 알고리즘의 작동을 잘 이해 못하는 경우가 많아서인지, 검산 위주의 정의가 쓰일 때도 많다.

NP 문제는 결정 문제들 중에서 적어도 검산은 쉽게 할 수 있는 것을 모아 놓은 집합으로도 정의할 수 있다. 정확히 말하면, 어떤 결정 문제의 답이 YES일 때, 그 문제의 답이 YES라는 것을 입증하는 힌트가 주어지면, 그 힌트를 사용해서 그 문제의 답이 정말로 YES라는 것을 다항식 시간 이내에 확인할 수 있는 문제가 바로 NP 문제에 해당된다. 예를 들어, $\{-5,6,1,2,-10,-7,13\}$과 같이 정수 n개로 이루어진 집합이 주어졌다고 할 때, '이 집합의 부분집합들 중에서 원소의 합이 0이 되는 집합이 존재하는가?'라는 문제는 아직까지 다항식 시간 알고리즘이 알려져 있지 않다. 곰곰히 생각해보아도, 그냥 모든 부분집합을 다 테스트해보지 않는 이상 답이 YES인지 NO인지 답하기가 어렵다는 것을 알 수 있다. 그렇지만 누군가가 우리에게 $\{6,1,-7\}$이라는 힌트를 제공하였다면, 우리는 먼저 이 집합이 원래 집합의 부분집합이라는 사실을 확인하고, 이 집합의 원소의 합이 0이라는 사실을 확인함으로서, 원래 문제의 답이 YES라는 것을 어렵지 않게 확인할 수 있다. 따라서 '크기가 n인 어떤 정수 집합이 주어졌을 때, 이 집합의 부분집합들 중에서 원소의 합이 0이 되는 집합이 존재하는가?'라는 문제는 적어도 NP 문제인 것은 확실하지만, 이것이 P 문제인지 아닌지는 아직 모르는 상황이라고 할 수 있다.


만약 어떤 P 문제가 주어졌고, 그 문제의 답이 YES라면, 우리는 그 문제의 답에 관한 힌트를 받더라도 그냥 무시하고, 곧바로 그 문제의 답이 YES라는 것을 쉽게 확인할 수 있을 것이므로, 모든 P 문제는 저절로 NP 문제도 된다. 즉, P⊂NP임을 알 수 있다. 하지만 그 역방향인 NP⊂P에 대해서는 참인지 거짓인지 아직 알려져 있지 않다. 만약 모든 NP 문제가 P 문제인 경우, 즉 모든 NP 문제가 다항 시간에 풀 수 있는 알고리즘이 존재함을 증명할 경우 P=NP라는 결론이 된다. 그래서 P=NP인지, 아니면 P≠NP인지를 묻는 것이 바로 P-NP 문제이다. 7대 난제 중에서는 문제의 내용을 이해하기 가장 쉽다.


사실 많은 컴퓨터공학자들은 절대로 P=NP일리가 없다고 믿고 있다. 왜냐하면, P=NP가 의미하는 바는, 만약 어떤 문제가 주어졌을 때, 그 문제의 답안을 쉽게 검산할 수 있다면, 그 문제 자체도 쉽게 풀 수 있다는, 너무나도 강력한 주장이기 때문이다. 이는 우리가 지금까지 열심히 수학을 공부하면서 몸에 체득해온 직관과는 배치되는 일이다. 일부 방정식의 경우 해를 직접 구하는 것은 어렵지만, 남이 미리 풀어서 구한 답을 방정식에 대입해서 그게 맞는지 확인하는 일은 훨씬 쉬운 경우가 많다. 따라서 P≠NP라는 것을 쉽게 입증할 수 있을 것 같지만, 불행히도 아직까지는 아무도 올바른 증명을 찾아내지 못하였고, 이것을 증명하는 것이 왜 어려운 일인지를 암시하는 간접적인 결과만이 조금 밝혀져 있을 뿐이다.

P는 NP에 속하지만, NP가 P에 속하는지 여부는 밝혀지지 않았다.

P-NP 문제는 복잡도 종류 P와 NP가 같은지에 대한 컴퓨터 과학의 미해결 문제로 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻고 있다. 1971년 스티븐 쿡이 그의 논문 〈The Complexity of Theorem Proving Procedures〉(정리 증명 절차의 복잡성)에서 처음으로 제안하였고 클레이 수학연구소에서 발표한 7개의 '밀레니엄 문제' 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있다. 이것은 본래 1956년 쿠르트 괴델이 존 폰 노이만에게 썼던 편지에서 처음으로 언급되었다. 괴델은 어떤 NP 완전 문제가 2차 혹은 선형 시간 안에 풀릴 수 있는지 아닌지를 물었다.

P는 결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이고, NP는 비결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이다. 여기에서 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분집합이 된다. 하지만 여기에서 P와 NP가 같은 집합인지, 아니면 P가 NP의 진부분집합인지는 아직 밝혀지지 않았다. 현재 2000년에 클레이 수학연구소가 100만 달러를 걸었다.

​위에 사용된 일상적인 단어인 "빠르게"​는 다항 시간안에 실행되는 작업을 위한 알고리즘의 존재를 의미한다. 다항시간 안에 답을 제공하는 알고리즘이 있는 문제들의 일반 류 general class(종합적인 모임)를 P류 혹은 P라고 한다. 어떤 문제들은 빠르게 답을 찾을 수 있는 방법이 알려져 있지 않지만 답이 무엇인지를 나타내는 정보가 제공된다면 답을 빠르게 확인하는 것이 가능하다. 다항 시간 안에 확인할 수 있는 문제류를 NP라고 한다.

​쉽게 풀이법이 확인될 수 있는 문제이지만 답을 계산하기는 어려울 수 있는 문제의 한 예인 부분집합 합 문제를 예를 들어보면 다음과 같다. 어떤 정수의 집합이 주어졌을 때 공집합이 아닌 부분집합중 적어도 하나 이상의 부분집합의 합계가 0일 수 있는지, 예를 들면 {−2, −3, 15, 14, 7, −10}의 부분집합 중 어떤 것은 합계가 0일지 생각해보면 답은 그렇다 이다. 왜냐하면 부분집합 {−2, −3, −10, 15}의 합계가 0 이기 때문인데, 이것은 3회의 덧셈으로 빠르게 풀린다. 그런데도 그런 부분집합을 다항시간 안에 찾아내는 알고리즘은 알려져 있지 않다.그런데 만약 P = NP​라면 시간 복잡도(2ⁿ-n-1 회)안에 풀리는 이 문제를 다항시간에 풀 수 있는 알고리즘이 존재할 것이다. 이런 이유로 이 문제는 빠르게 확인가능한 NP안에 있지만 반드시 빠르게 풀 수 있는 P​안에 있지는 않다.

​P = NP​문제의 답은, 부분집합의 합계 문제와 같이 지수시간 안에 답을 계산할 수 있는 문제들이 다항시간안에도 답을 계산할 수 있는지를 결정할 것이다. 만약 P ≠ NP​인 것으로 드러난다면, NP안에는 풀이법을 확인하는 것보다 답을 계산하는 게 더 어려운 문제들이 있다는 것을 의미할 것이다. : 그것들은 다항시간 안에 풀 수 없지만 다항시간 안에 풀이법을 찾을 수는 있다.

컴퓨터 과학에서 이 문제의 중요성을 차치하더라도, 이 문제의 증명은 수학, 암호, 알고리즘 연구, 인공지능, 게임이론, 멀티미디어 프로세싱, 철학, 경제학등 다양한 분야에 엄청난 영향을 끼칠 것이다.