| NP 완전 문제 | 여러 가지 NP 완전문제 | NP-완전성과 변환성 |

NP-완전성과 변환성

  - Class P : 결정론적 알고리즘에 의해 다항식 시간에 풀 수 있는 모든 판정문제의 집합

  - Class NP : 비결정론적 알고리즘에 의해 다항식 시간에 풀 수 있는 모든 판정문제 집합 

  - P⊆ NP임은 자명한 사실이지만, P≠NP인지 아니면 P=NP인지는 컴퓨터 과학의 대표적인 미해결 문제로 남아 있다.

P≠NP일 때 문제의 관계

   다수의 연구자가 P≠NP일 것으로 믿고 있으나 아무도 이를 증명하지는 못하였다.
P≠NP라고 가정할 때, 문제 부류는 위 그림과 같이 나타낼 수 있다.

  ▶ 변환 : 문제 B에 대한 알고리즘으로 문제 A를 풀 수 있을 때 문제 A를 문제 B로 변환 할 수 있다고 말한다. 이러한 변환에 다항식 시간이 소요되면 다항식 시간 변환이라 하고 기호 '∝'로 나타낸다. 그림에서 판정문제 D1의 입력 I1을 문제 D2의 입력으로 변환하는 다항식 시간 함수 f가 존재하여, D1에 입력 I1이 주어졌을 때, 참일 필요충분 조건이 f(I1)이 D2에 주어져서 참이 된다면 D1을 D2로 다항식 시간 변환 가능하다고 한다. 따라서 D2를 다항식 시간에 풀 수 있다면 D1의 입력 I1을 D2의 입력 f(I1)으로 변환한 후 D2를 푸는 다항식 시간 프로시저를 써서 다항식 시간에 풀 수 있다. 이런 경우에 D1 ∝ D2이다.

 다항식의 곱이나 합은 다항식이므로 D1 ∝ D2, D2 ∝ D3이면 D1 ∝ D3 이다. 즉, 다항식 시간 변환을 몇 번 반복 적용하든 다항식 시간 복잡도는 여전히 다항식 시간으로 유지된다.