NP, P 문제

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

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