어떤 주어진 문제를 푸는 알고리즘이 걸리는 시간이 어떤 다항식으로 나타날때 그 문제를 P 문제라고 부릅니다.

예를 들어서 어떤 임의의 수열을 정렬하는 방법을 생각해 보죠.

5, 3, 6, 1, 4, 2

Bubble Sort를 아시는지?

앞에서부터 차례로 두개씩 비교해서 큰수를 뒤에 작은수를 앞에 적는 방법입니다.

[Step 1]

[5, 3], 6, 1, 4, 2

3, [5, 6], 1, 4, 2

3, 5, [6, 1], 4, 2

3, 5, 1, [6, 4], 2

3, 5, 1, 4, [6, 2]

3, 5, 1, 4, 2, 6

(걸린시간 5)

[Step 2]

[3, 5], 1, 4, 2, 6

3, [5, 1], 4, 2, 6

3, 1, [5, 4], 2, 6

3, 1, 4, [5, 2], 6

3, 1, 4, 2, 5, 6

(걸린시간 4)

...

같은 식으로 하면 전체 걸리는 시간은 5+4+3+2+1이 걸리게 되구요.

일반적으로 n개의 수열을 정렬하는데에는 n(n-1)/2 의 시간이 걸리죠.

이 문제를 푸는데에는 n의 이차식 만큼의 시간이 걸렸으므로 수열의 정렬 문제는 P 문제입니다.

일반적으로 알고리즘이 걸리는 시간이 일차식, 이차식, 삼차식과 같이 다항식으로 나오는 문제는 그다지 오래 걸리는 알고리즘이 아니라고 생각됩니다.

따라서 P문제는 풀기에 쉬운 문제라고 할 수 있습니다.

그러면 NP 문제는 무엇일까요?

어떤 주어진 답이 그 문제의 답이 맞는지를 확인하는 시간이 다항식만큼만 걸린다는 의미입니다.

이것도 예를 들어서 생각해보죠.

기숙사 방배정 문제를 생각해보겠습니다.

100명의 학생이 각자 자기가 원하는 방의 상태에 대해 체크를 해서 제출을 합니다.

= 난 룸메이트가 담배를 안피면 좋겠다,

= 난 남쪽방이 좋더라.

= 난 무조건 일층에서 살면 좋겠다

그리고는 그 조건을 모두 만족하게 방을 배정하고 싶습니다.

아마도 문제가 참 어렵겠죠.

흠..

학생1은 이 조건에 다 맞으니 이 방에 넣고,

학생2는 저방에, 3은 요 방에.. 넣다보니,

조건이 아무래도 안맞는 학생이 있군..

그러면 이번에는 학생3을 이방에 넣어보면 어떨까.

그래서 또 처음부터 새로..

이렇게 가능한 방법의 수를 마구마구 생각해내야겠죠.

어쩌면 모든 가능한 조합을 생각해야 할지도 모릅니다.

그 경우에 알고리즘이 걸리는 시간은 100! (학생이 n명이면 n!)이 되겠죠.

물론 저것은 다항식이 아니고 따라서 굉장한 시간이 걸릴겁니다.

어쩌면 잘 알고리즘을 짜면 다항식 시간에 끝낼수 있을지도 모르지만..

딱 그 알고리즘을 떠올리기 전에는 확신할 수는 없습니다.

그렇지만 만약에 어떤 방배정표를 하나 만들어서 딱 주었을때 이 배정표가 모든 학생이 원하는 배정인지 아닌지를 확인하는 것은 딱 100번(학생의 수만큼)만 비교해 보면 알 수 있습니다.

n명이 있을때 n번(일차식)만큼만 확인하면 답이 맞는지를 알 수 있으므로 이 문제는 NP 문제입니다.

따라서 NP문제는 풀기에는 쉽지 않을 수 있지만 답이 맞는지 확인하기는 쉬운 문제입니다.

그럼 마지막으로 P 대 NP문제는 무엇일까요?

위의 문제가 풀기는 쉽지 않다고 했는데..

어떤 머리좋은 사람이 적당한 알고리즘을 만들어내면 위의 문제를 다항식만큼의 시간에 풀 수 있지는 않을까요?

조금 더 일반적으로 말해서 NP문제이면서 P문제가 아닌 것이 존재하나요?

그것을 증명하라는 문제입니다.

(즉, P = NP 입니까, 아닙니까?)

---------------------------------------------------------------------------------

우선 컴퓨터 프로그래밍에는 알고리즘이 있습니다

알고리즘은 쉽게 말해 문제를 푸는 방법 또는 논리적인 절차라 할수 있겠습니다

어떤 문제를 푸는데 다항식적인 시간으로 풀 수 있다면 그것은 P문제(polynomial time problem; 다항시간문제)에 속합니다.

만약 그렇지 않고 지수함수 등으로 다항식적인 시간내에 풀 수 있다면 그것은

NP문제(nondeterministic polynomial time problem; 미정다항시간문제)에 속합니다

이것이 무슨 뜻이나면,

예를 들어 다항함수 x^n 와 지수함수 a^x를 비교했을 때 지수함수가 훨씬 빨리 증가하는 것을 알 수 있듯이 P문제에 속하는 것들은 주어진 데이터 x에 따라 x에 관한 다항식으로 표현되는 시간내에 수행가능하지만 NP문제들은 그렇지 않다는 의미입니다.

P문제로는 두 행렬의 곱셉, 두 다항식의 곱셈 등이 있고

(사실 너무 많아 예를 들기도 어렵습니다)

NP문제로는 대표적으로 순회세일즈맨 문제, 한붓그리기 문제, 시간표 짜기, 한 자연수가 소수인지 판정하는 문제 등이 있습니다.

NP문제는 "다항식적인 시간으로 풀 수 있는 알고리즘이 존재하지만 그 알고리즘이 단지 알려지지 않았을 뿐"일 수도 있으므로 미정다항시간문제라 하는 것입니다.

만약 그렇다면 P=NP인 것이고 그렇지 않으면 P!=NP인 것인데 그것을 증명하는 것이 100만불이 걸린 문제였는데 그것이 풀렸다는 군요.

아래 사이트에 들어가시면 P문제, NP문제에 대한 훨씬 더 자세한 설명을 얻을 수 있습니다.

여기 들어가서 아래쪽에 보시면 "두가지 미래"란에 이것이 어떤 의의를 가지는가를 알 수 있습니다.

http://www.math.snu.ac.kr/~hongjong/잡필/PversusNP/PversusNP.html

http://kin.naver.com/db/detail.php?d1id=11&dir_id=110203&eid=WksITumhvEp4i37zw23N2LTGBzcxnO/c