정의

쉽게 해답을 확인할 수 있는 문제(NP 문제)는 쉽게 풀 수도 있는 문제(P 문제)와 같은가?를 묻는 컴퓨터 과학 및 수학 분야의 미해결 난제입니다. 

간단히 말해, P와 NP라는 두 문제 집합이 서로 같은지(P = NP) 혹은 다른지(P ≠ NP)를 증명하는 문제입니다.

설명

이 문제는 계산의 근본적인 한계를 탐구합니다.

• P 문제 (다항 시간 문제): 일반적인 컴퓨터로 짧은 시간(다항 시간) 안에 해답을 찾을 수 있는 문제들의 집합입니다.
• NP 문제 (비결정론적 다항 시간 문제): 해답이 주어졌을 때, 그 해답이 맞는지(검증)를 짧은 시간(다항 시간) 안에 확인할 수 있는 문제들의 집합입니다.

쉽게 검산할 수 있는 모든 문제(NP)가 쉽게 풀 수도 있는 문제(P)와 같다는 명제가 바로 "P = NP"입니다. 현재 P 문제는 항상 NP 문제에 포함되지만(P는 NP의 부분 집합), 역이 성립하는지는 알 수 없습니다. 대부분의 전문가는 P와 NP가 다르다(P ≠ NP)고 추측하고 있습니다. 만약 P=NP가 증명된다면, 인류가 풀지 못했던 수많은 최적화 문제를 단숨에 풀 수 있게 됩니다.

용례

"현대 암호 시스템의 안전성은 PNP 추측이 P는 NP와 다르다는(P ≠ NP) 가정에 기반하고 있습니다. 만약 이 추측이 P = NP로 풀린다면, 현재 사용되는 복잡한 암호들도 쉽게 해독될 수 있어 전 세계의 보안 시스템에 근본적인 변화가 생길 것입니다."

이칭

• P-NP 문제
• P 대 NP 문제
• P 대 NP 난제

출처

• 클레이 수학 연구소 (Millennium Prize Problems), 스티븐 쿡 (Stephen Cook)의 1971년 논문
• https://www.claymath.org/millennium/p-vs-np/