"쉬운 해법과 쉬운 검증의 차이"
P vs NP 문제는 21세기 수학의 7대 난제(밀레니엄 문제) 중 하나로, 상금이 무려 100만 달러입니다. 간단히 말해 "검산하기 쉬운 문제는 풀기도 쉬운가?"라는 질문입니다. 곱셈은 계산하기 쉽고 검산도 쉽지만(P 문제), 거대한 수의 소인수분해는 해답을 알면 검산은 쉽지만 그 해를 찾아내는 것은 매우 어렵습니다(NP 문제).
우리가 쓰는 인터넷 뱅킹과 암호화폐의 보안은 P≠NP라는 가정 위에 서 있습니다. 만약 누군가가 P=NP임을 증명한다면(즉, 어려운 문제도 쉽게 푸는 알고리즘을 발견한다면), 전 세계의 모든 암호 체계는 순식간에 무너질 것입니다.
이 문제는 컴퓨터가 할 수 있는 일의 한계를 묻는 것이기도 합니다. 외판원 문제(Traveling Salesman Problem)처럼 도시가 늘어날수록 계산량이 기하급수적으로 폭증하는 NP 문제가, 사실은 효율적인 지름길(P 문제)이 존재할까요? 대부분의 학자들은 '그렇지 않다(P≠NP)'고 믿지만, 아직 증명되지 않았습니다.