Algorithm
2013.04.23 12:52
Polynomial time 이란? ㅋㅋ
Views 22801 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
No. | Category | Subject | Author | Date | Views |
---|---|---|---|---|---|
909 | Database | [mysql] 루트 암호 초기화 | hooni | 2013.04.23 | 11127 |
908 | Database | [mysql] MySQL 한글 깨짐 현상 해결하기(UTF8) | hooni | 2017.12.01 | 5652 |
907 | Database | [mysql] MySql 에서 정렬 후 그룹 하는 방법 | hooni | 2015.05.07 | 3156 |
906 | Database | [mysql] MySQL 백업 및 복구 | hooni | 2019.11.22 | 938 |
905 | Database | [mysql] MySQL 데이터베이스 추가 및 사용자 추가 | hooni | 2019.11.22 | 796 |
904 | System/OS | [mysql] mysql user 생성시 ERROR 1364 | hooni | 2013.04.25 | 28621 |
903 | System/OS | [mysql] MySQL server has gone away 에러 대응 | hooni | 2013.05.29 | 19394 |
902 | Database | [mysql] MySql DB/테이블 사이즈 확인을 위한 쿼리 | hooni | 2019.11.22 | 794 |
901 | Database |
[mysql] MacOS에 MySQL 설치, 설정, 암호 재설정
![]() |
hooni | 2017.12.15 | 1632 |
900 | Database | [mysql] error while loading shared libraries: libmysqlclient.so.10: | hooni | 2003.04.23 | 12738 |
899 | Database | [mysql] ERROR 1820 (HY000): You must reset your password using ALTER USER statement before executing this statement. | hooni | 2017.12.15 | 1400 |
898 | Database | [mysql] DB->Text, Text->DB 변환 | hooni | 2003.04.23 | 12220 |