보완
사실 검토 — 작은 수정 후 가능
2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.
판정: 작은 수정 후 가능
인용한 장벽 세 개·후속 정식화(IKK·Aydınlıoğlu–Bach)의 저자·내용은 맞다. 고칠 것은 ① 자연 증명 장벽이 조건부라는 점이 빠짐 ② 「장벽을 실제로 뚫은 사례」 목록에 상대화만 넘은 결과(IP=PSPACE·MIP=NEXP — 둘 다 대수화는 넘지 못함)와 아직 장벽을 넘은 하한을 낸 적이 없는 계열(hardness magnification)이 섞여 있음 ③ 「제4의 장벽」을 새로 찾자고 하면서 이미 알려진 추가 장벽(국소성 장벽·대수적 자연 증명 장벽)을 언급하지 않음.
확인한 사실
| 주장 | 사실 여부 | 근거 링크 |
|---|---|---|
| 상대화 장벽 = Baker–Gill–Solovay | 맞음 (SIAM J. Comput. 4(4):431–442, 1975 — P^A=NP^A 인 오라클과 P^B≠NP^B 인 오라클이 모두 있음) | https://www.scottaaronson.com/papers/indep.pdf (참고문헌 [4]) · https://en.wikipedia.org/wiki/P_versus_NP_problem#Results_about_difficulty_of_proof |
| 자연 증명 장벽 = Razborov–Rudich | 맞음 (STOC 1994 / JCSS 55(1), 1997). 단 조건부 — 강한 의사난수 함수(지수적으로 어려운 일방향 함수)가 있다는 가정 아래에서만 「자연 증명은 P/poly 하한을 낼 수 없다」 | https://en.wikipedia.org/wiki/Natural_proof |
| 대수화 장벽 = Aaronson–Wigderson | 맞음 (STOC 2008 / ACM TOCT 1(1), 2009) | https://eccc.weizmann.ac.il/report/2008/005 |
| 「세 장벽은 각각 … 증명 기법 전체를 배제하는 불가능성 정리」 | 부분적으로 맞음 — 상대화·대수화는 무조건적 오라클 구성, 자연 증명은 암호 가정 아래의 조건부 정리 | 위 링크 |
| Impagliazzo–Kabanets–Kolokolova 의 산술화 공리화 | 맞음 (「An axiomatic approach to algebrization」, STOC 2009 — Arithmetic Checkability 공리) | https://www.cs.sfu.ca/~kabanets/Research/algebrization.html |
| Aydınlıoğlu–Bach 의 affine relativization | 맞음 (「Affine Relativization: Unifying the Algebrization and Relativization Barriers」, ECCC TR16-040 / ACM TOCT 2018) | https://eccc.weizmann.ac.il/report/2016/040 |
| IP=PSPACE 의 산술화가 장벽을 뚫은 사례 | 상대화만 뚫었다. Aaronson–Wigderson 은 IP=PSPACE·MIP=NEXP 등 산술화 기반 결과가 **대수화한다(algebrize)**고 보였다. 즉 이 사례에는 「비대수화 성분」이 없다. 자연 증명 장벽은 회로 하한에 대한 것이라 이 결과에는 해당 없음 | https://eccc.weizmann.ac.il/report/2008/005 |
| MIP=NEXP 가 장벽 우회 사례 | 상대화만 우회(Babai–Fortnow–Lund, Computational Complexity 1(1):3–40, 1991). 대수화는 함 | 위 링크 · indep.pdf 참고문헌 [3] |
| Williams 의 NEXP ⊄ ACC0 가 장벽을 뚫은 사례 | 맞음 — 상대화·대수화를 넘는다고 평가되며, 자연 증명은 대각선화(비결정 시간 계층)로 비켜 감. 단 ACC0 에 대해 자연 증명 장벽이 성립하는지(ACC0 안의 의사난수 함수)는 확립돼 있지 않다는 단서가 있음 | https://scottaaronson.blog/?p=472 · https://blog.computationalcomplexity.org/2010/11/breakthrough-circuit-lower-bound.html |
| 「시간 계층 정리의 비상대화 변형」이 장벽 우회 사례 | 근거 불명 — 시간 계층 정리 자체는 상대화한다. 아마 Buhrman–Fortnow–Thierauf 의 비상대화 분리(MA_EXP ⊄ P/poly, CCC 1998) 같은 결과를 가리키는 듯하나, 그것도 대수화하는 결과다 | https://www.scottaaronson.com/papers/indep.pdf (참고문헌 [8]) · https://eccc.weizmann.ac.il/report/2008/005 |
| hardness magnification 계열이 「장벽을 실제로 우회한 기존 결과」 | 틀림 — magnification 은 「약한 하한 → 강한 분리」라는 조건부 정리이고, 이로써 새 하한이 증명된 적은 없다. 오히려 Chen–Hirahara–Oliveira–Pich–Rajgopal–Santhanam 이 알려진 하한 기법이 magnification 전제를 못 채우는 이유를 **국소성 장벽(locality barrier)**으로 정리했다 | https://eccc.weizmann.ac.il/report/2019/168/ (ITCS 2020) |
| 「대수화 장벽 자체가 IP=PSPACE 는 왜 상대화를 피했는가라는 성분 분석에서 출발」 | 대체로 맞음 — AW 는 산술화 기반 비상대화 결과들을 분석해 그것들이 대수화함을 보였다 | https://eccc.weizmann.ac.il/report/2008/005 |
| 「Williams 의 하한도 장벽 회피 조건을 의식한 설계에서 나왔다」 | 해석 — Williams 의 출발점은 「SAT 알고리즘의 작은 개선 → 하한」 연결(STOC 2010)이며, 장벽 회피는 결과적 평가에 가깝다. 출처 없이 단정하기 어려움 | https://people.csail.mit.edu/rrw/improved-algs-lbs2.pdf |
| 「제4의 장벽」 가능성 탐색 | 이미 알려진 추가 장벽이 있음: 국소성 장벽(CHOPRS 2020), 대수적 자연 증명 장벽(Forbes–Shpilka–Volk 2017·Grochow–Kumar–Saks–Saraf 2017), affine relativization(대수화 재정식화). 「제4의 장벽」을 새로 찾자는 서술 전에 이것들을 기존 결과로 놓아야 함 | https://eccc.weizmann.ac.il/report/2019/168/ · https://eccc.weizmann.ac.il/report/2016/040 |
| 글 안 순서 대조 — 그림 설명 「점선 원은 8단계」 | 맞음 (진행 방법 8번째 항목이 「제4의 장벽」) | 본문 |
고칠 곳
- 원문: 「세 장벽 — 상대화(Baker–Gill–Solovay), 자연 증명(Razborov–Rudich), 대수화(Aaronson–Wigderson) — 은 각각 특정 성질을 가진 증명 기법 전체를 배제하는 불가능성 정리다.」
→ 제안: 「세 장벽 — 상대화(Baker–Gill–Solovay, 1975), 자연 증명(Razborov–Rudich, 1994/97), 대수화(Aaronson–Wigderson, 2008) — 은 각각 특정 성질을 가진 증명 기법으로는 P vs NP 를 풀 수 없음을 보인 정리다. 상대화·대수화는 오라클 구성으로 얻은 무조건적 결과이고, 자연 증명 장벽은 강한 의사난수 함수가 존재한다는 암호 가정 아래의 조건부 결과다.」 (핵심 정리 1번과 아이디어 개요 첫 문단 두 곳) - 원문: 「IP=PSPACE의 산술화나 Williams의 NEXP vs ACC0 하한처럼 실제로 장벽을 뚫은 성공 사례를 성분 분해하여, "비상대화·비자연·비대수화 성분"이 정확히 어디서 발생했는지 규명하는 작업」
→ 제안: 「IP=PSPACE 의 산술화(상대화만 넘음 — 대수화는 함)나 Williams 의 NEXP ⊄ ACC0 하한(세 장벽을 모두 넘는다고 평가됨)처럼 장벽을 실제로 넘은 사례를 성분 분해하여, 각 사례가 어느 장벽을 어느 단계에서 넘었는지 규명하는 작업」. 핵심 정리의 「검증 수단」 줄도 같은 뜻으로 고친다(「NEXP vs ACC0 하한」→「NEXP ⊄ ACC0 하한」). - 원문(진행 방법 3): 「장벽을 실제로 우회한 기존 결과들 — IP=PSPACE, MIP=NEXP, Williams의 ACC0 하한, 시간 계층 정리의 비상대화 변형, hardness magnification 계열 — 을 사례군으로 선정하고」
→ 제안: 「장벽을 실제로 넘은 기존 결과들 — 상대화만 넘은 IP=PSPACE·MIP=NEXP·MA_EXP ⊄ P/poly(Buhrman–Fortnow–Thierauf), 세 장벽을 모두 넘는다고 평가되는 Williams 의 NEXP ⊄ ACC0 — 을 사례군으로 선정하고, 아직 하한을 낳지 못했지만 자연 증명 장벽을 피하는 것처럼 보이는 hardness magnification 계열은 그 한계를 정리한 국소성 장벽(Chen 외, ITCS 2020)과 함께 대조군으로 둔다.」 - 원문(진행 방법 8): 「기존 세 장벽이 덮지 못하는 영역에 대해 "제4의 장벽"이 존재할 가능성도 함께 탐색하여」
→ 제안: 「세 장벽 뒤에 알려진 추가 장벽 — 국소성 장벽(Chen–Hirahara–Oliveira–Pich–Rajgopal–Santhanam 2020), 대수적 자연 증명 장벽(Forbes–Shpilka–Volk 2017, Grochow–Kumar–Saks–Saraf 2017) — 을 지도에 함께 올리고, 그래도 덮이지 않는 영역에 새 장벽이 있을 가능성을 탐색하여」 - 원문: 「Williams의 하한도 장벽 회피 조건을 의식한 설계에서 나왔다.」
→ 제안: 「Williams 의 하한(빠른 SAT 알고리즘 + 비결정 시간 계층)도 결과적으로 세 장벽을 모두 피한 사례로 평가된다.」
넣을 수 있는 문헌 목록 (제안)
- T. Baker, J. Gill, R. Solovay, Relativizations of the P=?NP question, SIAM J. Comput. 4(4):431–442, 1975.
- A. Razborov, S. Rudich, Natural proofs, STOC 1994 / J. Comput. Syst. Sci. 55(1), 1997.
- S. Aaronson, A. Wigderson, Algebrization: a new barrier in complexity theory, STOC 2008 / ACM TOCT 1(1), 2009.
- R. Impagliazzo, V. Kabanets, A. Kolokolova, An axiomatic approach to algebrization, STOC 2009.
- B. Aydınlıoğlu, E. Bach, Affine relativization: unifying the algebrization and relativization barriers, ACM TOCT, 2018 (ECCC TR16-040).
- R. Williams, Nonuniform ACC circuit lower bounds, CCC 2011 / J. ACM 61(1), 2014.
- L. Chen, S. Hirahara, I. Oliveira, J. Pich, N. Rajgopal, R. Santhanam, Beyond natural proofs: hardness magnification and locality, ITCS 2020.
고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.
이 글에 단 답 0
아직 없습니다.