「 Я Чайка 」

일단 어떤 문제가 있다고 가정하자.

[가장 간단한 이해]

이 문제의 해답을 그럭저럭 빠르게 구할 수 있다면, P다.

이 문제의 해답을 구하는데 시간이 많이 걸려야만 한다면, NP다.

[조금 발전]

어떤 문제의 해답을 구하는 데 걸리는 시간은, 그 문제의 입력의 크기에 의존한다.

간단한 예를 들어서, 숫자가 왕창 있고, 그것을 작은 순으로 정렬한다고 하면,

이 숫자가 천개 있을때랑, 1억개 있을때랑 걸리는 시간은 당연히 다르다.

이런 입력 사이즈를 n이라고 할 때, 어떤 문제의 해답을 n에 대한 다항식 시간(polynomial time) 안에

내놓을 수 있다면, 이 문제를 P 문제라고 한다. 

하지만, n의 크기에 따라 지수적으로 숫자가 증가하거나, 계승(factorial)이라거나 해서 시간이 급격히

증가한다면, 이 문제를 NP 문제라고 한다.

[좀 더 명확하게]

어떤 문제가 있다고 했을 때, 실제로 관심을 가져야 하는 것은 2가지 있다.

(1) 문제와 입력이 주어졌을때, 최적의 해를 찾는 것.

(2) 어떠한 해가 주어졌을때, 이 해가 올바른 최적해인지를 검사하는 것.

이 중에서 (1)의 경우는, 지금까지 하던 이야기니까 일단 놔두고, (2)를 생각해보기로 한다.

하나의 해답이 주어졌다고 해도, 이 것이 문제의 조건을 만족하는지 아닌지를 검사하기 위해서

어느정도의 계산이 필요한 경우가 있다.

예를 들어 그래프상의 모든 점을 정확히 한번씩만 방문하면서, 같은 변을 두번이상 지나지 않는 경로가

있는 지를 찾는 문제(Traveling Salesman Problem; TSP)가 있다고 했을때,

이 문제를 푸는 것(그러한 경로를 찾아내는 것)은 어렵지만, 만약에 답이 하나 주어졌다고 했을 때,

이 해답이 문제의 조건을 만족했는지 아닌지를 검사하는 것은 쉽다.

(모든 정점을 방문했는지 검사하고, 같은 변을 두번이상 지나지 않았는지를 검사하면 된다)

물론, 이러한 검증은 문제를 푸는 것보다는 기본적으로 간단하다.

이를 배경으로 NP문제를 정의하면 다음과 같이 된다.

"어떠한 문제 A가 있을시, 문제의 푸는 것은 다항식 시간에 불가능하나,

문제를 검증하는 것은 다항식 시간에 가능한 문제를 NP문제라고 한다"

* 참고

1. 문제에 대한 해답을 검증하는 것조차 다항식 시간에 할 수 없는 문제들이 물론 존재한다. 이는 NP보다도 어려운 문제이다.

예를 들어, 체스 게임에서 반드시 승리하는 전술이 있어서 이를 해법으로 제시해도, 항상 이길 수 없을지(즉, 어떠한 상대에 대해서도)를

검증하는 것은 간단하지 않다.

2. 문제의 해답을 검증하는 것은 "YES"만 가능하다. 

TSP문제를 예로 들면, 어떠한 답(경로)가 주어지고, 이 해답이 문제의 조건을 만족하는 것을 검증 가능하다면, "이 문제에는 해법이 존재한다"를

증명할 수 있지만, 반대로 틀린 답이 주어지고, "이 문제에는 해법이 존재하지 않는다"라는 것을 증명할 수는 없다. 뭐 당연한 이야기다.

[P와 NP의 관계]

일단 우선적으로 명심해야 할 것은, P와 NP는 완전히 다른 것이 아니다.

NP는, 다항식 시간에는 못풀지만, 다항식 시간에 검증은 가능한 문제들.

P는 푸는 것 조차도 다항식 시간에 할 수 있는 문제이다.

즉, 아래 그림과 같은 관계를 갖는다.

위 그림에서 보이는 것처럼 P ⊂ NP 의 관계가 성립한다.

단지, 이 관계에서 중요한 것은 과연 P = NP 인가 아닌가 하는 것이다.

NP는 다항식 시간에 못푸는 문제라고 했지만, 사실은 풀 수 있는데 아직 그런 해법을 찾아내지 못했을 가능성이

충분히 존재한다. 즉, NP문제가 가지는 정확한 위치는 "다항식 시간에 풀 수 있는지 없는지 모르는 문제"이다.

이 논란은 과거부터 수학, 전산학에서 계속 다루어진 문제로, P-NP문제라고 한다.

전 세계 연구자들 사이에서는 P≠NP라는 의견이 지배적이지만, 아직 아무도 확실하게 이를 증명해내지는 못하고 있다.

(사실 이 의견이 지배적인 이유도 간단하다. 이렇게 오랫동안 궁리했는데도 해법을 찾지 못했기 때문이다)