P / NP 의 개념

스케줄링 카테고리의 첫 글이 스케줄링에 관련된 게 아니라서 아이러니하지만, P / NP / NP-Hard / NP-Compelete 개념을 먼저 알고 넘어가는게 좋다고 생각해 첫 게시글을 P / NP / NP-Hard / NP-Compelete를 다루기로 하였습니다. ㅎㅎ

 

일단 스케줄링 문제들은 보기엔 간단하더라도 대부분 문제를 해결하기가 매우 까다롭습니다.

job의 갯수가 세개 라면, 3!으로 총 여섯번의 경우의 수를 탐색해보면 최적의 해를 구할 수가 있겠죠. 그런데 job의 수가 40개이고, job들 마다 ,release time이 다르고, due date와 같은 제약조건이 제각각인 상황에서 최적의 스케줄링을 하라고 하면? 뭐 그냥 간단히 40!의 방법을 다 해보면 될 테지만 40!은 엑셀 함수를 이용해 계산해보니 '8.15915E+47' 라고 나오네요......ㅋㅋㅋㅋㅋ 딱 보아도 풀 수는 있지만 엄청나게 시간이 걸리는 어려운 문제인 듯 합니다.... 지금부터 P와 NP에 대한 제대로 된 개념과 예시를 알아보겠습니다!!  

 

 

Class P (Polynomial Time)

---

먼저 P는 'Polynomial time' 의 약자입니다. Polynomial time???? 우리말로 하면 다항시간이라는 말이에요! 

일단 P의 정의는 다음과 같습니다. 

 

P는 다항 시간(polynomial time)에 결정론적(deterministically)으로 해결 가능한(solvable) 문제들의 집합입니다. 다시 말해, 어떤 결정 문제(decision problem) X에 대해, 주어지는 입력(input)이 참인지 거짓인지를 다항 시간에 결정론적으로 해결하는 알고리즘이 존재하면 X∈P입니다.

출처: https://gazelle-and-cs.tistory.com/74 [Gazelle and Computer Science]

간단하게 표현하면 "n^k형태로 Worst time Complexity가 정의되는 알고리즘 (k는 상수.)" 입니다. 

혹시 자료구조,알고리즘에 대해 공부하신 적 있나요?? 

대부분의 정렬 알고리즘들이 Big(O)의 시간복잡도가 n^2입니다. 그렇기 때문에 정렬 알고리즘들은 Polynomial Time Algorithm이라고 할 수 있습니다. 그러니까 이러한 문제들은 다항시간안에 해결할 수 있는 알고리즘을 갖고 있으니 클래스 P에 속한다고 할 수 있겠죠!!

 

그러면 서두에서도 얘기한 NP는 다항시간에 해결할 수 없는 문제들을 NP라고 할까요? 그러면 좋겠지만 그건 아닙니다. ㅎㅎ

 

 

 

Class NP (Non-Deterministic Polynomial Time)

---

앞에서 P는 어떤 약자인지 알아보았는데, 그럼 N은 어던 약자일까요?? 제목에도 쓰여있지만 N은

Non-Deterministic라는 뜻의 약자입니다. 해석해보면 비결정적?? 라는 뜻이네요.... 그러니까 붙혀서 읽어보면 

NP는 '비결정적 다항시간'이란 뜻이네요 ㅎㅎㅎ?ㅎㅎㅎ

우선! NP의 정의는 다음과 같습니다.

 

 

NP는 다항 시간에 비결정론적(nondeterministically)으로 해결 가능한 문제들의 집합으로, 어떤 결정 문제 X에 대해, 주어지는 입력이 참인지 거짓인지를 다항 시간에 비결정론적으로 해결하는 알고리즘이 존재하면 X∈NP입니다. NP의 또 다른 정의는 다항 시간에 결정론적으로 검증 가능한(verifiable) 문제들의 집합입니다. 자세히 살펴보자면, 어떤 결정 문제 X에 대해 어떤 입력과 입력 크기의 어떤 다항식으로 표현되는 크기를 갖는 증거(certificate)를 함께 제공 받았을 때 이를 다항 시간에 결정론적으로 검증하는 알고리즘이 존재하면 X∈NP입니다.

출처: https://gazelle-and-cs.tistory.com/74 [Gazelle and Computer Science]

NP-완전 이해하기 (NP-Completeness)

 

정의만 봐서는 정확하게 NP가 뭔지 알기는 어려운것 같습니다. '비결정론적으로 해결하는 알고리즘이 존재하면 NP'부터 아래 그림을 보며 알아보겠습니다.

 

왼쪽 그림은 Deterministic Polynomial Time Algorithm을 설명하는 그림입니다. 어떤 Algorithm에 의해서 결과가 나왔는지 알고, 다항시간안에 해결되는 문제입니다. 오른쪽 그림은 Non-deterministic Polynomial Time Algorithm을 설명하는 그림인데, 어떤 Algorithm에 의해 결과가 나오는지는 알 수 없지만 다항시간안에 풀리는 문제입니다. 이런 경우를 정의에서 '비결정론적으로 해결하는 알고리즘이 존재하면 NP'라고 표현하였고, 이러한 문제를 NP 클래스에 속한다고 합니다. (NP-class에 속한다고 표현이 정확한 표현입니다!!)

 

전부 알아본거 같지만 NP class에 속할 수 있는 조건이 하나가 더 있습니다! 즉, NP-class에 속하는 문제의 종류는 두가지라고 할수도 있겠네요. 두 번째로 NP-class에 속하는 경우는 정의로 돌아가 다시 보면 '어떤 결정 문제 X에 대해 어떤 입력과 입력 크기의 어떤 다항식으로 표현되는 크기를 갖는 증거(certificate)를 함께 제공 받았을 때 이를 다항 시간에 결정론적으로 검증하는 알고리즘이 존재하면' 이라고 나옵니다. 좀 더 쉽게 예시와 함꼐 설명해보겠습니다. 

강을 사이에 두고 60kg이 나가는 사람과, 보물이 가득한 동굴이 있습니다. 강에는 200kg까지 버틸 수 있는 외나무다리가 있습니다. 동굴안의 보물들에는 다행히 보물의 각각의 보물의 값어치가 얼마인지, 무게는 얼마인지가 모두 적혀있습니다. 그렇다면 동굴안에는 값어치가 2억이상이면서 본인을 포함해서 200kg넘지 않아 보물을 챙겨 안전하게 돌아올 수 있는 보물들의 조합이 있을까요???

 

어떤 보물을 챙기면 1, 챙기지 않으면 0이라고 하면 보물이 n개 있다고 하면 1과0의 조합은 총 2^n개가 나오게 됩니다. 즉 Polynomial X입니다. 만약 어떤 사람이 2^n개의 시퀀스 중 하나의 시퀀스를 줬다고 합시다. (ex.0111...11010101) 이 보물들을 시퀀스를 따라 조합해보니 2억이 넘고, 200kg가 넘지 않았습니다. 그렇다면 이 문제에는 답이 있는 문제였네요! 그리고 Polynomial Time안에 해결하기도 했습니다.

-->어떤 certificate가 다항 시간에 verify할 수 있기 때문에, 이 문제는 클래스 NP에 속합니다. 

 

다시 말해, 모든 경우를 고려해보지는 않았고, 몇개의 해결책이 있는지도 모르지만 적어도 다항시간안에 하나의 해결책이 있고, 그 해결책을 찾는데 성공했습니다. 이렇게 이 문제는 답이 있고, 답은 몇개가 있고, 첫 번쨰 답은 a, 두번째 답은 b 세번쨰 답은 c........이렇게 전부를  구하지 않아도 어떤 답을 다항시간에 구할 수 있다면 클래스 NP에 속하는 겁니다!

 

클래스 NP에 속하는 두가지 경우를 정리해보겠습니다!-!

1. 어떤 Algorithm에 의해 결과가 나오는지는 알 수 없지만 다항시간안에 풀리는 문제

2. 어떤 certificate가 다항시간에 verify할 수 있는 문제

 

 

 

다음에는 NP-Hard와 NP-Compelete에 대해서 알아볼게여~~~~