P, NP, NP-COMPLETE, NP-HARD

1. NP : yes 또는 no로 답할 수 있는 문제에서 yes 라는 답을 주었을 때, 그 답이 정말 yes가 맞는지를 빠른시간(polynomial time)안에 확인할 수 있으면, 그 문제를 NP문제라고 한다. 또는 Non-deterministic Turing Machine 에서 다항시간안에 풀 수 있는 문제이다.

2. P : NP문제 중에서도 답을 polynomial time안에 찾을 수 있으면 그 문제를 P 문제라고 한다. Deterministic Turing Machine에서 다항식나내에 풀 수 있는 문제이다.

3. NP-COMPLETE : 모든 NP 문제들이 빠른 시간안에 변환(reduction)될 수 있는 문제이다. 모든 NP문제를 빠른시간안에 NP-COMPLETE 문제로 변환할 수 있기 때문에, NP-COMPLETE 문제만 풀면 모든 NP문제를 빠르게 풀 수 있다. NP problem 중에서도 해결하는 알고리즘의 시간이 많이 드는(O(n!) 이나 O(k^n)정도의 시간) 문제를 뜻한다. 다르게 말하면 NP문제중에 가장 어려운 문제라고 할 수 있다. 위에서 모든 NP문제를 NP-Complete 문제로 환원할 수 있다고 하였는데, 이때 NP-Complete 문제가 문제를 해결하는데 드는 시간이 많이 걸리기 때문에, 이 NP-Complete 문제에 대해서 Polynomial Time안에 해결하는 방법을 찾으면 P=NP 가 되는 것이고, 만약 Polynomial time 안에 해결하는게 불가능하다는 것을 증명하면, P는 NP와 같지 않다는게 증명이 되는 것이다.

4. NP-HARD : 정말 어려운 문제로, NP문제이기도 하고, 아니기도 하다. TSP(Traveling Salesman Problem) 문제가 그에 해당하는데, 세일즈맨이 최단 경로로 모든 방문지를 방문하는 방법을 구하는것인데, 만약 최단경로라고 하는 답을 준다고해도, 우리는 그것이 최단경로인지 확인해보려면 모든 경로를 방문해서 그중에서 최단경로를 구하고 주어진 최단경로와 비교해보아야 하기 때문에 빠른시간(polynomial time) 안에 하는 것은 불가능하다.

참고사항

 - 튜링머신 : Alan Turing에 의해 고안된 가상의 기계로, 오늘날의 컴퓨터, deterministic turing machine 이라고도 한다.

 - Non-deterministic Turing Machine : 가상의 기계이고, TM에서 Current State와 Tape Symbol에 따른 Action이 최대 1개인데, NTM에서는 1개 이상의 Action을 가진다. 다시말하자면, 컴퓨터가 어떤 state와 symbol을 가질때 여러개의 동작을 할 수 있다는 것이다. 여기서 동작은 Branch 의 수많큼 Computation Tree를 가지게 된다.

DTM -> NTM은 변환이 쉽다, DTM은 NTM의 어떤 한가지 동작일 뿐이다.(special case)

NTM -> DTM은 변환이 가능한데, 이때 변환된 DTM은 Accepting Computation의 길이가 NTM의 Shortest accepting computation 길이의 exponential 한 만큼 길어진다고 한다...

 - P, NP문제는 어떤 Decision problem의 복잡도의 종류를 구분한 것이다.

 - Decision problem은 yes 또는 no로 답할 수 있는 문제를 말한다.

P, NP, NP-Complete, NP-Hard 관계에 관한 다이어그램

참고사이트

 - http://yoonho.info/19

 - http://azza.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-P-NP-NPComplete-NPHard