P 대 NP 문제의 여러 얼굴 — 같은 물음을 말하는 다른 방법들
P 대 NP 문제를 탐색, NP-완전 문제, 증명 찾기, 논리, 다항 위계, 회로, 증명 복잡도, 대수, 근사의 말로 다시 적어 보고, 각 진술이 P = NP 와 동치인지, 더 강하거나 약한 이웃인지, 닮은꼴일 뿐인지를 가른다.
화면·그림·수식 전수 점검(2026-10-07)으로 내용을 확인했습니다. 증명이 옳다는 뜻은 아닙니다.
P 대 NP 문제를 탐색, NP-완전 문제, 증명 찾기, 논리, 다항 위계, 회로, 증명 복잡도, 대수, 근사의 말로 다시 적어 보고, 각 진술이 P = NP 와 동치인지, 더 강하거나 약한 이웃인지, 닮은꼴일 뿐인지를 가른다.
한 문장이 아닌 문제
P 대 NP 문제는 「P = NP 인가」 한 줄로 적히지만, 같은 물음을 탐색, 증명, 논리, 회로의 말로 다시 적을 수 있다. 다시 적은 문장이 모두 같은 무게는 아니다. 어떤 것은 P = NP 와 정확히 같은 말이고, 어떤 것은 더 많은 것을 요구하며, 어떤 것은 닮았을 뿐이다. 이 글은 얼굴마다 그 관계를 네 낱말로 가른다.
- 동치
- 양쪽 방향이 모두 증명되어 있다. 하나가 풀리면 다른 하나도 풀린다.
- 더 강함
- 그 진술이 증명되면 P ≠ NP 가 따라 나오지만, 거꾸로는 알려져 있지 않다.
- 더 약함
- P ≠ NP 에서 따라 나오지만, 거꾸로는 알려져 있지 않다. P ≠ PSPACE 가 그런 예다.
- 닮은꼴
- 다른 계산 모델에서 세운 비슷한 물음이다. 같은 문제가 아니어서 한쪽의 답이 다른 쪽의 답을 그대로 주지 않는다.
P = NP 와 동치인 얼굴
1. 검증 대 탐색
「답을 다항 시간에 확인할 수 있으면 다항 시간에 찾을 수도 있는가.」 P 와 NP 는 예/아니오만 답하는 결정 문제로 정의되지만, 해를 찾는 문제로 바꿔 물어도 같은 물음이다.
P = NP 이면 NP 의 모든 언어와 그 검증자에 대해, 답이 「예」인 입력의 증거를 실제로 찾아내는 다항 시간 알고리즘이 있다(Arora–Barak 정리 2.19).
증명은 SAT 의 자기 환산성(self-reducibility)을 쓴다. 변수를 하나씩 고정하며 충족 가능성이 유지되는지를 물으면, 판정만 하는 알고리즘으로 대입을 찾을 수 있다. 거꾸로 증거를 찾을 수 있으면 증거가 있는지도 안다.
2. NP-완전 문제 하나
「SAT ∈ P 인가」, 「3색칠 ∈ P 인가」. NP-완전 문제 하나가 P 에 속하면 P = NP 이고(Cook 의 명제 1), 그 문제는 NP 에 속하므로 역은 당연하다. NP-완전 문제마다 얼굴이 하나씩 있다.
3. 증명 찾기
공리계를 정해 두고 「명제 φ 에 길이 n 이하의 형식 증명이 있는가」를 묻는다. 증명이 옳은지는 그 길이의 다항 시간에 검사되므로 이 문제는 NP 에 속하고, Arora–Barak 은 통상의 공리계에서 이것이 NP-완전이라고 적는다. 그래서 「짧은 증명이 있는 정리의 증명을 그 길이의 다항 시간에 찾을 수 있는가」는 둘째 얼굴의 한 사례이고 P = NP 와 동치다.
괴델의 1956년 편지는 이 얼굴의 원형이지만 글자 그대로는 더 좁은 물음이다. 괴델은 1차 술어 논리의 식 F 와 수 n 에 대해 길이 n 인 증명이 있는지 판정하는 기계를 두고, 가장 좋은 기계의 단계 수가 n 이나 n² 에 비례하는 정도일 가능성을 진지하게 보았다. Hartmanis 는 이를 NP-완전 문제가 선형이나 제곱 시간에 풀리는지를 물은 것으로 읽는다. 그런 기계가 있으면 P = NP 이지만, P = NP 라고 해서 n² 이 보장되지는 않는다.
4. 논리
서술 복잡도(descriptive complexity)는 성질을 판정하는 데 드는 시간 대신 그 성질을 적는 데 필요한 논리의 힘을 잰다.
Fagin 은 1974년에, 유한 구조의 성질이 NP 에 속하는 것과 존재 2차 논리의 식으로 적히는 것이 같음을 보였다.
존재 2차 논리의 식은 「이러한 관계들이 있다」로 시작하고 1차 논리식이 뒤따른다.
3색칠을 논리식으로
3색칠은 「꼭짓점의 집합 R, Y, B 가 있어서 모든 꼭짓점이 어느 하나에 들고, 이웃한 두 꼭짓점은 같은 집합에 함께 들지 않는다」로 적힌다.
P 쪽은 Immerman 과 Vardi 가 1982년에 독립적으로 밝혔다. 원소들에 순서가 주어진 유한 구조에서는, 1차 논리에 최소 고정점 연산자(귀납적 정의)를 더한 논리로 적히는 성질이 곧 다항 시간에 판정되는 성질이다.
둘을 합치면 P = NP 는 「순서 있는 유한 구조에서 2차 논리로 적히는 성질은 모두 최소 고정점을 더한 1차 논리로도 적힌다」와 동치다(Immerman 의 따름정리). 존재 2차 논리 대신 2차 논리 전체로 적어도 되는 것은, P = NP 이면 NP 가 여집합에 닫혀 둘의 표현력이 같아지기 때문이다. 기계도 시간도 나오지 않는 문장이다.
5. 다항 위계
다항 위계는 NP 와 coNP 위에 「어떤 y 가 있어 모든 z 에 대해 …」처럼 한정 기호가 번갈아 나오는 문제를 층층이 쌓은 것이다. 형식적 정의는 Stockmeyer 의 1976년 논문에서 왔다. P = NP 이면 위계 전체가 P 로 무너지고(Arora–Barak 정리 5.6), NP 가 위계의 첫 층이므로 역은 당연하다. 「다항 위계가 P 와 같은가」는 동치다. 다만 「위계의 모든 층이 서로 다르다」는 P ≠ NP 를 일반화한 더 강한 추측이다.
더 강한 이웃
6. 회로
그래서 NP ⊄ P/poly 를 보이면 P ≠ NP 가 따라 나온다. 역은 알려져 있지 않다. P ≠ NP 이면서 NP 의 문제에 작은 회로가 있을 가능성이 남아 있다.
역에 가장 가까운 결과가 Karp–Lipton 정리로, NP ⊆ P/poly 이면 다항 위계가 둘째 층으로 무너진다.
7. 증명 복잡도
P = NP 이면 NP = coNP 이므로 NP ≠ coNP 는 P ≠ NP 보다 강하다. 이 진술에도 고유한 얼굴이 있다.
Cook 과 Reckhow 는 1979년에, NP = coNP 인 것과 모든 항진식에 다항 길이의 증명을 주는 명제 증명 체계가 있는 것이 같음을 보였다.
「어느 증명 체계에나 짧은 증명이 없는 항진식이 있다」는 NP ≠ coNP 와 동치이고 P ≠ NP 보다 강하다.
닮은꼴, 그리고 얼굴이 아닌 것
8. 대수
Valiant 는 1979년에 덧셈과 곱셈으로 다항식을 계산하는 산술 회로 모델에서 P 와 NP 에 대응하는 VP 와 VNP 를 세우고, 퍼머넌트(permanent)가 VNP-완전임을 보였다(표수 2 인 체는 예외다).
VP ≠ VNP 추측은 n×n 퍼머넌트를 계산하는 산술 회로의 크기가 n 의 다항식을 넘는다는 것이다.
Aaronson 에 따르면 이는 퍼머넌트를 행렬식(determinant)으로 나타낼 때 필요한 행렬의 크기에 관한 추측과 거의 같은 말이다.
9. 근사
PCP 정리(NP = PCP(log n, 1))는 조건 없이 증명된 정리다.
여기서 다음이 나온다. 어떤 상수 ρ < 1 이 있어서, 3-SAT 꼴의 식에서 충족시킬 수 있는 절의 최대 개수의 ρ 배 이상을 언제나 충족시키는 대입을 다항 시간에 찾을 수 있으면 P = NP 다(Arora–Barak 따름정리 18.7). 「근사조차 NP-난해하다」는 말은 이 뜻이다. 근사할 수 없다는 결론은 P ≠ NP 를 가정해야 나오므로, 이것은 P 대 NP 의 다른 표현이 아니라 그 답에 딸린 귀결이다. 굳이 얼굴로 읽자면 둘째 얼굴의 목록이 근사 문제까지 늘어난 것이다.
한눈에
| 얼굴 | 진술 | 관계 |
|---|---|---|
| 1. 검증 대 탐색 | NP 문제의 증거를 다항 시간에 찾을 수 있다 | P = NP 와 동치 |
| 2. NP-완전 문제 하나 | SAT ∈ P, 3색칠 ∈ P 등 | P = NP 와 동치 |
| 3. 증명 찾기 | 길이 n 이하의 증명을 n 의 다항 시간에 찾을 수 있다 | P = NP 와 동치. 괴델의 원문(n, n² 시간)은 P = NP 보다 강함 |
| 4. 논리 | 순서 있는 유한 구조에서 2차 논리와 최소 고정점을 더한 1차 논리의 표현력이 같다 | P = NP 와 동치 |
| 5. 다항 위계 | 다항 위계가 P 와 같다 | P = NP 와 동치. 「모든 층이 다르다」는 P ≠ NP 보다 강함 |
| 6. 회로 | NP ⊄ P/poly | P ≠ NP 보다 강함 |
| 7. 증명 복잡도 | NP ≠ coNP | P ≠ NP 보다 강함 |
| 8. 대수 | VP ≠ VNP | 닮은꼴. NP ⊄ P/poly 에서 따라 나오는 쪽(표수 0 은 조건부) |
| 9. 근사 | 어떤 문제는 근사도 NP-난해 | 얼굴이 아님. P ≠ NP 를 가정한 귀결 |
| 견줌 | P ≠ PSPACE | P ≠ NP 보다 약함 |
얼굴이 여럿이라는 것의 쓸모
동치인 얼굴로 옮겨도 문제가 쉬워지지는 않는다. 어려움도 함께 옮겨 간다. 그래도 얼굴이 바뀌면 쓸 수 있는 도구가 바뀐다. Aaronson 은 서술 복잡도에 대해, 자원의 한계를 말하지 않고 클래스를 특징지으면 어느 것이 같고 다른지가 더 잘 보일지 모른다는 기대를 적고, Valiant 의 추측에는 대수기하의 도구를 쓸 수 있으리라는 기대를 적는다. 한 분야의 도구가 막히면 다른 얼굴에서 다시 시도할 수 있다. 2장 「주요 접근」의 회로 하한, 증명 복잡도, 기하적 복잡도 이론은 각각 여섯째, 일곱째, 여덟째 얼굴에서 출발한다.
출처
- Stephen Cook, "The P versus NP Problem", Clay Mathematics Institute 공식 문제 기술. https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf (명제 1, 탐색 문제와 SAT 의 대입 찾기, 합성수 판정과 인수분해, NP ≠ coNP 와 증명 체계)
- Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. 저자 공개 초고: https://theory.cs.princeton.edu/complexity/ (정리 2.19 와 자기 환산성 · 2.7.2절: 증명 길이 문제의 NP-완전성과 괴델의 물음 · 정리 5.6 과 5장 주석 · 정리 6.13 · 정리 18.2 와 따름정리 18.7)
- Scott Aaronson, "P =? NP", 2017. https://www.scottaaronson.com/papers/pnp.pdf (2.2.1절: 탐색·결정·최적화 · 2.2.3절: 다항 위계와 더 강한 추측들 · 5.2절: NP ⊄ P/poly 와 정리 26 · 6절 머리: 서술 복잡도 · 6.5.1절: Valiant 의 추측, 각주 77, Bürgisser 의 결과)
- Kurt Gödel, 폰 노이만에게 보낸 편지, 1956년 3월 20일. 영역은 Sipser 1992 의 부록(https://doi.org/10.1145/129712.129771). 이 글에서는 편지 본문을 R. J. Lipton, "The Gödel Letter", https://rjlipton.com/the-gdel-letter/ 에 실린 영역으로 확인했다
- Juris Hartmanis, "Gödel, von Neumann and the P=?NP Problem", Cornell University Computer Science Technical Report TR 89-994, 1989. https://ecommons.cornell.edu/handle/1813/6910 (초록과 4쪽: 괴델이 물은 문제의 성격)
- Ronald Fagin, "Generalized First-Order Spectra and Polynomial-Time Recognizable Sets", Complexity of Computation (R. M. Karp 엮음), SIAM–AMS Proceedings 7, 1974, 43–73. (본문은 열지 못해 정리의 진술은 Immerman 1995 로 확인)
- Neil Immerman, "Relational Queries Computable in Polynomial Time", Information and Control 68, 1986, 86–104. 저자 공개본: https://people.cs.umass.edu/~immerman/pub/query.pdf (정리 1 과 Vardi 의 독립 발견에 대한 서술)
- Moshe Y. Vardi, "The Complexity of Relational Query Languages", Proc. 14th ACM STOC, 1982, 137–146. https://doi.org/10.1145/800070.802186 (본문은 열지 못함)
- Neil Immerman, "Descriptive Complexity: a Logician's Approach to Computation", Notices of the American Mathematical Society 42(10), 1995, 1127–1133. 저자 공개본: https://people.cs.umass.edu/~immerman/pub/ams_notices.pdf (정리 1·3, 따름정리 4, 정리 12 · 3색칠의 식)
- Larry J. Stockmeyer, "The Polynomial-Time Hierarchy", Theoretical Computer Science 3(1), 1976, 1–22. https://doi.org/10.1016/0304-3975(76)90061-X (본문은 열지 못함)
- Richard M. Karp, Richard J. Lipton, "Some Connections between Nonuniform and Uniform Complexity Classes", Proc. 12th ACM STOC, 1980, 302–309. https://doi.org/10.1145/800141.804678 (본문은 열지 못해 정리의 진술은 Aaronson 과 Arora–Barak 으로 확인)
- Stephen A. Cook, Robert A. Reckhow, "The Relative Efficiency of Propositional Proof Systems", The Journal of Symbolic Logic 44(1), 1979, 36–50. 저자 공개본: https://www.cs.toronto.edu/~sacook/homepage/cook_reckhow.pdf (정의 1.3, 명제 1.1·1.4 와 그 뒤의 문단)
- Leslie G. Valiant, "Completeness Classes in Algebra", Proc. 11th ACM STOC, 1979, 249–261. https://doi.org/10.1145/800135.804419 (본문은 열지 못함)
- Peter Bürgisser, "Cook's versus Valiant's Hypothesis", Theoretical Computer Science 235(1), 2000, 71–88. https://doi.org/10.1016/S0304-3975(99)00183-8 (본문은 열지 못해 내용은 Aaronson 으로 확인)
- Peter Bürgisser, "Completeness classes in algebraic complexity theory", arXiv:2406.06217, 2024. https://arxiv.org/abs/2406.06217 (서론: Valiant 의 1979년 논문이 한 일, VP ≠ VNP 와 비균일 P ≠ NP 의 관계)
- S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, "Proof Verification and the Hardness of Approximation Problems", Journal of the ACM 45(3), 1998, 501–555. 저자 공개본: https://people.csail.mit.edu/madhu/papers/1992/almss-journ.pdf (초록)
출처·이용 조건: 직접 작성
참고문헌 17
- 원전원문 확인The P versus NP ProblemStephen Cook · 2000Clay Mathematics Institute, Millennium Prize Problems 공식 문제 기술 (12쪽 PDF · 문서에 날짜 표기 없음 · Cook 의 홈페이지 출판 목록에 따르면 2000년 4월 작성·11월 개정 원고 · 밀레니엄 상 문제는 2000년 5월 24일 발표 · 현재 공개본은 2004년 문헌까지 인용하므로 그 뒤에 손본 판)
Clay 수학연구소가 밀레니엄 상 문제로 내건 P 대 NP 문제의 공식 문제 기술이다. 문제의 정확한 진술, 역사와 중요성, 추측과 그것을 증명하려는 시도, 부록의 튜링 기계 정의로 이루어진 12쪽짜리 글이다. 「정확히 무엇을 증명해야 하는가」를 확인하려는 독자라면 누구나 가장 먼저 읽을 글이다.
확인:공식 PDF 12쪽 전체를 내려받아 읽고, 인용한 다섯 문장을 원문과 글자 단위로 대조함. - 교과서원문 확인Computational Complexity: A Modern ApproachSanjeev Arora, Boaz Barak · 2009Cambridge University Press, 2009
계산 복잡도 이론의 표준 교재로, 학부 고학년에서 대학원 입문 수준이다. P·NP 의 정의부터 회로 하한, 대화형 증명, PCP 정리, 탈무작위화, 자연 증명까지 이 서비스의 개념 대부분을 엄밀하게 다룬다. 정의와 증명을 제대로 공부하려는 독자에게 권한다. 연결한 것은 저자들이 운영하는 책 누리집으로, 초고와 정오표가 있다.
확인:출판본이 아니라 저자 공개 초고(2007년 1월판)의 해당 장·절을 읽음. - 개관원문 확인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년 판)을 열어 인용한 절들을 읽음. - 역사원문 확인Letter to John von Neumann (20 March 1956)Kurt Gödel · 1956독일어 손편지(프린스턴, 1956년 3월 20일) · 해설과 핵심 대목의 영문 번역: Juris Hartmanis, 「Gödel, von Neumann and the P=?NP Problem」, Cornell University Computer Science TR 89-994 (1989년 4월) = Bulletin of the EATCS (1989년 6월) 101–107쪽 · 전문 영문 번역: Sipser 1992 의 부록 (Arthur S. Wensinger 옮김)
괴델이 폰 노이만에게, 증명을 찾는 일을 기계가 얼마나 빨리 해낼 수 있는지 물은 편지다. P 대 NP 문제가 정식화되기 15년 전에 같은 물음의 핵심을 짚은 사료다. 연결한 Hartmanis 의 글(코넬 대학교 기술 보고서)은 편지가 쓰인 배경과 핵심 대목의 번역을 싣고 있고, 편지 전문의 영문 번역은 sipser-1992 의 부록에 있다. 문제의 역사에 관심 있는 모든 독자에게 권한다.
확인:독일어 손편지가 아니라 영문 번역(Sipser 1992 의 부록, Lipton 의 「The Gödel Letter」 페이지)을 읽음. - 보조 자료원문 확인The Gödel LetterRichard J. Lipton · 2026블로그 Gödel's Lost Letter and P=NP 의 고정 페이지 (2026-10-05 확인)
괴델이 폰 노이만에게 보낸 1956년 편지를 소개하는, Lipton 블로그의 고정 페이지다. 편지의 영문 번역이 실려 있다. 1-1 의 역사 글이 편지의 날짜와 장소를, 「여러 얼굴」 글이 편지 본문을 확인하는 데 썼다.
확인:2026-10-05 에 페이지를 직접 열어 편지 머리의 날짜·장소와 실린 영문 번역을 확인. - 역사원문 확인Gödel, von Neumann and the P=?NP ProblemJuris Hartmanis · 1989Cornell University, Department of Computer Science, Technical Report TR 89-994 (1989년 4월) · 「The Structural Complexity Column」 원고
괴델의 1956년 편지를 소개하고 그 물음을 P 대 NP 문제의 눈으로 읽은 Hartmanis 의 글이다. 괴델이 물은 것을 NP-완전 문제가 선형이나 제곱 시간에 풀리는지의 물음으로 읽는다. 1-1 의 「여러 얼굴」 글이 인용하며, godel-1956 카드가 연결하는 글이기도 하다. 코넬 대학 보존소의 스캔본으로 연결한다.
확인:코넬 대학 보존소의 스캔본을 열어 초록과 4쪽을 읽음. - 부분 결과서지만 확인Generalized First-Order Spectra and Polynomial-Time Recognizable SetsRonald Fagin · 1974R. M. Karp (ed.), Complexity of Computation, SIAM–AMS Proceedings 7, American Mathematical Society, 43–73쪽 (1974)
유한 구조의 성질이 NP 에 속하는 것과 존재 2차 논리의 식으로 적히는 것이 같음을 보인 논문이다. 기계도 시간도 쓰지 않고 NP 를 논리의 표현력으로 특징지은 Fagin 의 정리의 원전이다. 1-1 의 「여러 얼굴」 글이 인용한다. 논문 본문을 열지 못해, 정리를 소개하는 위키백과 문서로 연결한다.
확인:논문 본문은 열지 못함. 서지는 Immerman 1986 의 참고문헌과 위키백과 「Fagin's theorem」 문서로, 정리의 진술은 Immerman 1995 의 정리 1 로 확인. - 부분 결과원문 확인Relational Queries Computable in Polynomial TimeNeil Immerman · 1986Information and Control 68(1–3), 86–104쪽 (1986) · 예비판 STOC 1982 (Proceedings of the 14th Annual ACM Symposium on Theory of Computing), 147–152쪽
순서 있는 유한 구조에서, 1차 논리에 최소 고정점 연산자를 더한 논리로 적히는 성질이 곧 다항 시간에 판정되는 성질임을 보인 논문이다. Vardi 가 같은 정리를 독립적으로 얻었다(vardi-1982). Fagin 의 정리와 합치면 P = NP 를 논리의 표현력에 관한 문장으로 바꿔 적을 수 있다. 1-1 의 「여러 얼굴」 글이 인용한다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본을 열어 정리 1 과 Vardi 의 독립 발견에 관한 서술을 읽음. - 부분 결과서지만 확인The Complexity of Relational Query Languages (Extended Abstract)Moshe Y. Vardi · 1982STOC 1982 (Proceedings of the 14th Annual ACM Symposium on Theory of Computing), 137–146쪽
Immerman 과 독립적으로, 다항 시간에 판정되는 성질을 논리로 특징지은 결과가 실린 학회 논문이다. 1-1 의 「여러 얼굴」 글이 Immerman–Vardi 정리의 한쪽 원전으로 인용한다. ACM 디지털 도서관으로 연결된다.
확인:논문 본문은 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 같은 정리를 독립적으로 얻었다는 것은 Immerman 1986 의 서술로 확인. - 개관원문 확인Descriptive Complexity: a Logician's Approach to ComputationNeil Immerman · 1995Notices of the American Mathematical Society 42(10), 1127–1133쪽 (1995)
서술 복잡도를 수학자 일반 독자에게 소개한 Immerman 의 글이다. Fagin 의 정리, Immerman–Vardi 정리, 그리고 P = NP 를 논리의 표현력으로 바꿔 적은 따름정리를 정리한다. 1-1 의 「여러 얼굴」 글이 인용한다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본을 열어 정리 1·3, 따름정리 4, 정리 12 를 읽음. - 원전서지만 확인The Polynomial-Time HierarchyLarry J. Stockmeyer · 1976Theoretical Computer Science 3(1), 1–22쪽 (1976 · Arora–Barak 은 연도를 1977년으로 적는다)
다항 위계의 형식적 정의가 나온 논문이다. NP 와 coNP 위에 한정 기호가 번갈아 나오는 문제를 층층이 쌓은 위계를 다룬다. 1-1 의 「여러 얼굴」 글이 인용한다. 게시자(Elsevier) 페이지로 연결된다.
확인:논문 본문은 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 위계의 형식적 정의가 이 논문에서 왔다는 것은 Arora–Barak 공개 초고 5장의 주석으로 확인. - 부분 결과서지만 확인Some Connections between Nonuniform and Uniform Complexity ClassesRichard M. Karp, Richard J. Lipton · 1980STOC 1980 (Proceedings of the 12th Annual ACM Symposium on Theory of Computing), 302–309쪽
NP 가 다항 크기 회로를 가진다면 다항 위계가 둘째 층으로 무너짐을 보인 논문이다. NP ⊄ P/poly 와 P ≠ NP 를 잇는 가장 가까운 결과(Karp–Lipton 정리)의 원전이다. 1-1 의 「여러 얼굴」 글과 2-3 의 회로 하한 글이 인용한다.
확인:논문 본문은 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 정리의 진술은 Aaronson 2017 정리 26 과 Arora–Barak 공개 초고 정리 6.13 으로 확인. - 접근원문 확인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)을 읽음. - 접근서지만 확인Completeness Classes in AlgebraLeslie G. Valiant · 1979STOC 1979 (Proceedings of the 11th Annual ACM Symposium on Theory of Computing), 249–261쪽
산술 회로 모델에서 P 와 NP 에 대응하는 클래스(VP·VNP)를 세우고 퍼머넌트가 VNP-완전임을 보인 논문이다. VP ≠ VNP 추측(Valiant 의 추측)의 원전으로, P 대 NP 의 대수적 닮은꼴이다. 1-1 의 「여러 얼굴」 글이 인용한다. ACM 디지털 도서관으로 연결된다.
확인:논문 본문은 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Bürgisser 2024 의 개관과 Aaronson 2017 §6.5.1 로 확인. - 부분 결과서지만 확인Cook's versus Valiant's HypothesisPeter Bürgisser · 2000Theoretical Computer Science 235(1), 71–88쪽 (2000)
Valiant 의 추측이 틀리면 NP ⊆ P/poly 가 따라 나옴을 보인 논문이다(표수 0 인 체에서는 일반화 리만 가설을 가정한다). 퍼머넌트 대 행렬식 문제가 P 대 NP 의 「산술판 예행연습」으로 여겨지는 근거다. 1-1 의 「여러 얼굴」 글과 2-3 의 GCT 글이 인용한다.
확인:논문 본문은 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.5.1 로 확인. - 개관원문 확인Completeness classes in algebraic complexity theoryPeter Bürgisser · 2024arXiv:2406.06217 (2024년 6월 제출)
Valiant 의 1979년 논문이 연 대수적 완전성 클래스 이론을 정리한 개관이다. 서론이 Valiant 의 논문이 한 일과, VP ≠ VNP 추측이 비균일한 P ≠ NP 와 어떤 관계인지를 설명한다. 1-1 의 「여러 얼굴」 글이 인용한다. arXiv 공개본으로 연결한다.
확인:arXiv 공개본의 서론을 읽음. - 부분 결과원문 확인Proof verification and the hardness of approximation problemsSanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy · 1998Journal of the ACM 45(3), 501–555쪽 (1998) · 학회 발표 FOCS 1992 (33rd Annual Symposium on Foundations of Computer Science), 14–23쪽
NP 의 증명을 상수 개의 비트만 읽고 확률적으로 검증할 수 있음을 보여 PCP 정리를 완성한 논문이다. 그 귀결로, MAX-3SAT 같은 문제는 P ≠ NP 인 한 최적값에 얼마든지 가깝게 근사하는 다항 시간 방법을 가질 수 없음을 보인다. 근사 불가능성 이론의 원전을 찾는 독자에게 권한다. 공저자 Sudan 의 누리집에 있는 학술지판 공개본으로 연결한다.
확인:저자 공개본(학술지판)을 열어 초록을 읽음. 정리의 내용은 Arora–Barak 공개 초고 18장으로 확인.
하위 정보 0
이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.
아직 없습니다.