[알고리즘] P, NP, NP-Complete, NP-Hard

분명, 학교에서 배운거 같은데 기억이 안나네.

다시 한 번 정리하는 차원에서...

먼저 Turing Machine(튜링 머신, 이하 TM)에 대해서 알아야겠다.

Turing Machine(튜링 머신)

TM은 Alan Turning에 의해 소개된 가상의 기계이다. (무한한 메모리와 저장장치-테이프-를 가진...)

간단하게 생각하면, 오늘날의 컴퓨터와 같다고 생각하면 된다.

(단, 오늘날의 컴퓨터는 메모리/저장장치의 제약이 있다.)

여기에서 Non-deterministic Turing Machine(비결정적 튜링 머신, 이하 NTM 혹은 NDTM)이라는 것을 생각해 내었는데,

이것 또한 가상의 기계이다. (아니, 상상의 기계에 가깝다고 해야 하나...)

원래 TM에서는 Current State와 Tape Symbol에 따른 Action이 최대 1개이다.

NTM은 같은 상황에서 Action이 1개 이상도 될 수 있다.

NTM에서 어떤 Action을 선택할 것인가 결정하는가?

http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine#Resolution_of_multiple_rules

위키피디아의 설명에 따르면, Branches 수 만큼, Computation Tree를 가지게 되는 것이다.

(TM은 하나의 Computation Path를 가진다.)

이러한 기계를 Non-deterministic Turing Machine라고 하고,

원래의 Turing Machine을 NTM과 구분하기 위해 Deteministic Turing Machine이라고 한다.

DTM -> NTM 으로 쉽게 변환이 가능하다. DTM은 NTM의 Special case 중 한 가지일 뿐이니깐,

그럼 NTM -> DTM 으로 변환이 가능한가? 가능하다... 가능하긴 한데...

변환된 DTM의 Accepting computation의 길이는 NTM의 Shortest accepting computation 길이의

Exponential 한 만큼 길어진다고 한다.

P, NP

Decision Problem(결정 문제)라는 것이 있다.

( http://en.wikipedia.org/wiki/Decision_problem )

어떤 유한한 입력에 대해서 Yes/No로 대답할 수 있는 문제를 말한다.

이런 문제들은 단순히 Yes/No를 대답하는 것보다 복잡하다.

문제에 대한 최적의 해를 알아야 하기 때문이다.

P, NP 라는 것은 Decision Problem의 Complexity class(복잡도 종류)를 말한다.

P는 DTM에서 다항시간^[각주:1]에 풀 수 있는 문제의 복잡도이다. (즉, 현재의 컴퓨터에서 다항시간에 풀 수 있다는 것이다)

NP는 NTM에서 다항시간에 풀 수 있는 문제의 복잡도이다.

P 문제는 NP 문제에 포함되므로, 따로 P 문제라고 구분해서 부르지 않는듯 하다.

단지 NP 문제 중, 컴퓨터로 문제를 푸는 알고리즘이 비싼(O(n!) or O(k^n) 정도) NP Problem 을

NP-Complete Problem이라고 구분해서 부른다.

P = NP 인가?에 대한 질문은 아직까지 컴퓨터 과학계에서 해결하지 못한 문제이다.

NP-Complete, NP-Hard

이 두 가지는 정의가 좀 어렵다. 공식정인 정의는 알고리즘 책을 찾아보는게 좋겠다.

좀 쉽게(비공식적인 정의?) 적어보자면...

NP-Hard는 NP에서 가장 어려운 문제만큼 어려운 문제를 말한다.

하지만 이름과는 다르게 꼭 NP일 필요는 없다.(Decision Problem일 필요는 없다는 말)

NP-Complete는 NP에서 가장 어려운 문제를 말한다.

일반적으로 NP-Complete 문제들은 다항시간에 푸는 알고리즘이 없다고 추측한다.

하지만 이것은 증명된 것은 아니다.(존재하는지도 존재하는 않는지도 모른다는 말)

NP-Complete 정의에 따르면 모든 NP Problem 은 NP-Complete problem 으로 환원 될 수 있다고 되어있다.

다시 말해, 하나의 NP-Complete 문제에 대해 다항시간에 푸는 알고리즘을 찾아내거나

혹은 반대로 하나의 NP-Complete 문제에 해서 다항시간에 푸는 알고리즘이 없음을 증명한다면,

P = NP? 질문에 대한 답을 찾아낸 것이다. (그리고 추가로 100만달러 보너스까지!!!)

결론

NP-Complete 문제, NP-Hard 문제는 컴퓨터로 최적의 해를 구하시에는 어마어마한 시간이 걸리는 문제다.

따라서 이런 문제의 최적의 해를 찾기 위해 삽질하지 말고,

Approximation Algorithm이나 Heuristic Algorithm을 택하자.

(사실 이런 문제는 ACM 이나 Google Codejam 에는 안 나올꺼 같지만...)

P.S

이 글에선 P, NP, NP-Complete, NP-Hard를 용어를 형용사와 ~~ 문제를 의미하는 명사로

혼용하여 사용하였는데, 문맥에 맞추어 해석하면 됩니다.

P.S 2

이 글을 관심있게 읽을 사람이 있을까 싶지만은,

혹시나 오류가 있다면 리플을 부탁합니다.

각주.

1. T(n) = O(n^k), k 는 상수. [본문으로]