'NP-Complete'에 해당되는 글 1건

  1. 2010.05.05 NP, NP-COMPLETE, NP-HARD (7)

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

댓글을 달아 주세요

  1. 희민 2010.05.12 16:16  댓글주소  수정/삭제  댓글쓰기

    오~ np, np-hard 검색하니까 검색엔진이 나를 이리로 데려오는구나 ㅋㅋ
    설명이 깔끔하군.
    윤호 안녕~

  2. 우와 2011.12.01 21:35  댓글주소  수정/삭제  댓글쓰기

    많이 배우고갑니다 ... 어우 수학은 역시 어렵네요 ㅠㅠ

  3. 수학이라 하긴 뭐한데 2013.08.30 13:31  댓글주소  수정/삭제  댓글쓰기

    그나저나 NP hard는 NP일지 아닐지 모릅니다. 심지어 P일수도 있죠.
    그리고 P가 NP랑 다르다고 이야기하는 수많은 증거들이 생각보다 단순하고(그냥 수많은 문제들이 NP complete임만 밝혀지고 하나도 안풀렸다는 것. 잘 생각해보세요. 이게 왜 증거가 되는지.) 아직 미숙한 단계의 이론들이 논하기에는 너무 시기상조란 말도 많습니다. 페르마의 마지막 정리의 예를 생각해보라는 종류의 이야기죠.

  4. 지나가다가 2013.10.24 17:46  댓글주소  수정/삭제  댓글쓰기

    안녕하세요. 지나가다 봤는데, 몇가지 코멘트 남깁니다.

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

    무슨 의도인지는 알겠지만 엄밀히 말하면 틀린 문장이네요
    NP문제이지만 P문제는 아닐 수도 있다. 라고 표현해야 맞을 것 같네요.

    "NP-HARD문제는 정말 어려운 문제로, NP문제가 아니다."

    NP-hard 문제는 적어도 하나의 NP-complete problem으로 reduction 되는 문제를 지칭합니다.
    보통 어려운 문제들을 지칭할때 이런이런 문제는 NP-complete이다 라는 말을 많이 하는데, 가끔 yes/no question이 아니기 때문에 NP-complete problem 이라는 말을 쓰기 애매한 경우 NP-complete 대신 NP-hard 다 라고 쓰기 때문에 NP-hard가 NP 보다 어려운 문제라는 식의 뉘앙스는 오해의 소지가 있네요.

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

    과반수 이상의 학자들이 P가 NP와 다를 것이라고 추정하고 있지만 (기억이 맞다면 60~70%), P=NP라고 믿는 학자들도 많이 있고, 또 현재 우리의 ZFC 공리체계하에서 증명이 불가능한 명제라고 생각하는 분들도 상당수 있습니다.

  5. 지나가다가 2013.10.24 18:15  댓글주소  수정/삭제  댓글쓰기

    http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

    참고하시길~

  6. 학부생 2014.06.25 10:32  댓글주소  수정/삭제  댓글쓰기

    본문의 내용이 교과서들과 달라서 헷갈려하다가, 댓글을 보고 나서야 정리가 되었네요.

    필자께서 깔끔히 정리해 주시긴 했는데, 윗 분들이 지적한 사항은 수정해 주는 것이 좋을 것 같습니다.
    공부하는 학생에게는 잘못된 지식이 전달될 수 있습니다.