[알고리즘] P vs NP

P vs NP 문제 : 컴퓨터가 답이 되는 몇 가지 경우는 빠르게 찾을 수 있지만, 최적의 답을 빠르게 찾을 수는 없는 모든 경우에 대한 문제

 

- P (Deterministic Polynomial time, 결정론적 다항 시간)

• 다항식 시간복잡도를 가진 알고리즘으로 해결되는 문제 집합 (O(n), O(n²))
• P 클래스는 입력 크기에 대해 다항 시간 안에 결정론적 순차 기계에서 해결할 수 있는 모든 결정 문제들을 포함

 

- NP (Non-deterministic Polynomial time, 비결정론적 다항 시간)

• 비결정적 다항식 시간 알고리즘으로 해결되는 문제 집합 (O(n!), O(2^n))
• NP 알고리즘은 주어진 해에 대해 'Yes'를 확인해야 하므로 결정 문제로 변형
• NP 클래스는 긍정적인 해답을 주어진 정보로 다항 시간 안에 검증할 수 있는 결정 문제들 또는 비결정론적 기계에서 다항 시간 안에 해답을 찾을 수 있는 결정 문제들을 포함

- NP-complete 

• 모든 다른 NP 문제를 다항 시간 내에 변환할 수 있는 문제 집합으로, 해결된 답을 다항 시간 내에 변환할 수 있는 문제 집합으로, 해결된 답을 다항 시간 내에 검증할 수 있는 문제들로 구성

- NP-hard

• NP에 속하는 모든 문제에 대해 polynomial time many one reducible 문제들의 집합

* NP-hard이면서 NP인 문제: NP-complete  (subset sum)

* NP-hard이면서 NP-complete가 아닌 문제 (halting problem)