P vs NP — 빠른 검증과 빠른 탐색은 같은가?

완성된 스도쿠 해답의 행·열·블록을 검사하는 일은 빠르다. 일반화된 스도쿠에서 해답을 찾는 최악의 경우도 그만큼 빠른지가 핵심이다. 여기서 “빠르다”는 한 문제를 몇 초에 푼다는 뜻이 아니라, 입력 크기 n에 대한 실행 시간이 어떤 다항식으로 제한된다는 이론적 뜻이다.

P=NP라면 모든 NP-완전 결정 문제에 다항 시간 알고리즘이 존재한다. 많은 최적화 문제와 암호 가정에 깊은 영향이 있지만, 지수가 큰 다항식일 수도 있어 모든 실제 문제가 즉시 쉬워진다는 뜻은 아니다. 반대로 P≠NP여도 휴리스틱·근사·특수 구조 덕분에 큰 실제 사례를 잘 푸는 경우가 많다.

연구자 다수는 P≠NP를 예상하지만 증명은 없다. 상대화·자연스러운 증명·대수화 같은 장벽 결과들은 익숙한 증명 기법만으로는 부족할 수 있음을 보여 준다. 질문 자체의 독립성이 증명된 것은 아니다. 2000년에 지정된 클레이 밀레니엄 문제로 남아 있다.