Algorithm
2013.04.23 12:52
Polynomial time 이란? ㅋㅋ
Views 22799 Comment 0
어떤 주어진 문제를 푸는 알고리즘이 걸리는 시간이 어떤 다항식으로 나타날때 그 문제를 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
-
RSVP 란?
-
RPA란? 어디에 어떻게 쓰이고 누가 만드나?
-
Polynomial time 이란? ㅋㅋ
-
php.ini 설정 안됐을때.. ㅋㅋ
-
OSI (Open Systems Interconnection) 개방형 시스템간 상호 접속
-
OPT와 CAS에 대한 자료.. (교수님 메일로 보내드린 자료..)
-
OpenSSL로 ROOT CA 생성 및 SSL 인증서 발급하기
-
OpenGL 강좌 사이트 모음
-
OGNL(Object Graph Navigation Language)
-
OCB5 Injection 앗싸뵹! ㅋㅋ
-
NAT와 DHCP에 대한 간단한 설명
-
Mac에서 Node.js 설치하기