왜 중요한가

P = NP 일 때와 P ≠ NP 일 때 암호, 최적화, 수학 증명 찾기, 기계 학습에서 무엇이 달라지는지를 문헌이 말하는 만큼만 정리한다. P = NP 가 곧 실용적인 알고리즘을 뜻하지는 않는다는 단서와, P ≠ NP 가 암호의 안전을 보장하지는 않는다는 단서를 함께 적는다.

확인과 발견 사이

P 대 NP 문제는 「답이 맞는지 확인하기 쉬운 문제는 답을 찾기도 쉬운가」를 묻는다. 확인은 쉬운데 찾기는 어려워 보이는 일은 어디에나 있다. 암호의 열쇠, 가장 싼 배송 경로, 정리의 증명, 데이터를 잘 설명하는 모형이 모두 그렇다. 그래서 이 문제의 답은 한 분야의 일로 끝나지 않는다.

다만 두 가지를 먼저 적어 둔다. 첫째, 어느 쪽인지 아직 모른다. 둘째, 아래의 「달라지는 것」은 대부분 조건이 붙은 이야기다.

연구자들은 어느 쪽이라고 보는가

Cook 의 공식 문제 기술은 복잡도 이론가 대부분이 P ≠ NP 라고 믿는다고 적는다. 수치로 볼 수 있는 근거는 Gasarch 가 연구자들에게 세 차례 물은 설문이다. P ≠ NP 라고 답한 사람은 2002년에 61명(61%), 2012년에 126명(83%), 2019년에 109명(88%)이었고, 2019년에 P = NP 라고 답한 사람은 15명(12%)이었다.

설문은 증거가 아니다. Aaronson 에 따르면 Knuth 처럼 P = NP 일 것이라고 밝힌 이름난 학자도 있다. 아래에서는 두 경우를 모두 살핀다.

P = NP 라면

그러니 아래는 「P = NP 이고, 실제로 빠른 알고리즘까지 손에 들어온다면」의 이야기다.

암호

인터넷의 암호는 인수분해 같은 문제가 어렵다는 가정 위에 서 있다. 대부분의 암호에서 열쇠를 찾는 일은 찾은 열쇠가 맞는지 쉽게 확인할 수 있는 문제, 곧 NP 에 속하는 탐색 문제이고, P = NP 이면 그 가정은 모두 거짓이 된다. Fortnow 는 이 경우 공개 키 암호가 불가능해진다고 적는다. Aaronson 은 예외로, 계산의 어려움에 기대지 않는 일회용 패드와 양자 열쇠 분배를 든다.

최적화

Cook 은 일정 짜기와 경로 정하기처럼 산업에서 중요한 많은 문제가 NP-완전 문제에서 나온다고 적는다. Fortnow 는 이런 최적화 문제들이 쉬워지면 사람과 물건을 옮기는 일정과 제조 공정이 훨씬 효율적으로 짜일 것이라고 내다본다.

수학 증명 찾기

형식 증명이 올바른지는 기계가 다항 시간에 검사할 수 있다. 그래서 「이 명제에 길이 n 이하의 증명이 있는가」는 NP 에 속하는 물음이다. Cook 은 NP-완전 문제를 푸는 실용적인 알고리즘이 있다면, 적당한 길이의 증명을 가진 정리는 컴퓨터가 형식 증명을 찾아낼 수 있게 되어 수학이 달라질 것이라고 적는다. 괴델이 1956년 편지에서 본 것이 바로 이 귀결이었다.

기계 학습

Fortnow 는 오컴의 면도날을 든다. 주어진 데이터와 맞아떨어지는 가장 작은 프로그램을 찾는 일이 쉬워지므로 학습 과제들이 쉬워진다는 것이다. 이것은 한 연구자의 전망이지 정리가 아니다.

P ≠ NP 라면

겉으로는 달라지는 것이 없다. 암호도 알고리즘 설계도 이미 그렇게 가정하고 이루어지고 있기 때문이다. Aaronson 도 P ≠ NP 의 증명에는 세상을 바꾸는 귀결이 없을 것이라고 적는다. 그래도 얻는 것은 있다.

• NP-완전 문제를 모든 입력에서 빠르게 푸는 방법은 없다는 것이 확정된다. 근삿값을 구하거나, 특수한 경우를 풀거나, 경험적 기법을 쓰는 지금의 길이 유일한 길이 된다.
• 증명 자체가 수확이다. Cook 이 정리한 대로 지금까지의 증명 기법은 이 문제에 닿지 못했다. Sipser 는 P ≠ NP 의 증명이 무엇이 문제를 어렵게 만드는지를 알려 줄 수 있으리라고 기대한다.

답이 나오기 전에 이미 준 것

이 문제는 풀리지 않은 채로도 쓸모가 있었다. NP-완전성 이론 덕분에, 어떤 문제가 NP-완전임을 알게 된 사람은 완벽한 알고리즘을 찾는 일을 멈추고 다른 길을 찾는다. Fortnow 는 DNA 조각들에 가장 잘 맞는 서열 찾기, 이징 모형의 바닥 상태 찾기, 단백질 스레딩(protein threading)에서 NP-완전 문제가 나온 예를 든다. Cook 은 이 문제의 중요성이 NP-완전성 이론과, 계산의 어려움에 기반한 암호 이론의 성공에서 온다고 적는다.

한눈에

출처

• Stephen Cook, "The P versus NP Problem", Clay Mathematics Institute 공식 문제 기술. https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf (2절: 암호와 수학 증명, n^100 의 예, P ≠ NP 이더라도 「대부분의」 입력에서 풀릴 가능성 · 3절: 연구자들의 믿음, 비구성적 증명의 가능성, 증명 기법의 한계)
• Lance Fortnow, "The Status of the P versus NP Problem", Communications of the ACM 52(9), 2009, 78–86. 저자 공개본: https://lance.fortnow.com/papers/files/pnp-cacm.pdf (3절 「What if P = NP?」, 7.1절 암호, 2절 NP-완전 문제의 예)
• Scott Aaronson, "P =? NP", 2017. https://www.scottaaronson.com/papers/pnp.pdf (1.1절: 암호와 예외, 과장에 대한 단서, P ≠ NP 증명의 귀결 · 3절: Knuth 의 견해)
• William I. Gasarch, "Guest Column: The Third P =? NP Poll", ACM SIGACT News 50(1), 2019, 38–59. 저자 공개본: https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf (2002·2012·2019년 설문 결과 표)
• Michael Sipser, "The History and Status of the P versus NP Question", Proc. 24th ACM STOC, 1992, 603–618. https://doi.org/10.1145/129712.129771 (1절: P ≠ NP 의 증명에 거는 기대 · 부록: 괴델의 편지)