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

{{밀레니엄 문제}}

 

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

 

 

위에 사용된 일상적인 단어인 "빠르게"​는 [[다항 시간]]안에 실행되는 작업을 위한 알고리즘의 존재를 의미한다. 다항시간 안에 답을 제공하는 알고리즘이 있는 문제들의 일반 류 general class(종합적인 모임)를 P류 혹은 [[P (복잡도)|P]]라고 한다. 어떤 문제들은 빠르게 답을 찾을 수 있는 방법이 알려져 있지 않지만 답이 무엇인지를 나타내는 정보가 제공된다면 답을 빠르게 확인하는 것이 가능하다. 다항 시간 안에 확인할 수 있는 문제류를 [[NP (복잡도)|NP]]라고 한다.