공식 문제 기술 — Stephen Cook 의 「The P versus NP Problem」(Clay 수학연구소)

Clay 수학연구소가 밀레니엄 문제의 공식 기술로 실은 Stephen Cook 의 글 「The P versus NP Problem」을 절 순서대로 안내한다. 핵심 문장 다섯 곳만 원문과 우리말 옮김을 나란히 싣고, 나머지는 해설이다.

원문 PDF(영어, 12쪽) · Clay 수학연구소의 문제 페이지

원문

서지: Stephen Cook, "The P versus NP Problem". Clay 수학연구소(Clay Mathematics Institute)가 밀레니엄 문제(Millennium Prize Problems)의 공식 문제 기술(official problem description)로 내건 글이다.

글쓴이 Cook 은 이 문제를 처음 세운 사람 가운데 한 명이다. Clay 의 문제 페이지는 Cook 과 Leonid Levin 이 1971년에 서로 독립적으로 이 문제를 정식화했다고 적는다. Cook 의 홈페이지에 따르면 원고는 2000년 4월에 쓰였고 같은 해 11월에 고쳐졌다. 지금 배포되는 PDF 는 2004년 논문까지 인용하므로 그 뒤에 다시 손본 판이며, 같은 글이 단행본 『The Millennium Prize Problems』(2006) 87~104쪽에도 실려 있다.

한 문장으로 적은 문제

원문은 첫 문장에서 문제를 이렇게 적는다.

The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is also accepted by some (deterministic) algorithm in polynomial time.

P 대 NP 문제는, 어떤 비결정적(nondeterministic) 알고리즘이 다항 시간(polynomial time)에 받아들이는 모든 언어(language)가 어떤 (결정적(deterministic)) 알고리즘에 의해서도 다항 시간에 받아들여지는지를 판정하는 문제이다.

Stephen Cook, "The P versus NP Problem", 1절, 1쪽

낱말은 낯설어도 물음은 단순하다. 「답이 맞는지 빨리 확인할 수 있는 문제라면, 답도 빨리 찾을 수 있는가?」

그렇다고 「빠른 방법은 없다」가 증명된 것도 아니다. 확인과 발견 사이의 이 틈이 P 대 NP 문제다.

원문의 짜임

1절 — 문제를 정확히 적기

「빨리」와 「알고리즘」을 수학의 말로 옮기려면 계산 모델이 있어야 한다. 원문은 Alan Turing 이 1936년에 내놓은 튜링 기계(Turing machine)를 표준 모델로 삼고, 먼저 P 를 말로 소개한다.

Informally the class P is the class of decision problems solvable by some algorithm within a number of steps bounded by some fixed polynomial in the length of the input.

비형식적으로 말하면, 클래스 P 는 입력의 길이에 대한 어떤 고정된 다항식으로 한정되는 단계 수 안에 어떤 알고리즘으로 풀 수 있는 결정 문제(decision problem)들의 클래스이다.

같은 글, 1절, 1쪽

결정 문제는 답이 「예」 아니면 「아니오」인 문제다. 형식 정의에서는 문제를 문자열의 집합인 언어로 바꿔 놓는다. 답이 「예」인 입력을 모두 모은 집합이 그 문제의 언어다.

튜링 기계가 실제 컴퓨터보다 굼떠 보여도 정의는 흔들리지 않는다. 테이프가 여럿인 기계나 임의 접근 메모리를 가진 기계를 튜링 기계로 흉내 내도 시간은 제곱이나 세제곱 정도로만 늘어나므로, 어느 모델로 정의해도 P 는 같은 클래스가 된다고 원문은 짚는다.

NP 는 이름부터 오해를 사기 쉽다. 원문의 설명은 이렇다.

The notation NP stands for "nondeterministic polynomial time", since originally NP was defined in terms of nondeterministic machines (that is, machines that have more than one possible move from a given configuration).

NP 라는 표기는 "비결정적 다항 시간(nondeterministic polynomial time)"을 뜻하는데, 본래 NP 가 비결정적 기계(곧, 주어진 상황(configuration)에서 가능한 움직임이 둘 이상인 기계)로 정의되었기 때문이다.

같은 글, 1절, 2쪽

다만 원문은 오늘날의 관례를 따라 NP 를 「검사 관계(checking relation)」로 정의한다.

이제 문제는 한 줄로 적힌다.

Problem Statement. Does P = NP?

문제 진술. P = NP 인가?

같은 글, 1절, 2쪽

P ⊆ NP 는 쉽게 보인다. 증거 없이도 판정되는 언어라면 증거를 무시하는 검사 관계를 쓰면 된다. 물음은 반대 방향, 곧 NP 의 모든 언어가 P 에도 들어가는가이다. 원문은 합성수의 집합이 사실은 P 에도 속한다는 것이 최근에 밝혀졌다고 덧붙이는데, 그 근거가 Agrawal·Kayal·Saxena 의 논문 「PRIMES is in P」(2004)다.

2절 — 역사와 중요성

가장 긴 절이며 세 가지를 차례로 다룬다.

뿌리 — 계산 가능성 이론

첫째는 뿌리다. 1930년대의 계산 가능성(computability) 이론은 「결정 가능한 언어」와 「계산적으로 열거 가능한 언어」라는 두 부류를 다루었고, 정지 문제(Halting Problem)처럼 어떤 기계로도 판정할 수 없는 문제를 찾아냈다. 원문은 P 와 NP 를 이 두 부류의 다항 시간 판으로 소개한다. 한 문제를 다른 문제로 바꿔 푸는 환산(reduction), 한 부류에서 가장 어려운 문제를 가리키는 완전성(completeness)도 그 이론에서 건너온 개념이다.

실행 가능성 논제

둘째는 「다항 시간에 풀린다 = 현실에서 풀 수 있다」는 생각이다. 원문은 1960년대의 Cobham 과 Edmonds 를 출발점으로 들고 이 동일시를 「실행 가능성 논제(Feasibility Thesis)」라 부르면서, 단서도 함께 적는다. n¹⁰⁰ 단계가 드는 프로그램은 다항 시간이지만 n = 10 에서도 돌릴 수 없다. 반대쪽에서는 난수를 쓰는 알고리즘과 양자 컴퓨터(Shor 의 인수분해 알고리즘)가 「다항 시간이 아니면 못 푼다」는 방향을 흔들 수 있다.

NP-완전성

셋째가 NP-완전성(NP-completeness)이다. Cook 자신의 1971년 논문, 그 결과로 다른 스무 문제가 NP-완전임을 보인 Karp 의 논문, 독립적으로 같은 생각에 이른 Levin 의 논문이 소개되고, 핵심 사실이 명제로 정리된다.

예로는 충족 가능성 문제(Satisfiability)와 3-SAT, 부분집합의 합, 해밀턴 순환, 그래프 3색 칠하기가 나온다. 이어서 NP 언어의 여집합을 모은 coNP, 그리고 NP 에 속하지만 P 인지 NP-완전인지 알려지지 않은 문제(그래프 동형, 인수분해에 대응하는 언어)가 다뤄진다.

이 문제가 중요한 까닭

절의 끝은 이 문제가 중요한 까닭이다. 인터넷의 암호는 인수분해 같은 문제가 어렵다는 가정에 기대는데, P = NP 이면 그 가정은 모두 거짓이 된다. 한편 NP-완전 문제를 푸는 실용적인 알고리즘이 나온다면, 적당한 길이의 증명을 가진 정리는 컴퓨터가 형식 증명을 찾아낼 수 있게 되어 수학이 달라질 것이라고 원문은 말한다. 이 주제는 「왜 중요한가」 글에서 따로 살핀다.

3절 — 추측과 증명 시도

절은 이 문장으로 시작한다.

Most complexity theorists believe that P ≠ NP.

복잡도 이론가 대부분은 P ≠ NP 라고 믿는다.

같은 글, 3절, 7쪽

근거는 두 갈래로 제시된다. P = NP 를 보이려면 NP-완전 문제 하나의 다항 시간 알고리즘을 내놓으면 된다. 그런데 산업 현장의 필요 때문에 수많은 사람이 30년 동안 찾았어도 나오지 않았다. P ≠ NP 를 보이는 쪽에서는 두 방법이 시도되었다.

원문이 힘주어 말하는 것은 막힌 곳이 P 대 NP 하나가 아니라는 점이다. LOGSPACE ⊆ P ⊆ NP ⊆ PSPACE 에서 양 끝이 서로 다르다는 것은 증명되어 있다. 그런데 이웃한 두 클래스가 정말 다른지는 어느 자리에서도 증명하지 못했다. 절은 난수가 계산을 얼마나 돕는가 하는 물음(클래스 BPP)과 P 대 NP 사이의 뜻밖의 연결을 소개하며 끝난다.

부록 — 튜링 기계의 정의

마지막 두 쪽은 튜링 기계를 유한한 상태 집합, 테이프 알파벳, 전이 함수로 정의하고, 기계의 상황(configuration), 계산, 단계 수, 수락을 차례로 정한다. 1절의 정의가 딛고 선 바닥이다. 「형식 정의」 글이 같은 내용을 풀어 쓴다.

이 글의 범위

원문에서 그대로 옮긴 것은 위의 다섯 문장뿐이고 나머지는 이 서비스가 직접 쓴 해설이다. 전문 번역은 싣지 않았다. 해설에서 든 수치 예(221 = 13 × 17)는 원문에 없는 것이다.

출처

• Stephen Cook, "The P versus NP Problem", Clay Mathematics Institute 공식 문제 기술. https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf (인용 다섯 곳과 절 구성·쪽수의 근거)
• Clay Mathematics Institute, "P vs NP" 문제 페이지. https://www.claymath.org/millennium/p-vs-np/ (기숙사 배정 예, Cook 과 Levin 의 1971년 독립 정식화)
• Stephen A. Cook 홈페이지 출판 목록. https://www.cs.toronto.edu/~sacook/ (원고 작성 2000년 4월, 개정 2000년 11월)
• J. Carlson, A. Jaffe, A. Wiles (eds.), The Millennium Prize Problems, Clay Mathematics Institute / American Mathematical Society, 2006, 87~104쪽. https://www.claymath.org/library/monographs/MPPc.pdf (같은 글의 단행본 수록)
• M. Agrawal, N. Kayal, N. Saxena, "PRIMES is in P", Annals of Mathematics 160(2), 2004, 781–793. https://annals.math.princeton.edu/2004/160-2/p12