P vs NP 연표 — 1936년부터 지금까지

튜링 기계에서 메타복잡도까지, P vs NP 문제의 배경·정식화·증명 시도를 연도순으로 정리한다. 연도는 학회 발표와 학술지 게재를 구분해 적었다.

입문
관리자
2026-10-05 23:05
조회 0
AI 도움

검토 완료 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.

화면·그림·수식 전수 점검(2026-10-07)으로 내용을 확인했습니다. 증명이 옳다는 뜻은 아닙니다.

P vs NP 문제는 1971년에 정식화되었지만, 그 뿌리는 1930년대의 계산 이론에 있고 증명 시도는 지금도 이어진다. 이 연표는 그 흐름에서 갈림길이 된 사건을 연도순으로 추린 것이다.

이 연표를 읽는 법

각 항목은 연도, 누가, 무엇을 했는지, 그리고 그것이 왜 중요한지의 차례로 적었다.

연표

1936 (5월 접수·11월 발표, 권의 연도는 1937) · A. Turing

튜링 기계(Turing machine)를 정의하고, 기계적 절차로는 풀 수 없는 문제가 있음을 대각선 논법으로 보였다.

왜 중요한가 「알고리즘」과 「계산 단계 수」를 수학의 대상으로 만든 출발점이다. 여기서 쓴 대각선 논법은 뒤에 복잡도 이론의 기본 도구가 된다.
1956 (3월 20일 편지) · K. Gödel

폰 노이만에게 보낸 편지에서, 어떤 식에 길이 n 이하의 증명이 있는지 판정하는 기계의 단계 수가 n 이나 n² 에 비례하는 정도로만 늘 수 있는지 물었다.

왜 중요한가 정식화보다 15년 앞서 P vs NP 와 사실상 같은 물음을 던졌다. 편지는 1980년대 말에야 널리 알려졌다.
1965 (게재) · J. Hartmanis, R. Stearns

계산 단계 수로 문제의 어려움을 재는 틀을 세우고 시간 계층 정리(time hierarchy theorem)를 증명했다.

왜 중요한가 시간을 더 주면 더 많은 문제를 풀 수 있다는 것, 예컨대 P ≠ EXP 를 대각선 논법으로 얻는다.
1965 (Cobham: 1964 발표·논문집 간행, Edmonds: 1965 게재) · A. Cobham, J. Edmonds

다항 시간에 풀리는 문제들을 「현실적으로 풀 수 있는 문제」의 수학적 모형으로 제안했다. Edmonds 는 최대 매칭을 다항 시간에 푸는 알고리즘도 주었다.

왜 중요한가 클래스 P 의 뿌리다. 「전수 탐색을 피할 수 있는가」가 수학적 물음이 되었다.
1971 (STOC 발표, 5월) · S. Cook

NP 를 정의하고, NP 의 모든 문제가 명제 논리식의 만족 가능성 문제로 다항 시간에 환원됨을 보였다.

왜 중요한가 P vs NP 추측이 처음으로 정확히 정식화되었다. NP-완전성 이론의 시작이다.
1972 (논문집 게재) · R. Karp

클릭, 해밀턴 회로, 그래프 색칠 등 21개 조합 문제가 NP-완전임을 보였다.

왜 중요한가 NP-완전성이 드문 현상이 아니라 곳곳에 있음을 드러냈다.
1973 (게재) · L. Levin

소련에서 독립적으로 「보편 탐색 문제」를 정식화하고 완전 문제의 존재를 보였다.

왜 중요한가 같은 발견이 서로 모르는 채 두 곳에서 나왔다. 그래서 Cook–Levin 정리라 부른다.
1975 (1월 게재) · R. Ladner

P ≠ NP 라면, P 에 속하지도 않고 NP-완전도 아닌 NP 문제가 존재함을 보였다.

왜 중요한가 NP 가 「쉬운 것과 가장 어려운 것」 둘로만 나뉘지 않는다.
1975 (12월 게재) · T. Baker, J. Gill, R. Solovay

P^A = NP^A 인 오라클 A 와 P^B ≠ NP^B 인 오라클 B 가 모두 있음을 보였다.

왜 중요한가 첫 번째 장벽인 상대화(relativization). 대각선 논법만으로는 P vs NP 를 풀 수 없다.
1981–1986 (FSS: 1981 발표·1984 게재, Ajtai: 1983 게재, Yao: 1985 발표, Håstad: 1986 발표) · M. Furst·J. Saxe·M. Sipser, M. Ajtai, A. Yao, J. Håstad

패리티 함수는 깊이가 상수인 다항 크기 회로(AC⁰)로 계산할 수 없음을 보이고, 하한을 지수 크기까지 끌어올렸다.

왜 중요한가 제한된 회로에 대한 첫 강한 하한. 회로 복잡도로 P ≠ NP 에 다가가려는 계획의 출발이다.
1985 (게재) · A. Razborov

NOT 게이트가 없는 단조 회로로 클릭 문제를 풀려면 다항식보다 큰 크기가 필요함을 보였다.

왜 중요한가 NP-완전 문제에 대한 초다항 하한이 NOT 없는 모형에서 나왔다. 일반 회로로 넓히면 P ≠ NP 가 되지만, 그 길은 막혀 있음이 곧 밝혀졌다.
1987 (Razborov: 게재, Smolensky: STOC 발표) · A. Razborov, R. Smolensky

소수 p 로 나눈 나머지를 세는 게이트를 더한 회로 AC⁰[p] 에 대한 지수 하한을 증명했다.

왜 중요한가 다항식으로 회로를 근사하는 방법. 이 뒤로 회로 하한은 오래 제자리에 머문다.
1990–1992 (둘 다 FOCS 1990 발표·1992 게재) · C. Lund·L. Fortnow·H. Karloff·N. Nisan, A. Shamir

대화형 증명으로 검증할 수 있는 문제의 클래스가 다항 공간과 같음, 곧 IP = PSPACE 를 증명했다.

왜 중요한가 상대화하지 않는 증명 기법(산술화)이 실제로 있음을 보였다.
1992 (FOCS 발표·1998 게재) · S. Arora·S. Safra, S. Arora·C. Lund·R. Motwani·M. Sudan·M. Szegedy

PCP 정리: NP 의 모든 문제는 증명의 상수 개 비트만 무작위로 읽어 검사할 수 있는 증명을 가진다.

왜 중요한가 NP-완전 문제는 근사해조차 구하기 어렵다는 결과들의 토대다.
1994 (STOC 발표·1997 게재, 문헌에 따라 1993) · A. Razborov, S. Rudich

자연 증명(natural proofs): 그때까지의 회로 하한 기법은 강한 유사난수 생성기가 있다면 일반 회로에는 통할 수 없음을 보였다.

왜 중요한가 두 번째 장벽. 회로 하한이 왜 멈췄는지 설명한다.
2000 (5월 24일 파리 발표) · Clay 수학연구소

P vs NP 를 일곱 「밀레니엄 문제」의 하나로 정하고 문제마다 100만 달러의 상금을 걸었다.

왜 중요한가 전산학의 물음이 수학 전체의 대표 난제로 자리 잡았다.
2001 (게재) · K. Mulmuley, M. Sohoni

기하적 복잡도 이론(GCT)의 첫 논문. 하한 문제를 대수기하와 표현론의 문제로 옮기자고 제안했다.

왜 중요한가 알려진 장벽을 피하려는 장기 계획의 출발이다.
2002 (예비 논문 공개·2004 게재) · M. Agrawal, N. Kayal, N. Saxena

소수 판정이 다항 시간에 됨, 곧 PRIMES ∈ P 를 증명했다.

왜 중요한가 괴델의 편지에도 나오는 오래된 물음이다. 1970년대부터 무작위 알고리즘으로만 다항 시간에 풀 줄 알던 문제가 결정적 다항 시간으로 내려왔다.
2008 (STOC 발표·2009 게재) · S. Aaronson, A. Wigderson

대수화(algebrization): 산술화를 써도 P vs NP 는 풀 수 없음을 보였다.

왜 중요한가 세 번째 장벽.
2010 (8월 6일자 원고) · V. Deolalikar

P ≠ NP 를 증명했다고 주장하는 원고가 공개되었다. 공개 직후부터 연구자들이 온라인에서 함께 검토했고, 증명에 결함이 있다는 결론이 났다.

왜 중요한가 새 증명 주장이 나오면 「장벽을 어떻게 넘는가」, 「P 에 속한 문제에도 똑같이 적용되지 않는가」를 먼저 묻는다는 것을 보여 준 사례다.
2011 (학회 발표·2014 게재) · R. Williams

NEXP ⊄ ACC⁰ 를 증명했다. 회로의 만족 가능성을 전수 탐색보다 조금 빨리 푸는 알고리즘에서 회로 하한을 끌어냈다.

왜 중요한가 알려진 세 장벽을 모두 피한 하한으로 평가된다. 「알고리즘에서 하한으로」라는 길을 열었다.
2018 (STOC 발표) · C. Murray, R. Williams

같은 방법을 더 작은 클래스로 내려, 비결정적 준다항 시간 NQP 가 다항 크기 ACC⁰ 회로를 갖지 않음을 보였다.

왜 중요한가 하한의 대상이 NEXP 에서 NP 쪽으로 한 걸음 가까워졌다.
2018–2022 (모두 FOCS 발표) · S. Hirahara(2018·2022), Y. Liu·R. Pass(2020)

메타복잡도(meta-complexity)의 결과들: 최악의 경우를 평균적 경우로 옮기는 새 환원(2018), 일방향 함수의 존재와 시간 제한 콜모고로프 복잡도의 평균적 어려움이 동치임(2020), 부분 함수판 최소 회로 크기 문제가 무작위 환원 아래 NP-난해임(2022).

왜 중요한가 「어려움을 판정하는 문제의 어려움」이 암호, 평균적 복잡도, 회로 하한을 잇는 고리로 떠올랐다.

연표가 보여 주는 것

물음은 정식화보다 오래되었다. 괴델의 1956년 편지, Cobham 과 Edmonds 의 1960년대 논의에 이미 핵심이 들어 있다.
성공 뒤에 장벽이 왔다. 대각선 논법의 성공(1965) 뒤에 상대화(1975), 회로 하한의 성공(1981–1987) 뒤에 자연 증명(1994), 산술화의 성공(1990) 뒤에 대수화(2008)가 나왔다. 장벽은 실패의 기록이 아니라 「어떤 기법이 어디까지 가는가」에 대한 정리다.
문제는 아직 열려 있다. Fortnow 는 2009년 개관의 첫머리에 이 문제의 현황은 두 낱말, 「Still open.」으로 쓸 수 있다고 적었다. 그 뒤의 진전(2011, 2018, 메타복잡도)도 P ≠ NP 에서는 아직 멀리 있다.

1960년부터 2010년까지의 시간 축 위에 세 쌍의 화살표가 있다. 대각선 논법의 성공(1965)에서 상대화(1975)로, 회로 하한의 성공(1981–1987)에서 자연 증명(1994)으로, 산술화의 성공(1990)에서 대수화(2008)로 이어진다. — 성공 뒤에 장벽이 왔다 — 기법마다 성공한 해와 그 기법의 한계를 보인 장벽이 나온 해를 이었다.

출처

서지 사항은 원문·저자 공개본 또는 DOI 등록 정보(Crossref)·Math-Net.Ru 기록을 열어 확인했다. 각 결과의 내용은 원문을 열지 못한 경우 Sipser 1992, Fortnow 2009, Aaronson 2017 의 서술로 확인했다.

A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proc. London Math. Soc. (2) 42, 230–265. 접수·발표 날짜는 논문 첫 쪽에서 확인.
K. Gödel, 폰 노이만에게 보낸 편지(1956년 3월 20일). 영어 번역은 Sipser 1992 부록, 날짜는 R. J. Lipton 의 편지 소개 글에서 확인.
J. Hartmanis, R. E. Stearns, "On the Computational Complexity of Algorithms", Trans. AMS 117, 285–306 (1965).
A. Cobham, "The Intrinsic Computational Difficulty of Functions", Proc. 1964 International Congress for Logic, Methodology and Philosophy of Science, North-Holland, 24–30. 첫 쪽을 열어 확인. 간행 연도는 Sipser 1992 가 1964, Aaronson 2017 이 1965 로 적는다.
J. Edmonds, "Paths, Trees, and Flowers", Canadian J. Math. 17, 449–467 (1965).
S. A. Cook, "The Complexity of Theorem-Proving Procedures", STOC 1971, 151–158.
R. M. Karp, "Reducibility among Combinatorial Problems", Complexity of Computer Computations, Plenum, 85–103 (1972).
L. A. Levin, "Universal Sequential Search Problems", Probl. Peredachi Inf. 9(3), 115–116 (1973).
T. Baker, J. Gill, R. Solovay, "Relativizations of the P =? NP Question", SIAM J. Comput. 4(4), 431–442 (1975).
R. E. Ladner, "On the Structure of Polynomial Time Reducibility", J. ACM 22(1), 155–171 (1975).
M. Furst, J. B. Saxe, M. Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy", Math. Systems Theory 17(1), 13–27 (1984); FOCS 1981.
M. Ajtai, "Σ¹₁-Formulae on Finite Structures", Ann. Pure Appl. Logic 24(1), 1–48 (1983).
A. C.-C. Yao, "Separating the Polynomial-Time Hierarchy by Oracles", FOCS 1985, 1–10.
J. Håstad, "Almost Optimal Lower Bounds for Small Depth Circuits", STOC 1986, 6–20.
A. A. Razborov, "Lower Bounds on the Monotone Complexity of Some Boolean Functions", Dokl. Akad. Nauk SSSR 281(4), 798–801 (1985).
A. A. Razborov, "Lower Bounds on the Size of Bounded Depth Circuits over a Complete Basis with Logical Addition", Mat. Zametki 41(4), 598–607 (1987).
R. Smolensky, "Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity", STOC 1987, 77–82.
C. Lund, L. Fortnow, H. Karloff, N. Nisan, "Algebraic Methods for Interactive Proof Systems", J. ACM 39(4), 859–868 (1992); FOCS 1990.
A. Shamir, "IP = PSPACE", J. ACM 39(4), 869–877 (1992); FOCS 1990.
S. Arora, S. Safra, "Probabilistic Checking of Proofs: A New Characterization of NP", J. ACM 45(1), 70–122 (1998); FOCS 1992.
S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, "Proof Verification and the Hardness of Approximation Problems", J. ACM 45(3), 501–555 (1998); FOCS 1992.
A. A. Razborov, S. Rudich, "Natural Proofs", J. Comput. System Sci. 55(1), 24–35 (1997); STOC 1994. 저자 공개본을 열어 확인.
Clay Mathematics Institute, "P vs NP" (밀레니엄 문제 소개 페이지).
Wikipedia, "Millennium Prize Problems" (보조 자료: 2000년 5월 24일 파리 발표).
K. D. Mulmuley, M. Sohoni, "Geometric Complexity Theory I", SIAM J. Comput. 31(2), 496–526 (2001).
M. Agrawal, N. Kayal, N. Saxena, "PRIMES is in P", Ann. of Math. 160(2), 781–793 (2004).
S. Aaronson, A. Wigderson, "Algebrization: A New Barrier in Complexity Theory", ACM Trans. Comput. Theory 1(1) (2009); STOC 2008. 저자 공개본을 열어 확인.
V. Deolalikar, "P ≠ NP", 미출간 원고(2010년 8월 6일자). 보관된 사본의 표지를 열어 확인.
R. J. Lipton, "A Proof That P Is Not Equal To NP?", 블로그 Gödel's Lost Letter and P=NP, 2010년 8월 8일.
R. Williams, "Nonuniform ACC Circuit Lower Bounds", J. ACM 61(1), 1–32 (2014); CCC 2011. 저자 공개본을 열어 확인.
C. Murray, R. Williams, "Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP", STOC 2018, 890–901. 저자 공개본을 열어 확인.
S. Hirahara, "Non-Black-Box Worst-Case to Average-Case Reductions within NP", FOCS 2018, 247–258. 공개본(ECCC TR18-138)을 열어 확인.
Y. Liu, R. Pass, "On One-way Functions and Kolmogorov Complexity", FOCS 2020, 1243–1254. 공개본(arXiv:2009.11514)을 열어 확인.
S. Hirahara, "NP-Hardness of Learning Programs and Partial MCSP", FOCS 2022, 968–979. 공개본(ECCC TR22-119)을 열어 확인.
M. Sipser, "The History and Status of the P versus NP Question", STOC 1992, 603–618. 원문을 열어 확인.
L. Fortnow, "The Status of the P versus NP Problem", Commun. ACM 52(9), 78–86 (2009). 저자 공개본을 열어 확인.
S. Aaronson, "P =? NP", 저자 공개본(2017). 초판은 Open Problems in Mathematics (Springer, 2016), 1–122.

출처·이용 조건: 직접 작성

참고문헌 37

원전서지만 확인
On Computable Numbers, with an Application to the EntscheidungsproblemA. M. Turing · 1936Proceedings of the London Mathematical Society, Series 2, 42, 230–265쪽 (1936년 5월 28일 접수·11월 12일 발표, 권의 간행 연도 1937)
튜링 기계를 정의하고, 기계적 절차로는 풀 수 없는 문제가 있음을 대각선 논법으로 보인 논문이다. 「알고리즘」과 「계산 단계 수」를 수학의 대상으로 만든 출발점으로, 2-1 의 연표가 첫 항목으로 싣는다.
확인:논문 첫 쪽에서 접수·발표 날짜를 확인. 본문을 읽었다는 기록은 없음.
원문 주소 (doi.org)DOI 10.1112/plms/s2-42.1.230
역사원문 확인
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」 페이지)을 읽음.
원문 주소 (ecommons.cornell.edu)
원전원문 확인
On the computational complexity of algorithmsJuris Hartmanis, Richard E. Stearns · 1965Transactions of the American Mathematical Society 117 (1965), 285–306쪽
계산에 드는 시간으로 문제를 분류하는 틀을 세우고 시간 위계 정리를 증명한 논문이다. 「계산 복잡도」라는 분야가 여기서 시작되었다. 대각선 논법으로 복잡도 종류를 가르는 방법의 뿌리를 보려는 독자에게 권한다. 미국수학회 누리집에 PDF 가 올라 있다.
확인:미국수학회 누리집의 공개 PDF 를 열어 정리 6·정리 9 와 그 증명 요약을 읽음.
원문 주소 (www.ams.org)
원전서지만 확인
The Intrinsic Computational Difficulty of FunctionsAlan Cobham · 1964Proceedings of the 1964 International Congress for Logic, Methodology and Philosophy of Science, North-Holland, 24–30쪽 (1964년 학회 발표 · 논문집 간행 연도는 문헌에 따라 1964 또는 1965 — Sipser 1992 는 1964, Aaronson 2017 은 1965 로 적는다)
덧셈과 곱셈처럼 단계 수가 자릿수의 다항식으로 한정되는 함수들을 따로 다루자고 제안해, 다항 시간이라는 기준의 뿌리가 된 글이다. Edmonds 의 1965년 논문과 함께 클래스 P 의 출발점으로 꼽힌다. 1-1 의 역사 글과 2-1 의 연표가 인용한다. 연결한 것은 Stephen Cook 의 누리집에 있는 사본이다.
확인:Cook 누리집의 공개 사본을 열어 첫 쪽을 확인. 본문을 읽었다는 기록이 분명하지 않아 서지 확인으로 둠.
원문 주소 (www.cs.toronto.edu)
원전서지만 확인
Paths, Trees, and FlowersJack Edmonds · 1965Canadian Journal of Mathematics 17, 449–467쪽 (1965)
그래프의 최대 매칭을 찾는 알고리즘을 내놓으면서, 수고가 다항식 정도로만 늘어나는 「좋은」 알고리즘이 있는지가 뜻있는 물음이라고 논한 논문이다. Cobham 의 글과 함께, 다항 시간을 「현실적으로 풀 수 있음」의 기준으로 삼는 생각의 출발점이다. 1-1 의 역사 글과 2-1 의 연표가 인용한다.
확인:서지는 DOI 등록 기록으로 확인. 본문은 Sipser 1992 의 부록에 실린 발췌로만 확인.
원문 주소 (doi.org)DOI 10.4153/cjm-1965-045-4
원전원문 확인
The complexity of theorem-proving proceduresStephen A. Cook · 1971STOC 1971 (Proceedings of the 3rd Annual ACM Symposium on Theory of Computing), 151–158쪽
NP 의 모든 문제가 명제 논리식의 판정 문제로 환산됨을 보여 NP-완전 이론을 연 논문이다. 8쪽짜리 학회 논문으로, 다항 시간 환산의 개념과 오늘날 「SAT 는 NP-완전」이라 부르는 결과가 여기서 나온다. 용어와 표기(항진식 판정, 오라클을 쓰는 환산)가 지금과 달라서, 교과서로 개념을 익힌 뒤 원전을 확인하려는 독자에게 맞다. 연결한 것은 저자 누리집의 스캔본이다.
확인:저자 누리집의 스캔본을 열어 요약 부분을 읽음.
원문 주소 (www.cs.toronto.edu)
원전서지만 확인
Reducibility among Combinatorial ProblemsRichard M. Karp · 1972Complexity of Computer Computations (R. E. Miller, J. W. Thatcher, J. D. Bohlinger 엮음, Plenum Press, 1972), 85–103쪽
서로 달라 보이는 조합 문제 21개가 모두 NP-완전임을 환산의 사슬로 보인 논문이다. 쿡의 결과가 한 문제에 그치지 않고 조합 최적화 전반에 걸친 현상임을 드러내 NP-완전성을 널리 알렸다. 클릭·정점 덮개·해밀턴 순환·배낭 문제 등으로 가는 환산을 직접 보고 싶은 독자에게 좋다. 게시자(Springer) 페이지이며 본문 열람에는 구독이 필요할 수 있다.
확인:게시자 페이지와 DOI 등록 기록으로 서지를 확인. 1-1 의 NP-완전성 글은 주정리의 21문제 목록과 환산 그림을 이 논문에서 가져왔다고 적었으나, 본문을 어디서 열었는지는 기록에 없어 서지 확인으로 둠.
원문 주소 (link.springer.com)
원전서지만 확인
Universal sequential search problemsLeonid A. Levin · 1973Problemy Peredachi Informatsii 9(3), 115–116쪽 (1973, 러시아어) · 영문 번역 Problems of Information Transmission 9(3), 265–266쪽
쿡과 독립적으로, 여러 탐색 문제가 그런 종류의 문제 전체만큼 어려운 「보편」 문제임을 밝힌 두 쪽짜리 논문이다. 소련에서 러시아어로 발표된, 쿡–레빈 정리의 또 한쪽 원전이다. 내용보다 역사적 맥락을 확인하려는 독자에게 권한다. 연결한 Math-Net.Ru 페이지에 서지 사항과 러시아어 원문 PDF 가 있다.
확인:Math-Net.Ru 의 서지·초록 페이지에서 접수일과 게재 서지를 확인. 러시아어 본문은 읽지 않았고 내용은 Cook 의 공식 문제 기술의 설명에 기댐.
원문 주소 (www.mathnet.ru)
장벽서지만 확인
Relativizations of the P =? NP QuestionTheodore Baker, John Gill, Robert Solovay · 1975SIAM Journal on Computing 4(4), 431–442쪽 (1975)
P = NP 가 되는 오라클과 P ≠ NP 가 되는 오라클이 모두 있음을 보인, 상대화 장벽의 원전이다. 대각선 논법처럼 상대화되는 기법만으로는 P 대 NP 를 어느 쪽으로도 풀 수 없다는 첫째 장벽이 이 논문에서 나온다. 2-2 를 읽고 원문을 확인하려는 독자에게 권한다. SIAM 페이지로 연결되며 본문 열람에는 구독이 필요할 수 있다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Arora–Barak 공개 초고 정리 3.9 와 Aaronson 2017 정리 43 으로 확인.
원문 주소 (doi.org)DOI 10.1137/0204037
부분 결과서지만 확인
On the Structure of Polynomial Time ReducibilityRichard E. Ladner · 1975Journal of the ACM 22(1), 155–171쪽 (1975)
P ≠ NP 라면 P 에도 속하지 않고 NP-완전도 아닌 NP 문제가 반드시 있음을 증명한 논문이다. NP-중간이라는 개념의 근거가 되는 정리의 원전이다. 복잡도 이론 교과서에서 래드너의 정리를 먼저 읽고 원문을 찾는 독자에게 맞다. ACM 디지털 도서관으로 연결된다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 정리의 진술은 Aaronson 2017 정리 5 와 Arora–Barak 공개 초고 정리 3.4 로 확인.
원문 주소 (doi.org)DOI 10.1145/321864.321877
부분 결과서지만 확인
Parity, circuits, and the polynomial-time hierarchyMerrick Furst, James B. Saxe, Michael Sipser · 1984Mathematical Systems Theory 17(1), 13–27쪽 (1984) · 학회 발표 FOCS 1981 (22nd Annual Symposium on Foundations of Computer Science), 260–270쪽
깊이가 상수인 회로로는 패리티 함수를 다항 크기에 계산할 수 없음을 보인 논문이다. 제한된 회로 모형에서 구체적인 함수의 하한을 얻은 초기 대표 결과이며, 회로 하한과 다항 위계의 오라클 분리 사이의 연결도 다룬다. 회로 복잡도 접근이 어디서 출발했는지 보려는 독자에게 권한다.
확인:원문은 열지 못함. 서지는 게시자 페이지와 Crossref 의 DOI 등록 기록으로, 내용은 Sipser 1992·Aaronson 2017·Håstad 학위 논문 1장으로 확인.
원문 주소 (link.springer.com)
부분 결과서지만 확인
Σ¹₁-Formulae on Finite StructuresM. Ajtai · 1983Annals of Pure and Applied Logic 24(1), 1–48쪽 (1983)
Furst–Saxe–Sipser 와 독립적으로, 상수 깊이·다항 크기 회로가 패리티를 계산하지 못한다는 결론에 이른 논문이다. PARITY ∉ AC⁰ 의 두 원전 가운데 하나다. 2-1 의 연표, 2-3 의 회로 하한 글, 2-4 의 PARITY ∉ AC⁰ 글이 인용한다. 게시자(Elsevier) 페이지로 연결된다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Håstad 학위 논문 1장과 Aaronson 2017 로 확인.
원문 주소 (doi.org)DOI 10.1016/0168-0072(83)90038-6
부분 결과서지만 확인
Separating the Polynomial-Time Hierarchy by OraclesA. C.-C. Yao · 1985FOCS 1985 (26th Annual Symposium on Foundations of Computer Science), 1–10쪽
Furst–Saxe–Sipser 와 Ajtai 의 패리티 하한을 지수 크기로 끌어올린 논문이다. Håstad 가 이듬해 이를 거의 최적의 하한으로 다듬었다. 2-1 의 연표와 2-4 의 PARITY ∉ AC⁰ 글이 인용한다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Håstad 학위 논문 1장과 Williams 2014 서론으로 확인.
원문 주소 (doi.org)DOI 10.1109/sfcs.1985.49
부분 결과서지만 확인
Almost optimal lower bounds for small depth circuitsJohan Håstad · 1986STOC 1986 (Proceedings of the 18th Annual ACM Symposium on Theory of Computing), 6–20쪽 · 확장판 Randomness and Computation (Advances in Computing Research 5, S. Micali 엮음, JAI Press, 1989), 143–170쪽
상수 깊이 회로가 패리티를 계산하려면 지수에 가까운 크기가 필요함을 보인 논문이다. 무작위로 변수 일부를 고정하면 「작은 OR 들의 AND」를 「작은 AND 들의 OR」로 바꿀 수 있다는 핵심 보조정리(전환 보조정리)가 여기서 나온다. 깊이 k 에서는 다항 크기로 되지만 깊이 k−1 에서는 지수 크기가 필요한 함수가 있음도 보인다. 회로 하한 기법을 직접 배우려는 독자에게 권한다.
확인:저자 공개본 주소를 열어 제목·저자·실린 곳을 확인했으나 본문을 읽었다는 기록은 없음. 내용은 Håstad 학위 논문 1장, Aaronson 2017, Arora–Barak 공개 초고 13장으로 확인.
원문 주소 (www.csc.kth.se)
부분 결과원문 확인
Lower bounds on the monotone complexity of some Boolean functionsAlexander A. Razborov · 1985Doklady Akademii Nauk SSSR 281(4), 798–801쪽 (1985, 러시아어) · 영문 번역 Soviet Mathematics Doklady 31, 354–357쪽 (1985)
NOT 을 쓰지 않는 단조 회로로는 클릭 문제를 다항 크기에 풀 수 없음을 증명한 논문이다. NP-완전 문제에 대한 초다항 회로 하한을 (단조 회로라는 제한 아래) 처음 얻어 큰 기대를 모았다. 다만 이 방법은 일반 회로로 넓혀지지 않았다. 연결한 것은 저자가 올린 영문 번역본이며, 러시아어 원문의 서지는 Math-Net.Ru(mathnet.ru/eng/dan9192)에 있다.
확인:저자 누리집의 영문 번역본을 열어 정리 2·정리 3 과 그 설명을 읽음. 러시아어 원문의 서지는 Math-Net.Ru 로 확인.
원문 주소 (people.cs.uchicago.edu)
부분 결과서지만 확인
Lower bounds on the size of bounded depth circuits over a complete basis with logical additionA. A. Razborov · 1987Matematicheskie Zametki 41(4), 598–607쪽 (1987, 러시아어) · 영문 번역 Mathematical Notes of the Academy of Sciences of the USSR 41(4), 333–338쪽 (https://doi.org/10.1007/BF01137685)
MOD-2 게이트를 허용한 상수 깊이 회로가 다수결을 계산하려면 지수 크기가 듦을 보인 논문이다. 회로를 차수 낮은 다항식으로 근사하는 다항식 방법의 출발점으로, Smolensky 가 이를 일반 소수로 넓혔다. 2-1 의 연표, 2-3 의 회로 하한 글, 2-4 의 PARITY ∉ AC⁰ 글이 인용한다. 연결한 Math-Net.Ru 페이지에 러시아어 원문의 서지가 있다.
확인:Math-Net.Ru 의 서지 페이지와 영문 번역의 DOI 등록 기록으로 서지를 확인. 내용은 Williams 2014 서론과 Aaronson 2017 로 확인.
원문 주소 (www.mathnet.ru)
부분 결과서지만 확인
Algebraic methods in the theory of lower bounds for Boolean circuit complexityRoman Smolensky · 1987STOC 1987 (Proceedings of the 19th Annual ACM Symposium on Theory of Computing), 77–82쪽
나머지 세기(MOD p) 게이트를 더한 상수 깊이 회로에 대해 대수적 방법으로 하한을 증명한 논문이다. 회로를 낮은 차수의 다항식으로 근사하는 방법(라즈보로프–스몰렌스키 방법)의 대표 논문으로, ACC⁰ 하한 문제의 배경을 이해하는 데 필요하다. 회로 복잡도를 공부하는 독자에게 권한다. ACM 디지털 도서관으로 연결된다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Williams 2014 서론과 Aaronson 2017 §6.2.4 로 확인.
원문 주소 (doi.org)DOI 10.1145/28395.28404
부분 결과원문 확인
Algebraic methods for interactive proof systemsCarsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan · 1992Journal of the ACM 39(4), 859–868쪽 (1992) · 학회 발표 FOCS 1990 (31st Annual Symposium on Foundations of Computer Science), 2–10쪽
대화형 증명을 짓는 대수적 기법(산술화)을 도입해 다항 위계의 모든 문제가 대화형 증명을 가짐을 보인 논문이다. IP = PSPACE 와 PCP 정리로 이어지는 흐름의 출발점이다. 산술화가 어떻게 상대화 장벽을 넘는지 원문으로 보려는 독자에게 권한다. 공저자 Fortnow 의 누리집에 있는 공개본으로 연결한다.
확인:저자 공개본을 열어 초록과 서론을 읽음.
원문 주소 (lance.fortnow.com)
부분 결과서지만 확인
IP = PSPACEAdi Shamir · 1992Journal of the ACM 39(4), 869–877쪽 (1992) · 학회 발표 FOCS 1990 (31st Annual Symposium on Foundations of Computer Science), 11–15쪽
대화형 증명으로 증명할 수 있는 문제의 모임이 정확히 PSPACE 임을 보인 논문이다. 상대화되지 않는 증명의 대표 사례다. 같은 호에 나란히 실린 lfkn-1992 의 기법 위에 서 있으므로 두 편을 함께 본다. ACM 디지털 도서관으로 연결된다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.3.1 과 Arora–Barak 공개 초고 8장의 역사 주석으로 확인.
원문 주소 (doi.org)DOI 10.1145/146585.146609
부분 결과서지만 확인
Probabilistic checking of proofs: a new characterization of NPSanjeev Arora, Shmuel Safra · 1998Journal of the ACM 45(1), 70–122쪽 (1998) · 학회 발표 FOCS 1992 (33rd Annual Symposium on Foundations of Computer Science), 2–13쪽
NP 를 「무작위로 일부만 들춰 보는 증명」으로 새로 규정해 PCP 정리의 앞 절반을 놓은 논문이다. almss-1998 이 이 결과를 고쳐 읽는 비트 수를 상수로 줄였으므로 두 편을 함께 본다. ACM 디지털 도서관으로 연결된다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Arora–Barak 공개 초고 18장으로 확인.
원문 주소 (doi.org)DOI 10.1145/273865.273901
부분 결과원문 확인
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장으로 확인.
원문 주소 (people.csail.mit.edu)
장벽원문 확인
Natural proofsAlexander A. Razborov, Steven Rudich · 1997Journal of Computer and System Sciences 55(1), 24–35쪽 (1997) · 학회 발표 STOC 1994 (Proceedings of the 26th Annual ACM Symposium on Theory of Computing), 204–213쪽
알려진 회로 하한 증명들의 공통된 꼴을 「자연 증명」으로 정식화하고 그 한계를 보인 논문이다. 어려움에 관한 가정(강한 유사난수 생성기의 존재)이 참이라면 자연 증명으로는 일반 회로에 대한 초다항 하한을 증명할 수 없다는 둘째 장벽의 원전이다. 회로 하한 연구가 왜 막혔는지 이해하려는 독자에게 권한다. 게시자(Elsevier) 페이지로 연결된다.
확인:저자 공개본을 열어 §2(정의), §3.1, §4(정리 4.1·4.3)를 읽음. 연결한 게시자 주소의 서지는 DOI 등록 기록으로 확인.
원문 주소 (doi.org)DOI 10.1006/jcss.1997.1494
보조 자료원문 확인
P vs NPClay Mathematics Institute · 2026Clay Mathematics Institute 웹 페이지 (2026-10-05 확인)
Clay 수학연구소의 P 대 NP 문제 소개 페이지다. 기숙사 배정의 예로 문제를 설명하고, Cook 과 Levin 이 1971년에 독립적으로 문제를 정식화했다고 적으며, 문제의 상태를 「Unsolved」로 표시한다. 공식 문제 기술 PDF 로 가는 링크가 이 페이지에 있다.
확인:2026-10-05 에 페이지를 직접 열어 읽음(상태 표기 「Unsolved」 확인).
원문 주소 (www.claymath.org)
보조 자료원문 확인
Millennium Prize ProblemsWikipedia contributors · 2026영어 위키백과 (2026년 확인)
밀레니엄 문제를 다룬 영어 위키백과 문서다. 2-1 의 연표가 2000년 5월 24일 파리 발표라는 날짜와 장소를 확인하는 보조 자료로 썼다.
확인:위키백과 문서를 직접 열어 해당 서술을 확인(2차 자료).
원문 주소 (en.wikipedia.org)
접근서지만 확인
Geometric Complexity Theory I: An Approach to the P vs. NP and Related ProblemsKetan D. Mulmuley, Milind Sohoni · 2001SIAM Journal on Computing 31(2), 496–526쪽 (2001)
기하적 복잡도 이론(GCT)을 시작한 논문이다. 대수기하와 표현론의 배경이 필요한 전문 연구자용 논문이다. 접근의 얼개만 알고 싶다면 aaronson-2017 의 6.6절을 먼저 읽는 편이 좋다. SIAM 페이지로 연결되며 본문 열람에는 구독이 필요할 수 있다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.6.1–6.6.4 로 확인.
원문 주소 (doi.org)DOI 10.1137/s009753970038715x
부분 결과서지만 확인
PRIMES is in PManindra Agrawal, Neeraj Kayal, Nitin Saxena · 2004Annals of Mathematics 160(2), 781–793쪽 (2004) · 예비 논문 공개 2002년
주어진 수가 소수인지를 무작위도 미증명 가설도 쓰지 않고 다항 시간에 판정하는 알고리즘을 제시한 논문이다. 「소수 판별은 P 에 속하는가」라는 오랜 물음을 13쪽으로 해결했다. 어렵다고 여겨지던 문제에 뜻밖의 알고리즘이 나올 수 있음을 보여 주는 사례다. 학술지 누리집에서 PDF 를 받을 수 있다.
확인:학술지 누리집의 논문 페이지와 DOI 등록 기록으로 서지를 확인. 본문을 읽었다는 기록은 없음.
원문 주소 (annals.math.princeton.edu)
장벽원문 확인
Algebrization: A New Barrier in Complexity TheoryScott Aaronson, Avi Wigderson · 2009ACM Transactions on Computation Theory 1(1), 1–54쪽 (2009) · 학회 발표 STOC 2008 (Proceedings of the 40th Annual ACM Symposium on Theory of Computing), 731–740쪽
상대화를 넘어선 산술화 기법에도 한계가 있음을 보인, 대수화 장벽의 원전이다. 초록과 서론이 상대화·자연 증명·대수화 세 장벽의 관계를 정리하고 있어 2-2 를 깊이 읽으려는 독자의 다음 단계로 알맞다. 본론은 전문 연구자용이다. Aaronson 의 누리집에 있는 공개본으로 연결한다.
확인:저자 공개본을 열어 초록, §1, 정의 2.1–2.3 을 읽음.
원문 주소 (www.scottaaronson.com)
증명 주장원문 확인
P ≠ NPVinay Deolalikar · 2010미출판 원고 (HP Research Labs, 2010년 8월 6일 판, 66쪽) · G. Woeginger 의 P-versus-NP 페이지에 보관된 사본
2010년 8월에 공개되어 큰 관심을 모았고 며칠 만에 공개 검토를 받은 P ≠ NP 증명 주장의 원고다. 공개 검토에서 Immerman, Tao 등 여러 연구자가 찾아낸 문제는 두 갈래(P 를 논리로 규정하는 부분의 잘못된 사용, k-SAT 해 공간의 구조에 기댄 논증의 결함)로 요약되었다(lipton-regan-2010-08-15 카드의 글). 이 증명 주장은 받아들여지지 않았다. 그럴듯한 증명 주장이 어떻게 검증되는지 보여 주는 사례로, 2-5 를 읽는 독자에게 권한다. 연결한 것은 Woeginger 의 P-versus-NP 페이지에 보관된 원고 사본이다.
확인:Woeginger 의 페이지에 보관된 원고 사본(2010-08-06 판, 66쪽)을 열어 표지와 초록을 확인. 논증의 내용은 Lipton 의 요약 등 공개 검토 기록에 기댐.
원문 주소 (wscor.win.tue.nl)
증명 주장원문 확인
A Proof That P Is Not Equal To NP?R. J. Lipton · 2010블로그 Gödel's Lost Letter and P=NP, 2010년 8월 8일
Deolalikar 의 P ≠ NP 원고를 처음 소개한 Lipton 의 블로그 글이다. 원고를 진지한 연구자가 쓴 논문으로 소개하면서 논증의 뼈대를 요약하고, 상대화 문제를 걱정거리로 꼽는다. 2-5 의 Deolalikar 사례 글, 2-1 의 연표, 2-2 의 장벽 개관이 인용한다.
확인:블로그 글을 직접 열어 읽음.
원문 주소 (rjlipton.com)
부분 결과원문 확인
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 를 읽음.
원문 주소 (people.csail.mit.edu)
부분 결과원문 확인
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 공개본으로 연결한다.
확인:저자 공개본을 열어 초록과 서론을 읽음.
원문 주소 (eccc.weizmann.ac.il)
부분 결과원문 확인
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)을 읽음.
원문 주소 (eccc.weizmann.ac.il)
부분 결과원문 확인
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 공개본의 초록과 서론을 읽음.
원문 주소 (arxiv.org)arXiv 2009.11514
부분 결과서지만 확인
NP-Hardness of Learning Programs and Partial MCSPS. Hirahara · 2022FOCS 2022 (63rd Annual IEEE Symposium on Foundations of Computer Science), 968–979쪽 · ECCC TR22-119 (2022)
부분 함수판 최소 회로 크기 문제가 무작위 환원 아래 NP-난해임을 증명한 논문이다. MCSP 의 NP-난해성 문제로 한 걸음 다가선 결과다. 같은 논문은 효율적인 프로그램을 학습하는 문제의 NP-난해성도 보인다. 2-1 의 연표와 2-3 의 메타복잡도 글이 인용한다. ECCC 공개본으로 연결한다.
확인:ECCC TR22-119 공개본의 초록까지 확인. 본문을 읽었다는 기록이 분명하지 않아 서지 확인으로 둠.
원문 주소 (eccc.weizmann.ac.il)
개관원문 확인
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 등록 기록으로 확인.
원문 주소 (doi.org)DOI 10.1145/129712.129771
개관원문 확인
The status of the P versus NP problemLance Fortnow · 2009Communications of the ACM 52(9), 78–86쪽 (2009)
P 대 NP 문제의 의미와 2009년 시점의 연구 상황을 전산학 일반 독자에게 풀어 쓴 개관이다. 문제를 풀려던 시도들과 그 한계, NP-완전 문제를 현실에서 다루는 법, 양자 컴퓨터의 가능성까지 짧게 훑는다. 수식이 거의 없어 입문 독자가 처음 읽을 영어 글로 알맞다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본을 열어 인용한 절들을 읽음.
원문 주소 (lance.fortnow.com)
개관원문 확인
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년 판)을 열어 인용한 절들을 읽음.
원문 주소 (www.scottaaronson.com)

하위 정보 0

이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.

아직 없습니다.