P-NP 문제 (P versus NP problem)
쉽게 풀면
어떤 문제는 답을 찾기는 어려워도 남이 제시한 답이 맞는지 확인하기는 쉬운 경우가 있다. 예를 들어 스도쿠를 처음부터 푸는 것은 오래 걸리지만, 완성된 답이 맞는지 확인하는 것은 금방이다. P-NP 문제는 '검증이 쉬운 모든 문제는 사실 풀기도 쉬운가'를 묻는다. 아직 아무도 증명하거나 반증하지 못한 상태이며, 만약 P=NP라면 암호학을 포함한 여러 분야가 근본적으로 바뀔 수 있다.
왜 중요한가
P-NP 문제는 컴퓨터과학 이론의 근간을 이루는 질문이자, 암호학·최적화·알고리즘 설계 등 실용적인 분야와도 직결되어 있어 논문에서 자주 언급됩니다. 어떤 문제가 NP-완전 또는 NP-난해로 밝혀지면, 그 문제를 다항 시간에 정확히 푸는 알고리즘을 찾으려 애쓰기보다 근사해나 휴리스틱 접근으로 방향을 트는 것이 합리적이라는 판단 근거가 되기 때문입니다. 또한 현재 널리 쓰이는 공개키 암호 체계들이 특정 계산 문제의 어려움에 의존하고 있어, P=NP 여부는 정보보안의 근본 전제와도 맞닿아 있습니다.
논문에서는 이렇게 쓰입니다
어떤 문제가 최적해를 다항 시간에 구하기 어렵다는 근거로 P-NP 문제의 미해결 상태를 인용할 때 쓰인다.
조합 최적화 연구에서 문제의 난이도를 증명한 뒤 근사적 해법으로 방향을 전환한 사례이다.
암호학 분야에서 P-NP 문제가 갖는 실용적 함의를 설명한 예문이다.
조금 더 깊게 보면
P-NP 문제를 이해하려면 NP-완전이라는 개념이 핵심인데, 이는 NP에 속한 모든 문제를 다항 시간 안에 환원시킬 수 있는, 다시 말해 NP 안에서 가장 어려운 문제들의 집합을 가리킵니다. 만약 NP-완전 문제 중 단 하나라도 다항 시간에 풀 수 있는 알고리즘이 발견된다면 P=NP가 증명되는 것이므로, 많은 연구자들이 특정 문제의 NP-완전성을 증명하는 방식으로 이 문제에 접근해 왔습니다. 실제로 외판원 문제, 배낭 문제, 그래프 색칠 문제 등 많은 실용적 문제들이 NP-완전 또는 NP-난해로 분류되어 있으며, 이런 문제들에 대해서는 정확해 대신 근사 알고리즘이나 휴리스틱 기법이 실무에서 널리 쓰입니다.
주의할 점
P=NP인지 P≠NP인지는 증명되지 않았으며, 대다수 학자는 P≠NP일 것이라 추측할 뿐 확정된 사실이 아니다.