주요 접근의 지도 — P ≠ NP 로 가려던 여덟 갈래 길
대각선 논법, 회로 하한, 산술화, 증명 복잡도, 알고리즘에서 하한으로, 기하적 복잡도 이론, 메타복잡도, 평균적 복잡도까지 P ≠ NP 를 향한 주요 접근을 한 표로 정리하고, 각 접근의 핵심 생각·대표 결과·걸리는 장벽을 짚는다.
화면·그림·수식 전수 점검(2026-10-07)으로 내용을 확인했습니다. 증명이 옳다는 뜻은 아닙니다.
이 글은 P ≠ NP 를 향한 주요 접근 여덟 갈래 — 대각선 논법부터 평균적 복잡도까지 — 의 핵심 생각·대표 결과·걸리는 장벽을 한 표로 정리하고, 그 지도를 읽는 세 가지 눈을 제시한다.
한 장으로 보는 지도
P ≠ NP 를 증명하려는 시도는 몇 갈래의 큰 길로 묶인다. 아래 표는 이 장의 글들이 다루는 접근을 한눈에 정리한 것이다. 마지막 칸에는 세 장벽(상대화·자연 증명·대수화) 가운데 어느 것이 그 길을 막는지, 형식적인 장벽이 없다면 실제로 무엇이 발목을 잡는지를 적었다.
| 접근 | 핵심 생각 | 대표 결과 | 걸리는 장벽·한계 |
|---|---|---|---|
| 대각선 논법 | 다항 시간 기계를 하나씩 속이는 문제를 만든다 | 시간 계층 정리, P ≠ EXP | 상대화 |
| 회로 하한 | P ⊆ P/poly 이므로, NP 문제에 큰 회로가 필요함을 보이면 된다 | 패리티 ∉ AC⁰, AC⁰[p] 하한, 단조 회로의 클릭 하한 | 자연 증명. 일반 회로에 대한 하한은 3.1n 수준 |
| 산술화 | 논리식을 다항식으로 올리고 대각선 논법과 결합한다 | IP = PSPACE, MAEXP ⊄ P/poly | 대수화 |
| 증명 복잡도 | NP ≠ coNP 는 「어떤 증명 체계에도 짧은 증명이 없는 항진식이 있다」와 같다 | 분해(resolution) 체계의 지수 하한 | 형식적 장벽은 없으나, 프레게(Frege) 체계부터는 하한이 없다 |
| 알고리즘에서 하한으로 | 회로의 만족 가능성을 전수 탐색보다 조금 빨리 풀면 회로 하한이 나온다 | NEXP ⊄ ACC⁰, NQP ⊄ ACC⁰ | 알려진 장벽 없음. 큰 클래스와 작은 회로에 머문다 |
| 기하적 복잡도 이론 | 퍼머넌트 대 행렬식 문제를 궤도 폐포와 표현론의 문제로 옮긴다 | 가장 단순한 형태의 계획(출현 장애물)은 불가능함이 증명됨 | 알려진 장벽 없음. 필요한 수학이 매우 깊다 |
| 메타복잡도 | 「함수의 복잡도를 구하는 문제」의 복잡도를 묻는다 | 최악의 경우를 평균적 경우로 옮기는 환원, 일방향 함수의 특징짓기 | 최소 회로 크기 문제가 NP-난해인지가 미해결 |
| 평균적 복잡도 | 최악의 입력이 아니라 「대부분의 입력」에서의 어려움을 묻는다 | Levin 의 완전성 이론, Impagliazzo 의 다섯 세계 | P ≠ NP 보다 강한 명제들이 대상이다 |
지도를 읽는 세 가지 눈
첫째, 성공과 장벽이 짝을 이룬다. Aaronson 의 개관은 지금까지의 진전을 「하한과 장벽의 상호작용」으로 서술한다. 논리적 기법은 상대화에, 조합적 기법은 자연 증명에, 둘을 섞은 기법은 대수화에 걸렸다. 표의 위 세 줄이 그것이다. 아래 줄들은 그 뒤에 나온 길로, 장벽을 피하도록 설계되었거나 피할 수 있는지로 평가받는다.
둘째, 대부분 더 강한 명제를 겨냥한다. 회로 하한은 P ≠ NP 보다 강한 NP ⊄ P/poly 를, 증명 복잡도는 NP ≠ coNP 를, 암호와 닿아 있는 평균적 복잡도는 일방향 함수의 존재를 겨냥한다. 더 강한 명제를 노리는 까닭은 대상이 다루기 쉬워지기 때문이다. Sipser 의 설명으로는 회로는 정의가 단순해서 튜링 기계보다 조합적으로 분석하기 좋다. 다만 Aaronson 은 P ≠ NP 가 NP ⊄ P/poly 없이 증명될 가능성도 열어 둔다. P ≠ EXP 는 증명되었지만 EXP ⊄ P/poly 는 아직 증명되지 않았다는 것이 그 근거다.
셋째, 하한 증명과 알고리즘 설계가 만난다. 최근의 길들은 「불가능의 증명」을 「알고리즘의 발견」으로 바꾼다. Williams 의 방법은 더 빠른 만족 가능성 알고리즘을, 기하적 복잡도 이론은 표현론의 양을 계산하는 알고리즘을 찾는다. Aaronson 은 이런 흐름에 「아이러니한 복잡도 이론(ironic complexity theory)」이라는 이름을 붙였다.
표에 없는 길
이 표가 전부는 아니다. Aaronson 은 자신의 서술에서 빠진 길로 넷을 꼽는다. 복잡도 클래스를 논리의 표현력으로 특징짓는 서술 복잡도(descriptive complexity), 통신 복잡도로 회로 깊이를 재는 길(Karchmer–Wigderson), 무작위의 제거에서 회로 하한으로 가는 길(Kabanets–Impagliazzo), 행렬의 강성(rigidity) 같은 조합 문제다. 산술 회로의 하한(Valiant 의 추측)은 기하적 복잡도 이론 글에서 함께 다룬다.
이어지는 글
- 회로 하한: 제한된 회로에서의 성공과 일반 회로에서의 정체
- 기하적 복잡도 이론: 퍼머넌트 대 행렬식, 그리고 표현론
- 증명 복잡도: 짧은 증명이 없는 항진식 찾기
- 알고리즘에서 하한으로: Williams 의 방법
- 메타복잡도: 최소 회로 크기 문제와 콜모고로프 복잡도
- 평균적 복잡도와 다섯 세계
대각선 논법과 산술화는 장벽을 다룬 글(상대화, 대수화)에서 이미 살폈다.
어디까지 왔나
현황을 부풀릴 수는 없다. 어느 길도 P ≠ NP 에 가깝지 않다. Fortnow 는 2009년에 가까운 미래에 증명을 보리라고 믿을 이유가 거의 없다고 썼다. Aaronson 의 비유로는 P ≠ NP 가 먼 봉우리라면 지금까지의 진전은 모두 산기슭에 머물렀다. 그러나 산기슭을 오르는 일도 쉽지 않았고, 봉우리를 노리는 사람이라면 거기서 얻은 것부터 알아야 한다는 것이 그의 말이다.
출처
- S. Aaronson, "P =? NP", 저자 공개본(2017). §5.2(P/poly 와 P ≠ NP 의 관계), §6 머리말(하한과 장벽의 상호작용, 빠진 접근 넷, 산기슭 비유), §6.4·§6.6 을 확인.
- L. Fortnow, "The Status of the P versus NP Problem", Commun. ACM 52(9), 78–86 (2009). §1, §4 를 확인.
- M. Sipser, "The History and Status of the P versus NP Question", STOC 1992, 603–618. §3 을 확인.
- S. A. Cook, R. A. Reckhow, "The Relative Efficiency of Propositional Proof Systems", J. Symbolic Logic 44(1), 36–50 (1979). 명제 1.1·1.4 를 확인.
- R. Williams, "Nonuniform ACC Circuit Lower Bounds", J. ACM 61(1), 1–32 (2014). 초록을 확인.
- C. Murray, R. Williams, "Circuit Lower Bounds for Nondeterministic Quasi-Polytime", STOC 2018, 890–901. 초록을 확인.
- J. Li, T. Yang, "3.1n − o(n) Circuit Lower Bounds for Explicit Functions", STOC 2022, 1180–1193. 공개본(ECCC TR21-023)의 초록을 확인.
- P. Bürgisser, C. Ikenmeyer, G. Panova, "No Occurrence Obstructions in Geometric Complexity Theory", J. Amer. Math. Soc. 32(1), 163–193 (2019). 공개본(arXiv:1604.06431)의 초록을 확인.
- S. Hirahara, "Non-Black-Box Worst-Case to Average-Case Reductions within NP", FOCS 2018, 247–258. 공개본의 초록을 확인.
- Y. Liu, R. Pass, "On One-way Functions and Kolmogorov Complexity", FOCS 2020, 1243–1254. 공개본의 초록을 확인.
- R. Impagliazzo, "A Personal View of Average-Case Complexity", Structure in Complexity Theory Conference 1995, 134–147. 공개 사본에서 다섯 세계를 다룬 절을 확인.
출처·이용 조건: 직접 작성
참고문헌 11
- 개관원문 확인P =? NPScott Aaronson · 2017ECCC TR17-004 (2017년 1월 8일 공개) · 책 Open Problems in Mathematics (John Forbes Nash Jr., Michael Th. Rassias 엮음, Springer, 2016), 1–122쪽에 실린 글
P 대 NP 문제의 의미와 알려진 결과, 장벽, 접근 전반을 120여 쪽에 정리한 개관이다. 수학·과학·공학 배경의 넓은 독자를 겨냥해, 왜 P ≠ NP 라고 믿는지, 왜 증명이 어려운지, 지난 반세기에 무엇이 진전되었는지를 저자의 관점과 함께 설명한다. 상대화·자연 증명·대수화 장벽과 GCT 까지 다루므로, 이 서비스의 2부를 한 편으로 깊이 읽고 싶은 독자에게 가장 먼저 권한다.
확인:저자 공개본(2017년 판)을 열어 인용한 절들을 읽음. - 개관원문 확인The status of the P versus NP problemLance Fortnow · 2009Communications of the ACM 52(9), 78–86쪽 (2009)
P 대 NP 문제의 의미와 2009년 시점의 연구 상황을 전산학 일반 독자에게 풀어 쓴 개관이다. 문제를 풀려던 시도들과 그 한계, NP-완전 문제를 현실에서 다루는 법, 양자 컴퓨터의 가능성까지 짧게 훑는다. 수식이 거의 없어 입문 독자가 처음 읽을 영어 글로 알맞다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본을 열어 인용한 절들을 읽음. - 개관원문 확인The history and status of the P versus NP questionMichael Sipser · 1992STOC 1992 (Proceedings of the 24th Annual ACM Symposium on Theory of Computing), 603–618쪽
P 대 NP 문제의 뿌리와 1992년까지의 연구 상황을 정리한 개관 논문이다. 문제의 의의와 역사, 대각선 논법과 회로 복잡도(얕은 회로·단조 회로)로 이어진 시도들을 차례로 설명한다. 부록에는 괴델이 폰 노이만에게 보낸 편지 전문의 영문 번역이 실려 있다. 30여 년 전 글이지만 큰 그림을 잡으려는 입문·중급 독자에게 여전히 좋다. ACM 디지털 도서관으로 연결된다.
확인:공개 사본으로 본문과 부록(괴델 편지의 영문 번역 포함)을 읽음. 연결한 ACM 디지털 도서관 주소의 서지는 DOI 등록 기록으로 확인. - 접근원문 확인The relative efficiency of propositional proof systemsStephen A. Cook, Robert A. Reckhow · 1979The Journal of Symbolic Logic 44(1), 36–50쪽 (1979) · 예비판 「On the lengths of proofs in the propositional calculus」, STOC 1974, 135–148쪽
명제 증명 체계를 일반적으로 정의하고 증명 길이의 문제를 NP 대 coNP 문제와 이은 논문이다. 모든 항진식에 다항 길이의 증명을 주는 증명 체계가 있는 것과 NP = coNP 가 같은 말임을 보여 증명 복잡도라는 분야의 틀을 세웠다. 증명 복잡도 접근을 공부하려는 독자의 출발점이다. Cook 의 누리집에 있는 공개본으로 연결한다.
확인:저자 공개본을 열어 §1(명제 1.1·1.4, 정의 1.3·1.5)을 읽음. - 부분 결과원문 확인Nonuniform ACC Circuit Lower BoundsRyan Williams · 2014Journal of the ACM 61(1), 1–32쪽 (2014) · 학회 발표 CCC 2011 (26th Annual IEEE Conference on Computational Complexity), 115–125쪽
NEXP 의 문제 가운데 다항 크기 ACC⁰ 회로로는 풀 수 없는 것이 있음을 증명한 논문이다. 회로의 충족 가능성을 전수 조사보다 조금이라도 빨리 푸는 알고리즘을 만들면 회로 하한이 따라 나온다는 연결을 써서, 알고리즘 설계로 하한을 증명했다. 알려진 장벽들을 피한 드문 사례로 꼽힌다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본(2012-07-31 판)을 열어 초록, 서론, 정리 1.1·1.2 를 읽음. - 부분 결과원문 확인Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQPCody Murray, Ryan Williams · 2018STOC 2018 (Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing), 890–901쪽 · 학술지판 SIAM Journal on Computing 49(5) (2020) · ECCC TR17-188 (2017)
비결정적 준다항 시간에 풀리는 문제 가운데 다항 크기 ACC⁰ 회로로는 풀 수 없는 것이 있음을 증명한 논문이다. williams-2014 의 NEXP 를 훨씬 작은 종류로 낮춰, NP 에 대한 하한 쪽으로 한 걸음 다가선 결과다. ACC⁰ 하한이 지금 어디까지 왔는지 확인하려는 전문 독자에게 권한다. ECCC 공개본으로 연결한다.
확인:저자 공개본을 열어 초록과 서론을 읽음. - 부분 결과원문 확인3.1n − o(n) Circuit Lower Bounds for Explicit FunctionsJ. Li, T. Yang · 2022STOC 2022 (Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing), 1180–1193쪽 · ECCC TR21-023 (2021)
구체적인 함수에 대한 일반 회로 하한을 3.1n − o(n) 으로 올린 논문이다. 2-3 의 글들이 일반 회로 하한의 현황으로 드는 값이며, 하한이 여전히 선형 수준임을 보여 준다. 초록은 크기 10n 인 회로로 계산되지 않는 구체적인 함수가 있는지조차 모른다고 적는다. ECCC 공개본으로 연결한다.
확인:ECCC TR21-023 공개본의 초록과 서론을 읽음. - 접근원문 확인No Occurrence Obstructions in Geometric Complexity TheoryP. Bürgisser, C. Ikenmeyer, G. Panova · 2019Journal of the American Mathematical Society 32(1), 163–193쪽 (2019) · 학회 발표 FOCS 2016, 386–395쪽
기하적 복잡도 이론에서 출현 장애물만으로는 퍼머넌트와 행렬식을 분리할 수 없음을 증명한 논문이다. GCT 계획의 가장 단순한 형태가 불가능함을 보였지만, 일반적인 중복도 장애물까지 배제한 것은 아니라고 초록이 밝힌다. 2-3 의 접근 지도와 GCT 글이 인용한다. arXiv 공개본으로 연결한다.
확인:arXiv 공개본(1604.06431)의 초록과 서론을 읽음. - 부분 결과원문 확인Non-black-box worst-case to average-case reductions within NPShuichi Hirahara · 2018FOCS 2018 (59th Annual IEEE Symposium on Foundations of Computer Science), 247–258쪽 · ECCC TR18-138 (2018)
NP 안의 문제에 대해, 블랙박스 방식의 한계를 넘는 「최악의 경우에서 평균적 경우로」의 환산을 처음 제시한 논문이다. 시간 제한을 둔 콜모고로프 복잡도와 최소 회로 크기를 근사하는 문제가 평균적으로 쉽다면 최악의 경우에도 쉽다는 것을 보인다. 메타 복잡도 접근의 대표 성과로, 평균적 복잡도와 다섯 세계를 공부하는 전문 독자에게 권한다. ECCC 공개본으로 연결한다.
확인:ECCC 공개본(TR18-138)의 초록과 서론(§1.1)을 읽음. - 부분 결과원문 확인On One-way Functions and Kolmogorov ComplexityY. Liu, R. Pass · 2020FOCS 2020 (61st Annual IEEE Symposium on Foundations of Computer Science), 1243–1254쪽 · arXiv:2009.11514
일방향 함수의 존재와 시간 제한 콜모고로프 복잡도의 평균적 어려움이 동치임을 증명한 논문이다. 암호의 기초 가정이 잘 연구된 계산 문제 하나의 어려움으로 특징지어진 첫 사례다. 2-1 의 연표와 2-3 의 접근 지도·메타복잡도·평균적 복잡도 글이 인용한다. arXiv 공개본으로 연결한다.
확인:arXiv 공개본의 초록과 서론을 읽음. - 개관원문 확인A personal view of average-case complexityRussell Impagliazzo · 1995Proceedings of Structure in Complexity Theory, Tenth Annual IEEE Conference (1995), 134–147쪽
평균적 복잡도 연구를 정리하면서 「다섯 세계」라는 분류를 내놓은 글이다. P 대 NP 의 답과 암호의 가능성에 따라 세상이 어떻게 달라지는지를 다섯 가지 세계로 나눠 설명한다. 문제의 답이 현실에서 무슨 뜻인지 알고 싶은 독자에게 권한다. 주소는 저자가 올린 PostScript 파일이라 전용 보기 프로그램이 필요하다.
확인:공개 사본(PDF)에서 초록과 다섯 세계를 다룬 절 전체를 읽음. 서지는 DOI 등록 기록으로 확인.
하위 정보 0
이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.
아직 없습니다.