수학 7대 난제인 밀레니엄 문제 중에 하나
컴퓨터를 사용해서 문제를 풀 때 문제가 쉽게 풀리면 P 문제, 어렵게 풀리면 NP 문제다. 여기서 쉽냐 어렵냐의 기준은 보통은 시간이 얼마나 걸리냐를 기준으로 한다.
P-NP 문제는 이 쉽게 풀리는 P문제와 쉽게 풀리지 않는 NP 문제가 같은 집합인지 아닌지를 묻는 문제이다. 즉 P=NP라면 어렵게 풀리는 (시간이 오래 걸리는) 문제들도 쉽게 풀 수 있다(시간이 짧게 걸린다) 는 뜻이 되고 P≠NP 라면 그렇지 않다는 뜻이 된다.
언뜻 보면 당연히 P≠NP인게 맞는 것 같지만 진짜로 그런가는 아직도 증명이 안되었다. 할거 없으면 이런거 하나 증명해라. 100만달러 준다.