P-NP 문제

P-NP 문제는 복잡도 종류 P 집합과 NP 집합이 같은지에 대한 컴퓨터 과학의 미해결 문제이다.

개요

P(PTIME 또는 DTIME)는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 집합이다. NP는 비결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제들의 집합으로, 이 문제들은 결정론적 튜링 기계로 다항 시간 안에 답을 검증할 수 있다. 즉 P는 NP의 부분집합이다. 그러나 P=NP인지, 즉 NP 역시 P의 부분집합인지는 아직 알려지지 않았다. 이에 대한 문제를 P-NP 문제라고 한다.

1971년 미국의 전산학자인 스티븐 쿡이 그의 논문 〈The Complexity of Theorem Proving Procedures>에서 처음 제안하였고, 그보다 더 전에는 1956년 수학자이자 논리학자인 쿠르트 괴델이 폰 노이만에게 썼던 편지에서 처음으로 언급되었다. 괴델은 어떤 NP 완전 문제가 2차 시간 혹은 선형 시간 안에 풀릴 수 있는지를 물었다.

밀레니엄 문제 중 하나이다.