P-NP 문제: 두 판 사이의 차이

{{밀레니엄 문제}}

 

'''P-NP 문제'''는 [[복잡도 종류]] [[P (복잡도)|P]]와 [[NP (복잡도)|NP]]가 같은지에 대한 [[컴퓨터 과학]]의 미해결 문제로 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻고 있다. [[1971년]] [[스티븐 쿡]]이 그의 논문 〈The Complexity of Theorem Proving Procedures〉(정리 증명 절차의 복잡성)에서 처음으로 제안하였고 [[클레이 수학연구소]]에서 발표한 7개의 '밀레니엄 문제' 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있다. 이것은 본래 1956년 [[쿠르트 괴델]]이 [[존 폰 노이만]]에게 썼던 편지에서 처음으로 언급되었다. 괴델은 어떤 NP 완전 문제가 2차 혹은 선형 시간 안에 풀릴 수 있는지 아닌지를 물었다.