출처 - 위키
P-NP 문제는 복잡도 종류 P와 NP가 같은지에 대한 컴퓨터 과학의 큰 문제로 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻고 있다. 1971년 스티븐 쿡이 그의 논문 〈The Complexity of Theorem Proving Procedures〉(정리 증명 절차의 복잡성)에서 처음으로 제안하였고 클레이 수학연구소에서 발표한 7개의 밀레니엄 문제 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있다. 이것은 본래 1956년 쿠르트 괴델이 존 폰 노이만에게 썼던 편지에서 처음으로 언급되었다. 괴델은 어떤 NP 완전 문제가 2차 혹은 선형 시간 안에 풀릴 수 있는지 아닌지를 물었다.
P는 결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제류 이고, NP는 비결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제류 이다.여기에서 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분류가 된다.그리고 NP의 진부분격자가 됨을 세학자가 증명하였다.
[P=NP] vs [P!=NP] 에 관한 논쟁
NP-완전 문제가 하나라도 다항시간 안에 풀리면 P=NP가 되어 논쟁이 종료되지만... 아직까지 NP-완전 문제를 다항시간 안에 풀지 못했다.
