개요

1

클래스 P란, 결정론적 튜링 기계에서 다항 시간에 판정 가능한 문제의 클래스이며, 클래스 NP는 Yes가 되는 증거(Witness라고 함)가 주어졌을 때 다항 시간에 Witness의 정당성 판정(이를 검증이라고 함)이 가능한 문제의 클래스이다. 다항 시간에 판정 가능한 문제는 다항 시간에 검증 가능하므로 P⊆NP인 것은 분명하지만, P가 NP의 진부분집합인지 여부에 대해서는 명확하지 않다. 아직 증명되지는 않았지만, 많은 연구자는 P≠NP라고 믿고 있다. 그리고 이 클래스 P와 클래스 NP가 같지 않다는 예상을 'P≠NP 예상'이라고 한다.