P vs NP 문제 이야기

결론적으로 말하자면 인간이 추측하는 근사치를 구한다는 말이다

학창시절에 이 알고리즘이 풀리는거냐 안풀리는거냐에 대한 알고리즘을 푼 적이 있는데 이것도 P vs NP 문제에 대한 하나의 부류라고도 할 수 있다

그때 알고리즘의 답이 있는가에 대해 풀면서 생각하길 인간에 대해서도 이것이 풀린다면 대단한 알고리즘이 되겠다  라는 생각을 했던적이 있었다

아래는 P vs NP에 대해 약간 자극적으로 설명을 한 글이 있어서 퍼왔다

p.s 너무 자극적이여서 이해가 안될 수가 없네 ㅋㅋ

---

http://bazzi1003.blog.me/60102597195

원본 링크

http://ruliweb.nate.com/mypi/mypi.htm?id=jmbhk&num=1459

※로그인 필요

[출처] P vs NP 문제 이야기|작성자 데스모

 

"P대NP 문제": 이거 풀면 기본 13억 받는데, 중요한 건 이거 풀면 13억이 문제가 아니라 돈이 넝쿨 째로 굴러들어 올 수도 있음.


우선 이 문제는 컴공 쪽에서 나온 문제임. 
그러니까.... 오늘은 밤이 늦었으니까 간단히 개요만 설명하고 넘어가도록 하겠음. 


우선 컴퓨터의 알고리듬이 어떻다느니, 연산을 통해서 풀 수 있는 문제가 P(Polynomial-time)네, NP(Non-deterministic P)네 하는 어려운 소리는 다음 편에 하도록 하고, 가장 간단하고 쉽게 이해할 수 있는 예를 들어 보겠음. 이제 너님들은 유명한 패션 디자이너야. 그리고 여기는 너님들의 패션쇼를 보는 장소이고. 올 트렌드가 되는 옷들을 입고 모델들이 무대를 돌고 있어. 그런데 너님들이 쇼만 보고 있자니 지금 심심한거야, 그래서 모델 언니들 슴가를 눈으로 어림짐작 하는 놀이를 하기로 했다고 쳐. 

자, 너님들은 여태까지의 경험과 지식을 바탕으로 슴가 크기를 측정을 했어. A모델은 88, B모델은 84, C모델은 77... 자, 그럼 물어보자. 너님들의 측정은 정확할까? 답부터 말하자면 그럴 수도 있고 아닐 수도 있겠지, 뭐.

여하간 그렇게 너님들이 슴가 크기 측정 놀이를 마치고 난 뒤 얼마 지나서, 이제는 너님들의 패션쇼를 하는 때가 되었어. 그래서 모델 언니들 몸에 맞게 옷을 만드려고 모델 언니들 사이즈를 재게 된 거지. 어머나, 그런데 전번 쇼에서 너님들이 치수 맞추기 놀이의 재료로 채택됐던 모델 언니들이 끼어 있네?

그럼 이제 너님들의 추측과 실제 슴가 크기에 대해서 비교해 보는 게 가능하겠지? 그럼 우선 슴가 크기를 재는 방법에 대해서 생각해 보도록 하자. 아이큐가 아~주 나쁜 디자이너라면 줄자로 치수를 이렇게 잴거야. 


1cm 재보고 이거보다 크네? 그럼 다음 2cm 재보자. 2cm재보고 이거보다 크네? 그럼 다음 3cm 재보자.......


이런식으로 계속해서 한 단위씩 높여가다가 결국 모델 언니의 실제 슴가 크기가 측정이 될 때까지 반복하겠지. 이렇게 측정하는 저능아는 없을 거라고? 맞아, 없을 거야. 그런데 이게 컴퓨터의 계산 방식인거야. 어느정도의 지능을 가진 인간이라면 '아, 저 모델 언니 슴가는 84 쯤 되겠군.'하면서 줄자를 84쯤 부터 시작해서 작으면 '어라, 작은가?' 하면서 치수를 늘리겠지.

그런데 컴퓨터는 이게 안되는 거야. 여기서 바로 인간과 컴퓨터 간의 사고에 결정적인 차이점이 있는거지. 인간의 사고는 '추측'이 가능해. 그래서 어떤 문제를 접했을 때 그 문제에 대해서 '쉬운지/어려운지', '어떤 알고리즘을 사용해야 되는지' 같은 것들을 추측할 수 있는 거지. 그리고 그렇게 추측한 결과를 통해 '연산시간을 비약적으로 단축'할 수도 있어.

고작 슴가 크기로 이야기 하니까 좀 시시해 보이기도 할거야. 그럼 조금 긴 시간을 요하는 연산 문제를 생각해 보자. 


자연수 N에 대하여 N이 10^30(10의 30승)자리의 수라고 할 때, 자연수 N에 대하여 10^10자리의 약수를 하나만 구하라.


무지하게 복잡하지? 이 문제를 풀려면 컴퓨터의 연산속도로는 무지하게 오랜 시간이 걸릴 거야. 그런데 NP가 되면 어떨까? 문제 해결 속도가 비교할 수도 없이 줄어드는 거야. 뭐 쿼드코어 이런 건 물론이고, 이게 가능하게 된다면 지금 가정용 컴퓨터로도 거대 연구소에나 하나씩 있는 슈퍼컴퓨터 정도는 우습게 발라버릴 수 있다는 거지.(물론 이건 좀 오바를 보탠 거지만) 때문에 P=NP냐, P≠NP냐는 겁나게 중요한 문제가 된거야. 

만약 P=NP라면 당장 현재 존재하는 모든 암호체계는 무용지물이 돼. 이걸 푼 인간은 말 그대로 그 무엇으로도 막을 수 없는 '창'을 가지게 된 거지. 만약 너님이 이걸 풀게 된다면, 그냥 13억 안 받고 보안회사 차리는 게 오히려 돈을 떼로 벌 수 있을 걸. 그리고 좀 더 오바해서 생각하면, 터미네이터도 꿈이 아니야. 이 P대NP문제는 인공지능과도 밀접한 연관이 있거든. 추측할 수 있는 연산은 '학습'이나 '반성'이 가능하다는 뜻이기도 하거든. 그럼 정말 기계가 인간을 지배할 지도 모르는 일이지.

여하간 그래서 이 문제는 되게 중요한 거야. 진짜 이거 하나만 풀면 못해도 13억(P≠NP일 경우), 잘하면 세계정복도 가능하니까. 뭐, 최대한 수학적인 이야기를 안하고 쉽게 풀어보려다 보니까 비유가 구린 부분이 좀 있긴 하지만, 그 부분에 대해서는 다음 편에 좀 어렵게 들어가면서 보완할 테니까 이해해 주길 바라.

[출처] P vs NP 문제 이야기|작성자 데스모