[정보] 해파리와 쉽게 이해하는 수학난제 - P-NP문제

[해파리6]

P.S

제가 작성한 내용은 정확도가 현저히 떨어질 수도 있으니 알아서 판단해서 취사하여 정보를 습득하시기 바랍니다. 

1.P-NP문제가 뭔가여????

->'P'는 결정론적 튜링기계를 사용해 다항시간 내에 답을 구할 수 있는 문제의 집합이고

   'NP'는 비결정론적 튜링 기계를 사용해 다항시간 내에 답을 구할 수 있는 문제의 집합이다

이  P와 NP가 같은가??를 묻는게 P-NP 문제인 것이다.

2.아니 이게 뭔 개소리인가여??

->그러니까 약간의 이해를 돕기위해 설명이전에 대략적인 그림을 그리겠다.

일단,NP의 내부에는 P가 속한다는 것은 이미 밝혀졌다.즉 P는 NP의 부분집합이라는 뜻이다.

시벌 그림으로 설명해야지.

대충 이런 말이다.이건 우리가 이미 알고있는 사실이다.

그런데,

이것이 , 즉 NP가 P의 부분집합인지는 아직 증명되지 않았다. 만약 위 그림인 NP가 P의 부분집합임이 참이 되면,P는 NP의 부분집합이고, NP는 P의 부분집합이라는 뜻이므로,결국 P=NP라는 뜻이 된다.

3.그냥 그림은 대충 이해는 했는데 P가 뭐고 NP가 뭘 말하는건데?

->아주 단순하게 말하면 'P'는 쉬운 문제이고 'NP'는 어려운문제?딱 맞는 표현은 아니지만 대충 이렇게 표현할 수 있다.

P는 Polynomial time problem으로 다항시간문제, NP는 Nondeterministic poly nomial time problem 미정다항시간문제라는 뜻인데,P문제같은 경우는 알고리즘으로 나타낼 수도 있고, 걸리는 시간도 알 수 있다.

아주 쉬운 예를 들겠다.

숫자 7,4,2,1이 있다.이를 작은 수 부터  차례대로 표현하게 하는 알고리즘을 만들고 싶은데 그러려면 어떻게 해야할까?

이것의 알고리즘을 짜는 방법은 대충 '가로()안에 있는 수 중 작은 것을 왼쪽으로 보낸다'라는 알고리즘을 명령하면,

[ (7,4) ,2,1]

    ㅣ 

[,4,(7,2),1]

    ㅣ 

[4,2,(7,1)]

    ㅣ    

<한바퀴> ->[4,2,1,7]

     ㅣ

[(2,4),1,7]   

    ㅣ  

[2,(4,1),7]

    ㅣ

 <2바퀴> ->[2.1.4.7]

    ㅣ

[(2,1),4,7] 

    ㅣ

 <3바퀴> -> [1,2,4,7] 끝.

결국엔 1,2,4,7을 얻을 것이다.

1바퀴 지날 때 마다 ()를 수행하는 갯수가 1개씩 줄어들어 알고리즘 시행갯수가 3+2+1=6번 만에 결과를 얻을 수 있음을 알 수 있고,시행갯수를 수학식으로 표현하면,

다음과 같이 됨을 알 수 있다.n이란 []안에 있는 숫자의 갯수이다.우리는 [7,4,2,1]이기 때문에 []안에 있는 숫자의 갯수는 4개, 즉 4*3/2를 하면 6번과 같다.

만약 알고리즘을 1번 수행하는데 1초가 걸린다면,총 알고리즘을 수행하는 데 걸리는 시간은 결국 6초가 된다는 의미이다.

NP문제는 뭐냐면 이게 좀 골때리는데 예를 들어

[-2,-3,15,14,7,-10]이라는 집합이 있다.

이 집합에서 공집합을 제외하고 합이 0인 것은 어떤것일까? 라는 문제가 있다고 치자.

여기서 우리는 존나게 더하고 합하고 쇼를 하다보면 -2하고 -3하고 -10하고 15를 더하면 0이 된다는 사실을 쉽게 알 수있다.

하지만 위에 P문제 처럼 이를 컴퓨터로 순차적으로 실행하게하는 알고리즘은 아직 알려져 있지 않다.

또 다른 예로는 68,718,821,377라는 소수가 두 소수의 곱이라고 하면 두 소수는 각각 무엇인가?라는 물음은 매우 어렵다.

하지만 메르센이라는 새끼가 메르센 소수를 개발해 놓아서,그가 발명한 소수표를 물끄러미 쳐다볼수만 있다면 메르센 소수 6번째와 7번째인 131071과 524287의 곱이 68,718,821,377이라는 것은 계산기만 뚜들겨 보면 알 수 있다.

하지만 이를 알아내는 알고리즘은 아직 알려져 있지 않다.

즉 NP문제는 답을 찾을 수 있는 방법이나 찾는 알고리즘이 알려져 있지 않지만,답을 빠르게 확인하는 것은 가능한 것을 말하는 것이다.

 4.이 문제를 증명하려면 뭘 어케해야하나요??

->P=NP를 증명하려면 NP속한 모든 문제들의 알고리즘을 발견하면 된다.

즉 위에 메르센 소수 어쩌구 한 풀이를 할 수 있는 알고리즘을 발견해야하는데,문제는 그것 뿐만이 아니라 NP에 해당하는 모든문제.즉 저거 말고 최단거리 문제역시 NP문제이며,지뢰찾기 역시 NP문제인데,그것에 대한 알고리즘을 싹다 개발해야하니 하면할수록 시간낭비만 하는 느낌이 들 게 분명하다.

다행히 현재 분위기상 P≠NP임이 느낌으로는 확실시 되고있어서 그런 노가다식으로 증명을 하진 않아도 될 것이다.

<P=제한 시간안에 해결할 수도 있는 문제

 NP=제한 시간 안에 '검증'할 수 있는 문제(알고리즘은 모르지만 계산기나 수작업 따위로 답을 확임함으로써)

 NP-COMPLETE는 NP의 부분집합 중 하나로, NP에 속하는 문제중 가장 어렵다고 증명된 문제를 말한다.>

NP-COMPLETE는 NP문제중 가장 어려운 문제의 하나로, NP문제 중 엄청나게 긴 시간이라도 어쨋든 풀릴 수 있는 문제로 치환할 수 있는 NP문제를 일컫는데, 이러한 문제는 많긴 하지만 왜 NP COMPLETE문제인지는 증명이 되지 않고 있다.

이게 중요한 이유는 만에하나 NP-COMPLETE 문제 중 '단 하나라도' P에 속한다고 증명이 되면,즉 제한된 시간안에 풀 수 있는 문제라고 증명이 되면,결국 NP=P라는 것을 의미하게 되기 때문에 이 난제는 해결될 수 있다.

시간 좀 남아돌면 NP-COMPLETE문제를 찾아다가 P에 속하는 지 한번 알아보아라.상금이 자그마치 100만달러다.자고로 NP-COMPLETE문제라고 일컫는 문제는 SAT문제,외판원문제,그래프 색칠 문제,해밀턴 경로 문제등등이 있다.이 문제에 대한 설명은 검색찬스를 쓰면된다.

5.대충 뭔말인지 알아먹겠네요!근데 이 문제는 아직 안 풀렸나요?

->2003년에 전북대학교의 한 교수가 P≠NP가 아님을 증명하여 문제를 해결했다고는 하는데 학계에서 인정받지 못하였다고 한다.왜냐하면 어떤 문제가 시간안에 풀리지 않는 것을 증명한 건 사실이지만 '그 문제자체'가 NP에 속함이 증명할 도리가 없어서 P-NP 문제의 증명으로 볼 수 없다고 결론을 지었기 때문이다.

쉽게 말하면 음료들 중에서 우유와 커피가 있다고 치자.우유는 커피가 아니기 때문에 당연히 우유≠커피인것은 맞는 말이지만 그 조사한 우유자체가 진짜 우유인지 사실 우유가 아니라 색깔만 비슷한 밀키스인지 아리까리하므로 우유≠커피라는 증명이 성립될 수 없다는 것과 비슷한 이치이다.

6.내 생각엔 P≠NP인 것 아닌가 싶은데요 걍 느낌이.학계에서는 뭐라고 하고 있나요?

->2012년 조사결과 'P와 NP는 다른것일 거 같네요.'라고 답을 한 이론전산학자의 비율이 81%인 것을 보면 P-NP가 다른 것인 것 같긴한데,엄밀한 증명이 나와봐야 알 것이다.

7.근데 위에 보면 결정론적 튜링기계 비결정론적 튜링기계 어쩌구 하는데 그게 뭐에요?

->그게 바로 위의 알고리즘을 짜는 프로그램이다.결정론적 튜링기계는 P문제를 풀기위한 것으로 알고리즘을 보면 한줄씩 내려가지만,비결정론적 튜링기계는 알다시피 답을 찾는 알고리즘이 아예 없을 수도 있고,알고리즘이 여러갈래로 내려갈 수 도있다.

비결정론적 튜링기계의 알고리즘은 갈래가 여러갈래로 갈라지므로 개복잡해질 수 있다는 얘기이다.

튜링기계란 이론전산학에서 테이프에 써져있는 기호들을 일정한 규칙에 따라 바꾸는 기계를 뜻하는데 일종의 컴퓨터라고 생각하면 된다.실제로 컴퓨터를 설명하는데 유용한 기계이다.

                                    <결정론적 튜링기계를 가상으로 표현하면 다음과같이,제어장치,테이프,입출력 헤드인 대가리로 구성된다.>

-제어장치란 계산하는 사람의 마음상태의 모든것들이다.예를 들어 어떤 사람이 있는데 '난 물을 마실거야' '난 밥을 먹을거야' '난 잠을 잘거야' '난 롤을 할거야' ' 난 헌팅을 갈거야' 이렇게 5개가 이사람이 할 수 있는 전부라고 가정하면,이 사람은 절대 소변을 볼 수 없고 밥쳐먹고 롤을 하다가 밤에 헌팅을 하러 갈 것이다.이 위의 5개 상황을 제외하고는 다른 상황은 할 수 없다.위에 5개의 명령 중 한가지를 하거나 아무것도 안하거나를 각 칸칸마다 지정해 놔야한다. 

-테이프는 칸마다 제어장치에 의해서 위의 5가지 명령 중 한가지를 기록해 놓은 일종의 계획표라고 보면된다.첫번째 칸에 롤,두번째 칸에 잠,세번째 칸에는 헌팅 이렇게 해놓으면 그 위치에 갈 때마다 쓰여져 있는 명령을 수행한다.

-대가리는 이제 가상의 플레이어라고 생각하면된다.각 칸에 갈 때마다 충실히 테이프에 적혀진 기록을 이행한다.낙뢰가 떨어지지 않는 한 세번째 칸에 가면 헌팅을 갈 것 이다.

8.저 문제 내가 풀고싶네요!

->클레이 수학연구소에서 발표한 7개의 밀레니엄문제중 하나가 바로 이 P-NP문제이다.상금이 100만달러가 걸린 문제로 만약 너가 이 문제를 풀게되면,수학,암호학,알고리즘연구,인공지능,게임이론,멀티미디어 프로세싱,철학,경제학 등 다양한 분양에 엄청난 영향을 끼칠 것이 분명하다.할 거 없으면 도전해라.

-위키백과,네이버 참고-

[[헬조센]희희]

?

[해파리6]

!

[해파리6]

저도 깊이는 모르겠는데 NP-COMPLETE문제가 아마 NP문제중 근원에 해당하는 문제라서 NP COMPLETE문제가 증명되면 도미노효과로 나머지 역시 증명되는것이라서 NP COMPLETE역시 NP문제이며, NP가증명되는 동시에 P가 되는 셈이 되어서 NP=P가 되는 것이라고 생각됩니다.제가 써놓고 어리버리하네요

[해파리6]

이미테이션게임!

[해파리6]

리만가설을 NP로 치환하여 P가 됨을 보이면 두 난제가 동시에 해결되는 것이겠죠.하지만 P와 NP 문제는 컴퓨터와같은 알고리즘으로 푸는 문제들로 명령에 따라 알고리즘이 구성하여야 하므로 리만가설처럼 X=4이므로 4는 어쩌구 하는 수학적 증명으로 하는 방법에 대해서 하나하나 알고리즘화 하기 힘들겠죠.그리고 알고리즘 자체가 증명도 아니구요.그러므로 불가능하다봅니다.게다가 결정적으로 리만가설은 NP문제인지 NP COMPLETE 문제인지조차도 모릅니다.

[늅늅]

하이오랜만

[해파리6]

ㅎㅇㅎㅇ

[해파리6]

음식사진 올리던 해파리는 해파리팸중 다른 해파리고 저는 예전부터 해파리와함께하는 시리즈를 올리던 또다른 해파리입니다.

[해파리6]

아니죠 만약 저와 음식 올리는 해파리6이 같은 해파리임을 증명하려면 근원이 같아야하는데 음식해파리와 저는 다음 아이디와 비밀번호가 다르므로 근원이 흐려지므로 NP=P정리를 사용하실 수 없습니다.

[화령군]

저런 문제 해결하면 교과서에 자기 이름 박기 가능

[럭키찬스]

문송합니다

[세계평화]

해파리7 보고싶다 왜 안오냐

[샤르트르]

아 이과냄새

[풍신수길]

문송..