NP, NP-COMPLETE, NP-HARD

공부 2010.05.05 05:11
P,NP 문제는 워낙에 유명한 난제라서 그런지 검색은 많이 되는데,
그렇게 나온 검색 결과는 보통
너무 엄격하게 써놔서 어려워서 뭔말인지 모르겠다거나
아예 틀린경우도 종종 보인다.

NP문제를 쉽게 설명하자면 yes/no로 답할 수 있는 문제중에,
yes라는 답에 해당하는 구체적인 예를 줬을때, 그것이 yes가 맞다는것을 빠른(polynomial)시간안에 알 수 있으면 NP문제이다.

알기쉽게 예를들면,

"평면위에 점이 n개가 있는데 그 점중에 하나에서 시작해서 모든 점을 한번씩만 방문하고 다시 제자리로 돌아오는 길중에서, 그 경로의 길이가 k이하인게  있을까?"

라는 문제는 NP문제이다.

yes/no로 대답할 수 있고,
(검은점 n=10개, 발로그려서 빨간선의 길이가 제멋대로긴 하지만 숫자만큼의 길이를 가진다고 하면, 한번씩 거치는 위의 빨간 길의 총 길이는 29. 문제에서 k가 30이었다면 답은 yes)

위의 그림에서처럼 yes에 해당하는 답을 줬을때 쉽게 답이 맞음을 알 수 있기 때문이다.


그러면 P문제는 뭘까?
NP문제 중에서 답조차도 빠른시간안에 찾는 방법이 알려져 있으면 그건 P문제다.

위에서 예를든 문제 같은 경우에는 NP문제이지만 P문제는 아니다.

저 경우에는 경로의 길이인 k가 30이라서 대충해도 쉽게 찾을 수 있었지만 k가 20정도라면 그 답을 쉽게 찾을 수 없기 때문이다. 실제로 위의 문제에 대해서 알려진 가장 빠른 알고리즘도 exponential한 시간복잡도를 요구한다.
물론 이경우에도 누가 k=20일때의 답을 알려준다면 우리는 손쉽게 그 답이 yes임을 알 수 있다. P문제도 NP문제에 속하기 때문이다.


NP-COMPLETE문제는 모든 NP문제들이 빠른시간안에 변환(reduction)될 수 있는 문제를 말한다. 모든 NP문제들이 빠른시간안에 NP-COMPLETE문제로 변환될 수 있기 때문에, NP-COMPLETE문제만 풀면 모든 NP문제를 빠르게 풀 수 있다.


NP-HARD문제는 정말 어려운 문제로, NP문제가 아니다.
유명한 TSP같은 문제가 NP-HARD인 문제인데,
TSP가 뭐냐하면 아까 위에서 예를 들었던문제의 일반적인 버전의 문제이다.
총 길이가 k이하인 길이 있느냐가 아니라, 가장 최적인 길이 뭐냐라는 문제같은거다.

이 문제의 경우에는 최단경로에 해당하는 답을 줘도 우리가 그 길이 진짜 최단경로인지 빠른시간안에 알 수 있는 알려진 방법이 없다.



그럼 이제 그 유명한 수학적 난제인 P=NP? 문제에 대한건데,
P문제가 NP문제와 같으냐 다르냐를 증명하는 문제이다.
NP가 P와 같다면 NP문제에 해당하는 모든 문제를 빠른시간안에 푸는것이 가능하다는 거니까.

그런 엄청난 파급력 때문인지 이 문제는 유독 이상한 사람들이 많이 꼬이는것 같다.

예를들어 입시철 즈음 되면 모 지방대학에서 P=NP를 증명했다고 '주장'하며 언론플레이를 하는 교수님이라거나...

사실 P는 NP와 다른것임이 거의 확실해 보인다.
다만 증명이 안되있을뿐이지.

그리고 사실 P,NP문제에 대해서 배우는 이유는 위에처럼 둘이 같거나 다르다는것을 증명하는 극단적인 응용 보다도
어떤 문제를 풀 수 없음을 미리 알수 있다는데 있는것 같다.
내가(혹은 누구라도) 이 문제를 빠르게 풀 수 없음을 미리 파악하고, 우회해서 갈 수 있다는건 정말 엄청난 이득이지.
신고

'공부' 카테고리의 다른 글

가변인수(va_arg)를 이용한 계산오차 줄이기  (3) 2010.08.02
계산기하 - 원 포함 알고리즘 코딩  (0) 2010.06.03
NP, NP-COMPLETE, NP-HARD  (7) 2010.05.05
for문에서 j  (3) 2010.04.26
SQL injection on python+SQLite3  (0) 2010.04.02
Google Summer of Code2010 & CGAL  (0) 2010.03.30
Posted by youknow04


티스토리 툴바