P와 NP의 개념

안녕하세요 ㅎ_ㅎ

종강을 했습니다..드디어XD

이번학기에는 알고리즘을 들었었는데요, 그 중에 꼭!! 쓰고싶은 주제가 있어서 까먹기 전에 얼른 쓰려고..

엄청 길어질듯한 느낌..

그 주제는 바로!! NP-Complete Problems입니다.

정말 이 주제를 배울 수 있어서 너무너무 재밌었어요XD

이 챕터에서 P, NP, NP-Hard, NP-Complete에 대해서 배웠어요.

하나하나 순서대로 알아봅시다. 최대한 쉽게 설명할게요! 

Polynomial Time : Class P

---

클래스 P란 간단합니다.

어떤 문제에대해서 Polynomial Time Algorithm이 존재하면 그 문제는 클래스 P에 속합니다.

(그 알고리즘이 클래스 P에 속하는 것이 아닌, 문제가 속한다는 것에 헷갈리시면 안됩니다.)

 Polynomial Time Algorithm?

다항시간 알고리즘? 

이게 뭘까요?

간단하게 말하면, 

"n^k형태로 Worst time Complexity가 정의되는 알고리즘 (k는 상수.)"

입니다. 

우리가 배운 알고리즘들 중에 최악수행시간이 n^k인게 뭐가있을까요?

음..간단하게 정렬 알고리즘부터 생각해볼까요?

선택정렬, 삽입정렬, 버블정렬, 퀵정렬..이 네가지 정렬은 최악수행시간이 n^2이죠? 2는 상수이니 

이 네가지 정렬 알고리즘들은  Polynomial Time Algorithm이라고 할 수 있겠네요. 

즉, 이 정렬알고리즘이 클래스 P에 속하는게 아니라!!!!!!!!!!!!!!!

그 "문제"가 클래스 P에 속하게 되는거죠. 

그러니까 간단하게 정리하면, 

어떤 문제에 대해 Polynomial Time, 즉 다항시간에 그 문제에 대한 solution을 찾아낼 수 있으면,(= Polynomial Time Algorithm이 있으면) 그 문제는 클래스 P에 속합니다.

쉽죠???

그리고 우리는 지금부터 어떤 알고리즘이 n^2든, n^3이든, n^4이든  Polynomial Time 이면, 효율적(efficient)인 알고리즘 으로 볼거에요. 

하.지.만....

우리가 지금까지 접한 문제들을 생각해봅시다. 다 뭔가 시간은 오래걸려도 풀리지 않았나요? 

하지만, 세상에는 아직 못푸는 문제들이 있답니다...아니 정확히 말하자면, 풀 수 있지만,  Polynomial Time Algorithm이 개발되지 않은 문제들이 있어요.

못푸는건 아닙니다......다만...아직까지...세계 각지에있는 천재적인 사람들이 도전해도...다항시간에 안풀린것 뿐...ㅎ

자..그렇게 많은 사람들이 도전했는데도 다항시간 알고리즘이 개발안된 걸 보면 정말 "어려운"문제겠죠?

이 "어려운 문제"에 대해서 이제 설명드릴게요.

Non-Deterministic Polynomial Time : Class NP

---

자! 이제 NP에 대해서 이야기 해보겠습니다. 

먼저, Class NP의 정의에 대해 어렵게 설명해드리면, 

"그 문제를 해결하는 Non-Deterministic Polynomial Time algorithm이 존재하면, 그 문제는 클래스 NP에 속한다"

라고 합니다.

NP역시 알고리즘이 클래스 NP에 속하는 것이 아니라, 문제가 클래스NP에 속하는 것입니다.

정의를 보시고...다들 엥...;;; 하실텐데요. P클래스와 정의가 굉장히 비슷하죠? 

다만 Non-Deterministic이 붙었는데..이게 무슨소리일까요?

직역을 하자면, "비 결정적"이라고 할 수 있겠네요. 

비 결정적 다항시간 알고리즘이 존재하면, 그 문제는 클래스 NP에 속한다..흠..

그래서 ㅡㅡ 이 비 결정적 다항시간 알고리즘 이 무슨소리야;;

정말!!간단하게 말하면, 같은 인풋이 들어가도 다른 아웃풋을 낼 수 있는 알고리즘입니다.

 

우리가 지금까지 배운 알고리즘을 생각해볼까요? 정렬은 좀 그렇고.. 

음..팩토리얼을 계산하는 알고리즘이 있다고 생각해볼게요.

같은 인풋이 들어가면 무조건!! 같은 아웃풋이 나와야겠죠??! 

그런데 비 결정적 다항시간 알고리즘은 다른 아웃풋이 나올 수 있는 알고리즘인거에요. 

그럼 비 결정적 알고리즘이라고 하면되지 왜 비결정적 "다항시간"알고리즘?;;

비 결정적이라는 것은 같은 인풋이 들어가도 알고리즘이 매번 다르게 작동해

 다른 아웃풋이 나올 수 있는 것이라고 했죠?

어떤 알고리즘이 있다고 생각해볼게요. 

이 알고리즘으로 정말 굉장히 어려운 문제를 풀거에요. 

이 알고리즘이 어떤 인풋에는 어케어케 동작해서 어떤 아웃풋을 냈어요.

그것도 다항시간에요!

하지만, 어쩔때는 다항시간안에 끝나지 않을 수도 있습니다. 

그래서 헷갈리지 않아야 할 것은 비결정적 다항시간 알고리즘이 !!!존재하면!!!! 클래스 NP에 속하는 거에요.

하지만.....공부하는 친구들의 마음은 다 똑같은것...ㅎ

이 클래스 NP에 대해서 이해가 가신 분들도 계시겠지만, 

아직 이해가 가지 않은 분들도 계실거에요.

위 설명으로 말고, 클래스NP를 정말 간단하게 설명드리면,

"어떤 certificate가 다항시간(Polynomial Time)에 verify할 수 있으면, 

그 문제는 클래스 NP에 속합니다"

...

......

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ..죄송합니다..

더 이해가 안가시나요? 

자. 예제를 들거에요 이제부터. 이 예제를 읽으시고 나면, 바로 이해가 가실겁니다.

수업시간에 교수님이 들어준 예제에요. 

간단하게 설명드릴게요.

자 눈을 감고 상상하는겁니다. 나는 보물탐험가?..암튼 보물을 찾으러 다니는 사람이에요.

지금 제 앞에는 강이 있고, 외나무 다리가 그 위에 있어요. 

외나무다리 끝에는 한 동굴이 있는데, 그 동굴안에는 보물이 잔뜩!!! 있어요.

하지만.. 외나무 다리에는 버틸 수 있는 무게가 있어요. 

음..딱 200kg을 버틸 수 있다고 해볼까요?

그리고 저는 60kg라고 해볼게요. 

그리고 저기 건너편에 있는 동굴안에는 보물이 있다고 그랬죠? 

정말 친절하게 보물 하나하나에 무게가 얼마고, 얘의 값어치는 얼마인지 

아주 친절하게 적혀있습니다. 

저는 저 건너편에 있는 보물들을 배낭에 가져오는데, 

이 보물들의 값어치가 2억이상이 되게 가져와야해요. 물론 무게도 저를 합쳐서 200kg를 넘으면 안됩니다.

200kg를 넘게되면, 외나무다리가 무너지기 때문이에요.

즉, 이게 가능하냐고 묻는 문제를 받았다고 해볼게요. 

Q : 저 동굴안에서 값어치가 2억이상이고, 무게가 200kg넘지않는 보물들의 조합이 있니?? 없니?? (이렇게 있냐 없냐라고 묻는 문제를 "결정문제(Decision Problem)"이라고 합니다.)

일단 외나무다리를 건너봅시다. 그리고 동굴안에서 저는 고민하죠. 보물을 넣고 빼면서 얘가 2억은 넘는지, 무게는 초과되지 않는지.. 넣고 빼고, 넣고 빼고...

정말정말 오래걸리겠죠?

비트로 생각해볼게요. 보물이 n개가 있다고 하고, 각 보물에 번호가 메겨져 있어요.

자 그럼 n비트가 나오겠죠? 그리고 각 보물을 배낭에 담으면 1, 아니면 0이라고 할게요. 

그럼 정말 많은 조합이 생길 수 있을거에요. 

000001101001010100...10100 => 2억원 넘고 200kg안되냐

0010101111010100001....10001 => 2억원 넘고 200kg안되냐

.

.

.

정말 오래걸리겠죠? 

보물이 n개라고 했으니 2^n번을 해봐야겠네요.

(각 자리마다 0,1 의 가능성이 있으니까 n비트면 2^n이겠죠 ? XD) 

보물이 100개만 되도....ㄷㄷ...

자!! 이 예제는 잘 이해하셨나요?

 저는 수업을 들으면서 이예제가 제일 이해가 잘가서 이 예제를 사용했어요.

이거랑 NP랑 뭔상관인데요 그래서 ㅡㅡ

앗..네..

근데 어떤사람이 저에게 어떤 비트 시퀀스를 줬어요. 

10101010111110101000....101011

이렇게요!

그러고 이렇게 말하죠.

"이렇게 보물들을 조합해볼래?"

각 보물에 번호가 메겨져있다고 했을 시, 

저는 그냥 건너서 1인 비트들의 보물들을 찾아서 배낭에 담기만 하면되죠. 

그게 어렵진않겠죠?? 그냥 비트 시퀀스 보고 얘담고.. 얘담고... 그렇게 담았어요.

근데!!!!!!!!

근데 정말 신기하게 값어치도 2억이 넘고, 

나까지 포함에서 200kg를 넘지 않은거에요!!!!!!!!!!!!!

근데 문제는 뭐였죠?

Q : 저 동굴안에서 값어치가 2억이상이고, 무게가 200kg넘지않는 보물들의 조합이 있니?? 없니?? 

였죠? 

근데 우리가 어떤 사람이 준 비트 시퀀스를 받고 그대로 조합해보니 2억이 넘고, 

무게도 200kg도 넘지않았어요.

그럼 

어!!!있던데!!!??!?! 있어!!!! 라고 대답할 수 있겠죠. 우리는 저 문제를 푼거죠?? 

있으니까!!!

그리고 우리가 이 조합하는 과정. 그냥 비트시퀀스 대로 따라 담는거, 어렵나요? 

당연히 다항시간안에 끝납니다.

우리는 다항시간(Polynomial Time)에 대답을 한거죠. 어떤 문제에 대해서요.

위에서 제가 말씀드렸죠 NP의 정의.

"어떤 certificate가 다항시간(Polynomial Time)에 verify할 수 있으면, 그 문제는 클래스 NP에 속합니다"

여기서 certificate란, 이 예제에서는 어떤사람이 준 비트시퀀스를 의미합니다. 

조금 감이 오시나요?

verify. 확인하다라는 뜻이죠?

그러니까. 어떤 certificate를 받고, Polynomial Time에 확인할 수 있으면 그 문제는 클래스NP인거죠.

그럼 이런 궁금증이 들 수 있겠죠? 

만약 그 certificate이 답이 아니면? 

위 문제에 대해서는 뭐 값어치의 총 합이 2억이 되지 않거나,

무게가 200kg넘으면 어떻게 될까요?

우리가 그 조합을 배낭에 담는건 여전히 다항시간이겠죠? 근데 값어치의 합이 1억이야.

그럼 우리는 

Q : 저 동굴안에서 값어치가 2억이상이고, 무게가 200kg넘지않는 보물들의 조합이 있니?? 없니?? 

A : 아니?NO!!!

라고 말할 수 있을까요? 

지금 제가 받은 certificate이 NO라고 이 동굴안에는 2억이 넘고, 200kg가 안되는 조합이 없다고 단정지을 수 있을까요?

다른조합은 그렇게 만들 수도 있겠죠? 우리는 모르는거에요 아직.

NO라고 단정지을 수 없다는 겁니다.

그러면 어떻게 대답하면 될까요?

정답은 그냥 "가만히 있으면 된다"

아무 대답도 안하면 되요 그냥 

근데 만약 YES인 답이 나오면 YES!!있어!!!라고 말하면 되는거죠.

이제, 

"어떤 certificate가 다항시간(Polynomial Time)에 verify할 수 있으면, 그 문제는 클래스 NP에 속합니다."

이 말뜻이 조금 이해가 가시나요? 

(아 글이 너무 길어지는 것 같아 걱정이네요 ㅠㅠ 쉽게 설명드리고 싶은 마음에..)

자.. 그럼 마지막으로..음 

만약에 어떤 사람이 가중그래프를 하나 주고, 여기서 weight가 최대 k인 최소스패닝트리(MST)가 있어? 

이 문제가 NP에 속하는지 알아봅시다. 

어떤 사람이 certificate를 줬네요..!! 운좋게도 말이죠!

그 certificate를 살펴볼까요? 

일단 "스패닝트리"의 조건을 만족해야겠죠.

이 certificate가 그래프의 모든 버텍스를 포함하는지,(버텍스가 n개인지) 

또한, n-1개의 엣지로 구성되어 있는지, 트리이기 때문에 사이클은 없는지. 

판별해볼거에요. 이를 판별하는데는 다항시간이 걸릴겁니다.

또한, 이 엣지들의 weight들의 합을 구할거에요. 이 합을 구하는데도 역시 다항시간이 걸릴겁니다. 

만약 이 합이 k보다 크다면? 가만히 있으면돼요.

근데 합이 k보다 작다? 그럼 어!!있어!!YES!!라고 대답하면 되겠죠?

근데.....

우리는 최소스패닝트리를 구하는 알고리즘을 알아요.

그것도 다항시간에 수행되는 알고리즘이요.

바로 프림 알고리즘과 크루스칼 알고리즘이죠.

다항시간에 수행되니,

위 두 알고리즘의 시간복잡도가 어떻든 효율적(efficient)으로 보자고 그랬죠?

만약에 저 문제를 받았으면 certificate 필요없이 그냥 프림이나 크루스칼 돌리면 최소 스패닝 트리가 나오겠죠?

그것도 다항시간에??

그리고 얘네 가중치의 합이 k넘는지, 안넘는지만 보면 되겠죠??? 다항시간이 걸리겠죠????

즉....제가 하고싶은 말은 Class P에 있는 애들은 다항시간 알고리즘이 존재하는 문제들입니다.

하지만, certificate를 줘도 풀 수 있죠. 다항시간에.

즉!!!!! Polynomial Time Algorithm이 존재하는 문제, 즉 클래스 P에 있는 문제들은 모두 클래스 NP에 속합니다.

NP의 정의를 다시 볼까요?

"어떤 certificate가 다항시간(Polynomial Time)에 verify할 수 있으면, 그 문제는 클래스 NP에 속합니다"

하지만 클래스 P에 있는 문제들은 그냥 풀 수도 있지만 (다항시간 알고리즘을 이용해서), certificate을 줘도 다항시간에 당연히 풀 수 있겠죠?? 

그러니까 P는 NP에 속하게 되는 겁니다. 

와...글이 정말 길어졌는데...ㅜㅜㅜ

이렇게 길어질 줄 몰랐어요...ㅎㅎㅎ..

NP-Hard와 NP-Complete는 다음글에서 소개해야겠네요..

어떤가요? 조금 이해가 가시나요? 최대한 쉽게 설명드릴려고 했는데..ㅠㅠ

정리하자면!

Polynomial Time Algorithm : n^k형태로 Worst time Complexity가 정의되는 알고리즘 (k는 상수.)

클래스 P : 어떤 문제에대해서 Polynomial Time Algorithm이 존재하면 그 문제는 클래스 P에 속합니다.

클래스 NP : 어떤 certificate가 다항시간(Polynomial Time)에 verify할 수 있으면, 그 문제는 클래스 NP에 속합니다. 또는 그 문제를 해결하는 Non-Deterministic Polynomial Time algorithm이 존재하면, 그 문제는 클래스 NP에 속합니다.

이해가 가시나요? 너무 길어도 ㅠㅠㅠ 한번쯤 읽어보는 것을 추천드립니다 XD

도움이 되었으면 좋겠어요!!

NP-hard, NP-complete 읽으러가기