보완
사실 검토 — 보완 필요
2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.
판정: 보완 필요
1단(LST·깊이 축소·캐즘)의 인용은 대체로 맞다. 그러나 ① 2단(대수 분리 → 불리언 분리)의 근거로 든 세 결과가 모두 반대 방향의 함의다 — Bürgisser 의 「Cook 대 Valiant」는 GRH 아래 「VP=VNP ⇒ 불리언 붕괴」, 즉 불리언 분리 ⇒ 대수 분리이고, τ-추측은 대수 분리를 낳는 가정이지 불리언으로 내리는 다리가 아니다. 대수 분리에서 불리언 분리를 끌어내는 정리는 알려져 있지 않으며, 2단 자체가 미해결 문제라는 사실이 글에 표시돼 있지 않다 ② 저자 이름 오기(Ghosal → Ghosh) ③ VP⁰≠VNP⁰ 를 더 강한 목표처럼 썼지만 실제로는 VP≠VNP 에서 따라 나오는 더 약한 명제 ④ LST 의 대상 다항식(IMM)은 VP 안에 있어 그 하한을 아무리 키워도 캐즘 문턱에 닿지 않는다(대상 다항식을 VNP 쪽으로 바꿔야 함). 2단 서술은 문장 몇 개가 아니라 단락 단위로 다시 써야 하므로 「보완 필요」로 판정했다.
확인한 사실
| 주장 | 사실 여부 | 근거 링크 |
|---|---|---|
| LST(2021): 표수 0 체 위 상수 깊이 산술 회로에 대한 최초의 초다항 하한 | 맞음 — Limaye–Srinivasan–Tavenas, FOCS 2021 (ECCC TR21-081). 표수 0 또는 큰 표수. 대상은 반복 행렬곱 IMM_{n,d}, 곱 깊이 Δ 에서 크기 n^{d^{exp(-O(Δ))}}. 이후 Forbes(CCC 2024)가 모든 체로 넓혔다(글에 없음) | https://eccc.weizmann.ac.il/report/2021/081/ · https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.31 |
| LST 의 지수가 깊이 축소 문턱(깊이 4 캐즘)에 못 미침 | 맞음. 단 LST 의 대상 IMM 은 VBP ⊆ VP 라 IMM 하한은 원리상 문턱에 닿을 수 없음 — 문턱 도달은 VNP 쪽 다항식(퍼머넌트 등)에 대해서만 의미가 있음 | https://eccc.weizmann.ac.il/report/2021/081/ |
| 깊이 축소·캐즘: Agrawal–Vinay, Koiran, Tavenas, Gupta–Kamath–Kayal–Saptharishi | 맞음 (Agrawal–Vinay FOCS 2008 「A chasm at depth four」, Koiran TCS 2012, Tavenas MFCS 2013, GKKS FOCS 2013 「A chasm at depth three」) | https://arxiv.org/abs/1307.3863 (대수 복잡도 클래스 개관) |
| LST 기법 = 집합-다중선형화 + 부분미분·랭크 측도 | 맞음 (set-multilinearization 후 relative rank 측도) | https://eccc.weizmann.ac.il/report/2021/081/ |
| 「Agrawal–Ghosal–Saxena」 부트스트랩 | 저자 이름 오기 — Manindra Agrawal, Sumanta Ghosh, Nitin Saxena, 「Bootstrapping variables in algebraic circuits」, STOC 2018 | https://eccc.weizmann.ac.il/report/2018/035 · https://www.cse.iitk.ac.in/users/nitin/papers/stoc18-tiny-circuits.pdf |
| AGS = 「약간 비자명한 하한이나 PIT 미세 개선이 강한 하한으로 증폭」 | 부분적으로 맞음 — AGS 가 증폭하는 것은 블랙박스 PIT(hitting set) 이다(아주 적은 변수에 대한 부분 hsg → 완전 hsg). 하한 결론은 「Kabanets–Impagliazzo 보다 약간 강한 하한」, 즉 「E ⊄ #P/poly 이거나 VNP 에 2^{Ω(n)} 복잡도 다항식이 있다」 라는 선언형이지 VP≠VNP 단독이 아님 | 위 PDF (Abstract · Lemma 10) |
| 「산술판 경도 증폭(hardness magnification)」 | 표준 용어로 확인되지 않음 — 산술 쪽에서 대응하는 것은 위 부트스트랩·「상수 변수 다항식의 경도 → PIT」 계열. 글의 새 제안이라면 그렇게 표시해야 함 | — |
| VP≠VNP 를 노리고 「가능하면 상수 없는 버전 VP⁰≠VNP⁰」 | 방향 오류 — 퍼머넌트는 VNP⁰ 에 있고 VP⁰ ⊆ VP 이므로, (표수 0 에서) VP≠VNP 이면 VP⁰≠VNP⁰ 가 따른다. 즉 VP⁰≠VNP⁰ 는 더 약한 목표다(τ-경로가 상수 없는 모델을 쓰기 때문에 등장하는 것) | 검토자 추론(정의에서 직접) · https://doi.org/10.1007/s00037-009-0260-x |
| Bürgisser 의 「Cook 대 Valiant」 연결로 대수 분리를 불리언 분리로 옮긴다 | 방향 오류 — Bürgisser(「Cook's versus Valiant's hypothesis」, TCS 2000): GRH 아래 VP=VNP 이면 비균일 #P ⊆ NC³/poly 등 불리언 붕괴. 대우는 「불리언 분리 ⇒ (GRH) VP≠VNP」. 역(대수 분리 ⇒ 불리언 분리)은 알려져 있지 않고, 역방향으로 「활용」할 수 있는 논리적 경로가 없다 | https://arxiv.org/abs/1307.3863 |
| Shub–Smale τ-추측·Koiran 실 τ-추측을 「통해」 불리언 세계로 이전 | 역할 오류 — τ-추측 ⇒ P_C≠NP_C(Shub–Smale, Duke Math. J. 1995), τ-추측(약한 형태) ⇒ 퍼머넌트의 상수 없는 회로 초다항 하한(Bürgisser, Computational Complexity 18, 2009), 실 τ-추측 ⇒ 퍼머넌트 초다항 하한(Koiran 2011). 모두 대수 분리를 낳는 가정이지 대수 → 불리언 다리가 아니다 | https://doi.org/10.1007/s00037-009-0260-x · https://arxiv.org/abs/1806.00417 |
| 유한체(F_2) 위 VNP 의 불리언 부분과 ⊕P | 관계 자체는 맞음(Bürgisser: 유한체 위에서도 VP=VNP 이면 해당 mod-p 계수 클래스가 붕괴). 그러나 역시 「불리언 분리 ⇒ 대수 분리」 방향 | https://arxiv.org/abs/1307.3863 |
| 「P≠NP 또는 그 전조인 ⊕P 하한·PH 비붕괴」 | 부정확 — PH 비붕괴는 P≠NP 보다 강한 명제(P≠NP 를 함의)이고, ⊕P 비균일 하한은 P≠NP 와 함의 관계가 없다. 「전조」가 아니라 「이웃 명제」 | 정의 |
| 대수적 자연 증명 장벽 = Forbes–Shpilka–Volk, Grochow–Kumar–Saks–Saraf | 맞음 (FSV STOC 2017 / Theory of Computing 2018 「Succinct hitting sets and barriers…」, GKSS arXiv 2017 「Towards an algebraic natural proofs barrier via PIT」) | https://arxiv.org/abs/1701.01717 |
| 「LST 증명이 대수적으로 자연한 형태이면서도 성공했다는 사실의 시사점」 | 모순은 아님 — 대수적 자연 증명 장벽(조건부)은 VP 전체에 대한 것이고 LST 는 상수 깊이 대상이다. 글이 「장벽과 긴장」처럼 읽히지 않게 한 줄 덧붙이길 권함 | https://arxiv.org/abs/1701.01717 |
| 「산술 회로 하한은 상대화·대수화 장벽의 직접 사정권 밖」 | 판단으로 표시됨 — 1단에 대해서는 통설과 맞다. 그러나 2단의 결론(불리언 P≠NP)은 세 장벽의 사정권 안이다. 표가 1단만 다룬다는 단서가 필요 | https://eccc.weizmann.ac.il/report/2008/005 |
| 「깊이 축소 정리 덕분에 목표가 "상수 깊이 모델에서 지수 몇 개 개선"이라는 유한한 기술 문제로 환원」 | 과장 — 깊이 4 캐즘은 VNP 다항식에 대해 n^{ω(√d)} 급(일반 깊이 4) 하한을 요구하고, LST 의 n^{d^{exp(-O(Δ))}} 와는 거리가 크며 대상 다항식도 바꿔야 한다 | https://eccc.weizmann.ac.il/report/2021/081/ |
| 글 안 순서 대조 — 「7단계에서 정리」, 「2의 개선된 하한이 3의 증폭기」 | 맞음 | 본문 |
고칠 곳
- 원문(핵심 정리 2·개요 2문단·진행 방법 3): 「Agrawal–Ghosal–Saxena」 → 「Agrawal–Ghosh–Saxena」 (세 곳 모두; 「AGS」 약칭은 그대로 맞다).
- 원문(개요 2문단): 「매우 제한된 모델의 "약간 비자명한" 하한이나 PIT 미세 개선이 강한 하한으로 증폭되는 Agrawal–Ghosal–Saxena 계열 결과」
→ 제안: 「아주 적은 변수에 대한 블랙박스 PIT(hitting set)의 미세 개선이 거의 완전한 PIT 탈무작위화로 증폭되고, 그 결과로 「E ⊄ #P/poly 이거나 VNP 에 지수 복잡도 다항식이 있다」는 하한이 따르는 Agrawal–Ghosh–Saxena(STOC 2018) 계열 결과」 - 원문: 「VP≠VNP(가능하면 상수 없는 버전 VP⁰≠VNP⁰)를 노리는 것이다.」
→ 제안: 「VP≠VNP 를 노린다. 2단의 τ-경로가 쓰는 상수 없는 버전 VP⁰≠VNP⁰ 는 VP≠VNP 에서 따라 나오는 더 약한 명제이므로 중간 목표로 둔다.」 (핵심 정리 2의 괄호도 같은 뜻으로) - 원문(개요 3문단): 「2단은 이렇게 얻은 대수적 분리를 Bürgisser의 "Cook 대 Valiant" 연결, Shub–Smale τ-추측과 Koiran의 실 τ-추측, 그리고 유한체 위 불리언 부분(Boolean part) 이론을 통해 불리언 세계의 분리(P≠NP 또는 그 전조인 ⊕P 하한·PH 비붕괴)로 이전하는 것이다.」
→ 제안: 「2단은 이렇게 얻은 대수적 분리를 불리언 세계의 분리(P≠NP, 또는 그 이웃 명제인 ⊕P 비균일 하한)로 옮길 길을 찾는 것이다. 알려진 연결은 모두 반대 방향이다 — Bürgisser 의 「Cook 대 Valiant」(2000)는 GRH 아래 「불리언 분리 ⇒ VP≠VNP」를 주고, Shub–Smale τ-추측·Koiran 실 τ-추측은 대수 분리를 낳는 가정이다. 대수 분리에서 불리언 분리를 끌어내는 정리는 알려져 있지 않으며, 2단은 그 역방향 다리를 새로 세워야 하는 미해결 문제다(이 글의 제안).」
핵심 정리 3(「2단: … 로 대수적 분리를 불리언 분리 … 로 옮긴다」)도 「옮길 다리를 찾는다 — 알려진 연결은 모두 반대 방향」으로 고친다. - 원문(진행 방법 6): 「Bürgisser의 GRH 조건부 붕괴 정리를 역방향으로 활용한다.」
→ 제안: 「Bürgisser 의 GRH 조건부 붕괴 정리(VP=VNP ⇒ 불리언 붕괴)는 방향이 반대라 그대로는 쓸 수 없으므로, 그 역이 어떤 추가 가정 아래 성립할 수 있는지를 조사 대상으로 삼는다.」 - 원문(진행 방법 5): 「τ-계열 결론(P_C≠NP_C, permanent 경도)을 불리언 세계로 내리는 데 필요한 추가 가정(GRH 등)을 전부 명시한 의존성 그래프」
→ 제안: 「τ-계열 결론(P_C≠NP_C, 퍼머넌트 경도)을 불리언 세계로 내리는 알려진 정리는 없으므로, 그런 이전이 가능하려면 무엇이 더 필요한지를 후보 가정과 함께 정리한 의존성 그래프」 - 원문(진행 방법 1·개요 1문단 뒤에 추가): 「LST 의 대상 다항식 IMM 은 VP 안에 있으므로, 깊이 축소 문턱 도달은 퍼머넌트 같은 VNP 다항식에 대한 하한으로만 의미가 있다.」 한 문장 추가.
- 원문(가치 3): 「목표가 "상수 깊이 모델에서 지수 몇 개 개선"이라는 유한하고 구체적인 기술 문제로 환원된다.」
→ 제안: 「목표가 「VNP 다항식에 대한 깊이 4(또는 깊이 3) 하한을 캐즘 문턱 위로」라는 구체적인 기술 문제로 환원된다. 다만 LST 지수와 문턱 사이의 간극은 아직 크다.」 - 원문(진행 방법 3): 「산술판 경도 증폭(hardness magnification)」
→ 제안: 「산술 회로판 경도 증폭(불리언 hardness magnification 에 대응하는 것을 이 글이 제안함)」 - 장벽 표 「상대화」·「대수화」 줄 끝에 추가: 「(1단에 한함 — 2단의 불리언 결론은 세 장벽의 사정권 안이다)」. 개요 1문단에 「이후 Forbes(CCC 2024)가 같은 하한을 모든 체로 넓혔다」를 덧붙이면 「표수 0」 서술이 최신 상태와 맞는다.
넣을 수 있는 문헌 목록 (제안)
- N. Limaye, S. Srinivasan, S. Tavenas, Superpolynomial lower bounds against low-depth algebraic circuits, FOCS 2021 (ECCC TR21-081).
- M. A. Forbes, Low-depth algebraic circuit lower bounds over any field, CCC 2024.
- M. Agrawal, S. Ghosh, N. Saxena, Bootstrapping variables in algebraic circuits, STOC 2018.
- M. Agrawal, V. Vinay, Arithmetic circuits: a chasm at depth four, FOCS 2008. / P. Koiran, Arithmetic circuits: the chasm at depth four gets wider, TCS 2012. / S. Tavenas, Improved bounds for reduction to depth 4 and depth 3, MFCS 2013. / A. Gupta, P. Kamath, N. Kayal, R. Saptharishi, Arithmetic circuits: a chasm at depth three, FOCS 2013.
- P. Bürgisser, Cook's versus Valiant's hypothesis, Theoretical Computer Science 235(1), 2000.
- P. Bürgisser, On defining integers and proving arithmetic circuit lower bounds, Computational Complexity 18:81–103, 2009.
- M. Shub, S. Smale, On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP≠P?", Duke Math. J. 81, 1995.
- P. Koiran, Shallow circuits with high-powered inputs, ICS 2011.
- M. A. Forbes, A. Shpilka, B. L. Volk, Succinct hitting sets and barriers to proving lower bounds for algebraic circuits, STOC 2017. / J. Grochow, M. Kumar, M. Saks, S. Saraf, Towards an algebraic natural proofs barrier via polynomial identity testing, arXiv 1701.01717, 2017.
고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.
이 글에 단 답 0
아직 없습니다.