개관 논문 길잡이

P 대 NP 문제를 더 깊이 읽으려는 사람을 위해 Sipser(1992), Fortnow(2009), Aaronson(2017)의 개관 논문과 Wigderson(2019), Arora–Barak(2009)의 책이 각각 무엇을 다루고 누구에게 맞는지, 어디서 읽을 수 있는지를 정리한다.

왜 개관 논문부터인가

P 대 NP 문제를 다루는 문헌은 많지만 전체 그림을 그려 주는 글은 손에 꼽힌다. 아래 다섯 문헌은 쓰인 때와 겨냥한 독자가 서로 달라서, 차례로 읽으면 1992년부터 2019년 사이에 무엇이 달라졌고 무엇이 그대로인지가 보인다. 주소는 이 글을 쓰면서 확인한 것만 적었다. 저자 공개본과 저자·출판사 페이지는 직접 열어 보았고, DOI 주소는 등록된 서지 정보로 확인했다.

Sipser (1992) — 역사와 1차 문헌

Michael Sipser 가 ACM 계산 이론 심포지엄(STOC)에서 발표한 「The History and Status of the P versus NP Question」이다. 저자는 문헌을 정리하되 기술적인 세부는 넣지 않았다고 밝힌다.

• 다루는 것: 문제의 의의, 역사(무차별 탐색, P 와 NP, 추측의 명시), 그리고 현황이다. 현황은 대각선 논법과 상대화, 독립성, 논리로의 표현, 제한된 체계, 회로 복잡도(깊이가 제한된 회로, 단조 회로) 순서로 정리된다.
• 눈여겨볼 곳: 부록이다. Shannon, von Neumann, Cobham, Edmonds, Rabin, Cook, Levin 의 글에서 뽑은 대목과, 괴델이 폰 노이만에게 보낸 1956년 편지의 영역과 자필 편지의 사진이 실려 있다.
• 한계: 1992년까지의 이야기다. 자연스러운 증명 같은 그 뒤의 결과는 없다.
• 읽을 곳: ACM Digital Library, https://doi.org/10.1145/129712.129771

Fortnow (2009) — 가장 짧은 입문

Lance Fortnow 가 Communications of the ACM 에 쓴 「The Status of the P versus NP Problem」이다. 첫머리에서 현황은 「Still open」 두 낱말이면 된다고 말한 뒤, 이 물음이 컴퓨터 과학과 그 바깥의 연구를 어떻게 이끌어 왔는지를 풀어 간다. 기술적·역사적으로 완전하려 하지 않고 비형식적으로 설명하겠다는 것이 저자의 말이다.

• 다루는 것: 문제의 뜻, P = NP 라면 벌어질 일, P ≠ NP 를 보이려는 접근(대각선 논법, 회로 복잡도, 증명 복잡도), 어려운 문제를 다루는 법(무차별 탐색, 매개변수 복잡도, 근사, 휴리스틱과 평균적인 경우), 대화형 증명과 근사의 한계, 어려움을 이용하는 암호, 양자 컴퓨터, 기하학적 복잡도 이론.
• 맞는 독자: 수식 없이 전체 지형을 보고 싶은 사람. 「NP-완전 문제를 만나면 실제로 어떻게 하는가」를 다루는 5절이 돋보인다.
• 읽을 곳: 저자 공개본 https://lance.fortnow.com/papers/files/pnp-cacm.pdf · 게재본 https://doi.org/10.1145/1562164.1562186
• 후속 글: 같은 잡지 65권 1호의 「Fifty Years of P vs. NP and the Possibility of the Impossible」(서지만 확인).

Aaronson (2017) — 증명 시도의 지도

Scott Aaronson 의 「P =? NP」는 수학자·과학자·공학자를 독자로 삼아 2017년 시점의 현황을 정리한 글이다. 단행본 『Open Problems in Mathematics』(Springer, 2016)에 실렸고, ECCC 보고서 TR17-004(2017년 1월)로도 공개되어 있다.

• 다루는 것: 문제의 중요성과 흔한 반론 일곱 가지에 대한 답, 형식 정의와 주변 개념, P ≠ NP 라고 믿는 까닭, 증명이 어려운 까닭, 추측의 강화판들, 그리고 본문의 절반을 넘는 6절 「Progress」다. 6절은 논리적 기법, 조합론적 하한, 산술화, 「아이러니한 복잡도 이론」, 산술 복잡도, 기하학적 복잡도 이론으로 나뉘고 상대화·자연스러운 증명·대수화라는 세 장벽을 설명한다.
• 맞는 독자: 「왜 아직 못 풀었는가」를 구체적으로 알고 싶은 사람. 1~4절은 중급, 6절은 전문 독자에게 맞는다.
• 읽을 곳: 저자 공개본 https://www.scottaaronson.com/papers/pnp.pdf · ECCC https://eccc.weizmann.ac.il/report/2017/004/

Wigderson (2019) — 계산 이론이라는 큰 그림

Avi Wigderson 의 책 『Mathematics and Computation: A Theory Revolutionizing Technology and Science』(Princeton University Press, 2019)는 개관 논문이 아니라 계산 복잡도 이론 전체의 개념 지도다.

• 다루는 것: 앞부분의 세 장 「Computational complexity 101: The basics, P, and NP」, 「Problems and classes inside (and around) NP」, 「Lower bounds, Boolean circuits, and attacks on P vs. NP」가 이 문제를 직접 다룬다. 이어서 증명 복잡도, 난수와 의사 난수, 대화형 증명, 양자 계산, 산술 복잡도, 암호, 학습 이론이 한 줄기로 엮인다.
• 맞는 독자: 증명의 세부보다 개념과 동기, 다른 수학 분야와의 연결을 알고 싶은 사람.
• 읽을 곳: 저자 페이지 https://www.math.ias.edu/avi/book 에 최종 초고가 있다. 저자는 개인의 연구와 교육 목적이라면 내려받아도 좋다고 적어 두었다.

Arora–Barak (2009) — 정의와 증명을 따라가는 교과서

Sanjeev Arora 와 Boaz Barak 의 『Computational Complexity: A Modern Approach』(Cambridge University Press, 2009)는 대학원 초년 수준의 교과서다. 출판사 소개에 따르면 수학적 성숙도 말고는 사전 지식을 요구하지 않고 연습 문제가 300개를 넘는다.

• 다루는 것: 공개 초고를 기준으로 1부 「기본 복잡도 클래스」가 계산 모델, NP 와 NP-완전성(Cook–Levin 정리의 증명 포함), 대각선 논법(시간 위계 정리, Ladner 정리, 상대화), 공간 복잡도, 회로, 확률 계산, 대화형 증명, 암호로 이어지고, 2부는 구체적인 계산 모델의 하한, 3부는 고급 주제다. 출판사 소개에 따르면 책 전체로는 양자 계산, 평균적인 경우의 복잡도, 탈난수화, PCP 정리까지 다룬다.
• 맞는 독자: 이 서비스의 「형식 정의」와 「NP-완전성」 글을 읽고 증명 전체를 보고 싶어진 사람.
• 읽을 곳: 저자 페이지 https://theory.cs.princeton.edu/complexity/ 에 초고가 있다(저자 허락 없이 복제·배포하지 말라는 문구가 붙어 있다). 출판사 페이지는 https://doi.org/10.1017/CBO9780511804090

읽는 순서

처음이라면

1. Fortnow
2. Cook 의 공식 문제 기술
3. Sipser 의 2절과 부록

정의부터 다지려면

1. Arora–Barak 의 1~3장을 읽고
2. Aaronson 의 1~4절로 넘어간다

연구 현황이 궁금하다면

1. Aaronson 의 6절을 읽고
2. 넓은 맥락은 Wigderson 에서 찾는다

NP-완전 문제의 목록이 필요하다면 Garey 와 Johnson 의 1979년 책이 지금도 표준 참고서로 꼽힌다.

출처

• 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
• Lance Fortnow, "The Status of the P versus NP Problem", Communications of the ACM 52(9), 2009, 78–86. https://doi.org/10.1145/1562164.1562186 · 저자 공개본 https://lance.fortnow.com/papers/files/pnp-cacm.pdf
• Scott Aaronson, "P =? NP", Open Problems in Mathematics, Springer, 2016, 1–122; ECCC TR17-004, 2017. https://www.scottaaronson.com/papers/pnp.pdf · https://eccc.weizmann.ac.il/report/2017/004/
• Avi Wigderson, Mathematics and Computation: A Theory Revolutionizing Technology and Science, Princeton University Press, 2019. https://www.math.ias.edu/avi/book
• Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. https://theory.cs.princeton.edu/complexity/
• Stephen Cook, "The P versus NP Problem", Clay Mathematics Institute. https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf
• Lance Fortnow, "Fifty Years of P vs. NP and the Possibility of the Impossible", Communications of the ACM 65(1), 76–85. https://doi.org/10.1145/3460351 (본문은 열지 못하고 서지만 확인)
• Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. (책은 열지 못함)