P-NP 문제

밀레니엄 문제
리만 가설	나비에-스토크스 방정식의 3차원 공간에서의 해의 존재와 매끄러움	버츠와 스위너톤-다이어 추측	양-밀스 가설의 존재와 질량 간극	호지 추측	P-NP 문제	푸엥카레 추측*
* 해결된 문제

P-NP 문제는 다항식 시간 복잡도 안에 풀 수 있는 문제(P 문제)와 다항식 시간 복잡도 안에 검증 가능한 문제(NP 문제)가 궁극적으로 동일한 문제인지 증명하는 문제이다.

P 문제 자체가 이미 NP 문제의 부분집합이므로 반대로 NP 문제가 P 문제의 부분집합인지 아닌지, 또는 답 자체가 없는지 확인할 수 있으면 해결되는 문제이기도 하다.