[알고리즘] P, NP

P와 NP는 "문제"를 구분하는 기준이다.

 

어떤 문제가 Polynomial Time Algorithm이 존재하면 그 문제는 P인 것이고,

어떤 문제를 해결할 때 Non-Deterministic Polynomial Time Algorithm이 존재하면 그 문제는 NP인 것이다.

 

쉽게 말하면 어떤 문제가 다항시간 안에 결정론적 튜링머신으로 답을 찾을 수 있는지 비 결정론적 튜링머신으로 답을 찾을 수 있는지를 구분한 것이다.

 

결정론적 튜링머신 - 정해진 명령을 수행하는 가상의 기계비결정론적 튜링 머신 - 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우, 즉 입력 값이 주어진 문제의 해답인지를 검사하는 장치이다.

 

**"시간"으로 구분한 것이다 아니다. P NP 모두 다항시간에서 판단이 된다!! **

 

 

 

polynomial time Algorithm(다항 시간 알고리즘)이란?

 

최악의 수행 시간이 O(N^K)의 시간복잡도를 가지는 알고리즘 (k는 상수)

우리가 지금까지 배우고 풀어본 대부분의 문제들은 이에 속한다. (정렬문제, 최대공약수 문제, 소수 판별 문제 등등)

지금까진 우리는 어떤 알고리즘이 O(N^10)의 시간복잡도를 가지고 있으면 엄청나게 느린 것으로 생각했다. 하지만 적어도 이는 그게 10년이 걸리던 20년이 걸리던 우리가 예상할 수 있는 시간 안에 풀린다. (최악의 시간복잡도를 알고 있기 때문에)

 

 

 

Non-Deterministic Polynomial Time Algorithm (비 결정적 다항시간 알고리즘) 이란?

 

어떤 문제를 풀기 위한 알고리즘이 input 값이 같아도 알고리즘을 시행할 때 마다 다른 output을 내지만,  문제에 대한 답에 대한 검증이 다항 시간 안에 이뤄질 수 있는 문제를 뜻한다.

즉, 결정론적 튜링머신으로는 다항 시간 내에 풀어낼 수 없는 문제들을 NP 문제라고 한다.

 

 

 

여기서 P에 속하는 문제들은 당연히 그 답은 그 답에 대한 검증도 다항시간 안에 이루어진다.

그렇기 때문에 P는 NP의 부분집합이다.