상수깊이 하한 부트스트랩

하위 정보 2

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

보완 2

• 보완#62사실 검토 — 보완 필요
  • 관리자
  • 2026-10-07 13:04
  • AI 도움

  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의 증폭기」	맞음	본문

  고칠 곳

  1. 원문(핵심 정리 2·개요 2문단·진행 방법 3): 「Agrawal–Ghosal–Saxena」 → 「Agrawal–Ghosh–Saxena」 (세 곳 모두; 「AGS」 약칭은 그대로 맞다).
  2. 원문(개요 2문단): 「매우 제한된 모델의 "약간 비자명한" 하한이나 PIT 미세 개선이 강한 하한으로 증폭되는 Agrawal–Ghosal–Saxena 계열 결과」
     → 제안: 「아주 적은 변수에 대한 블랙박스 PIT(hitting set)의 미세 개선이 거의 완전한 PIT 탈무작위화로 증폭되고, 그 결과로 「E ⊄ #P/poly 이거나 VNP 에 지수 복잡도 다항식이 있다」는 하한이 따르는 Agrawal–Ghosh–Saxena(STOC 2018) 계열 결과」
  3. 원문: 「VP≠VNP(가능하면 상수 없는 버전 VP⁰≠VNP⁰)를 노리는 것이다.」
     → 제안: 「VP≠VNP 를 노린다. 2단의 τ-경로가 쓰는 상수 없는 버전 VP⁰≠VNP⁰ 는 VP≠VNP 에서 따라 나오는 더 약한 명제이므로 중간 목표로 둔다.」 (핵심 정리 2의 괄호도 같은 뜻으로)
  4. 원문(개요 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단: … 로 대수적 분리를 불리언 분리 … 로 옮긴다」)도 「옮길 다리를 찾는다 — 알려진 연결은 모두 반대 방향」으로 고친다.
  5. 원문(진행 방법 6): 「Bürgisser의 GRH 조건부 붕괴 정리를 역방향으로 활용한다.」
     → 제안: 「Bürgisser 의 GRH 조건부 붕괴 정리(VP=VNP ⇒ 불리언 붕괴)는 방향이 반대라 그대로는 쓸 수 없으므로, 그 역이 어떤 추가 가정 아래 성립할 수 있는지를 조사 대상으로 삼는다.」
  6. 원문(진행 방법 5): 「τ-계열 결론(P_C≠NP_C, permanent 경도)을 불리언 세계로 내리는 데 필요한 추가 가정(GRH 등)을 전부 명시한 의존성 그래프」
     → 제안: 「τ-계열 결론(P_C≠NP_C, 퍼머넌트 경도)을 불리언 세계로 내리는 알려진 정리는 없으므로, 그런 이전이 가능하려면 무엇이 더 필요한지를 후보 가정과 함께 정리한 의존성 그래프」
  7. 원문(진행 방법 1·개요 1문단 뒤에 추가): 「LST 의 대상 다항식 IMM 은 VP 안에 있으므로, 깊이 축소 문턱 도달은 퍼머넌트 같은 VNP 다항식에 대한 하한으로만 의미가 있다.」 한 문장 추가.
  8. 원문(가치 3): 「목표가 "상수 깊이 모델에서 지수 몇 개 개선"이라는 유한하고 구체적인 기술 문제로 환원된다.」
     → 제안: 「목표가 「VNP 다항식에 대한 깊이 4(또는 깊이 3) 하한을 캐즘 문턱 위로」라는 구체적인 기술 문제로 환원된다. 다만 LST 지수와 문턱 사이의 간극은 아직 크다.」
  9. 원문(진행 방법 3): 「산술판 경도 증폭(hardness magnification)」
     → 제안: 「산술 회로판 경도 증폭(불리언 hardness magnification 에 대응하는 것을 이 글이 제안함)」
  10. 장벽 표 「상대화」·「대수화」 줄 끝에 추가: 「(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.

  고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.

  답 달기
• 보완#82원문 보완판 — 사실 검토 반영
  • 관리자
  • 2026-10-07 13:28
  • AI 도움
  • 빨간 표시 안보이게

  2021년 상수 깊이 산술 회로에 대한 최초의 초다항 하한이 나왔지만, 그 지수는 VP≠VNP 로 이어지는 문턱에 아직 못 미친다. 이 글은 그 간극을 메우고 결과를 불리언 세계까지 옮길 길을 찾는 2단 파이프라인을 제안한다. 2단(대수 분리 ⇒ 불리언 분리)은 알려진 정리가 없는 미해결 문제다.

  아이디어 개요

  2021년 Limaye–Srinivasan–Tavenas(LST)는 표수 0 체 위 상수 깊이 산술 회로에 대한 최초의 초다항 하한을 증명했지만(이후 Forbes(CCC 2024)가 같은 하한을 모든 체로 넓혔다), 그 지수는 깊이 축소(depth reduction) 정리가 VP≠VNP 도출에 요구하는 문턱값(예: 깊이-4에서의 캐즘 지수)에 아직 미치지 못한다. LST 의 대상 다항식 IMM 은 VP 안에 있으므로, 깊이 축소 문턱 도달은 퍼머넌트 같은 VNP 다항식에 대한 하한으로만 의미가 있다.

  본 아이디어는 이 간극을 메우는 2단 파이프라인을 설계하는 것이다. 1단은 산술 세계의 부트스트랩 현상 — 아주 적은 변수에 대한 블랙박스 PIT(hitting set)의 미세 개선이 거의 완전한 PIT 탈무작위화로 증폭되고, 그 결과로 「E ⊄ #P/poly 이거나 VNP 에 지수 복잡도 다항식이 있다」는 하한이 따르는 Agrawal–Ghosh–Saxena(STOC 2018) 계열 결과 — 을 하한 증폭기로 재구성해 LST형 하한을 (대상을 VNP 다항식으로 바꿔) 깊이 축소 문턱까지 끌어올려 VP≠VNP 를 노린다. 2단의 τ-경로가 쓰는 상수 없는 버전 VP⁰≠VNP⁰ 는 VP≠VNP 에서 따라 나오는 더 약한 명제이므로 중간 목표로 둔다.

  2단은 이렇게 얻은 대수적 분리를 불리언 세계의 분리(P≠NP, 또는 그 이웃 명제인 ⊕P 비균일 하한)로 옮길 길을 찾는 것이다. 알려진 연결은 모두 반대 방향이다 — Bürgisser 의 「Cook 대 Valiant」(2000)는 GRH 아래 「불리언 분리 ⇒ VP≠VNP」를 주고, Shub–Smale τ-추측·Koiran 실 τ-추측은 대수 분리를 낳는 가정이며, 유한체 위 불리언 부분(Boolean part)의 관계도 「불리언 분리 ⇒ 대수 분리」 방향이다. 대수 분리에서 불리언 분리를 끌어내는 정리는 알려져 있지 않으며, 2단은 그 역방향 다리를 새로 세워야 하는 미해결 문제다(이 글의 제안). PH 비붕괴는 「전조」가 아니라 P≠NP 를 함의하는 더 강한 명제다. 전체를 독립 모듈로 분해해 어느 연결부가 진짜 병목인지 정량화하는 것이 핵심 목표다.

  

  구체적 진행 방법

  1. 문턱값 지도 작성: Agrawal–Vinay, Koiran, Tavenas, Gupta–Kamath–Kayal–Saptharishi의 깊이 축소·"깊이의 캐즘" 결과를 정리해, 깊이 3/4/일반 상수 깊이 각각에서 VP≠VNP를 함의하는 데 필요한 하한 지수와 LST가 실제로 준 지수 사이의 간극을 표로 정량화한다. LST 의 대상 다항식 IMM 은 VP 안에 있으므로, 깊이 축소 문턱 도달은 퍼머넌트 같은 VNP 다항식에 대한 하한으로만 의미가 있다.
  2. LST 기법(집합-다중선형화 축소, 부분미분·랭크 측도 변환)의 손실 지점을 단계별로 분해해 지수가 깎이는 위치를 진단하고, 개선 여지가 큰 단계(예: set-multilinear화 비용)를 특정한다.
  3. 부트스트랩 모듈 구축: AGS형 PIT 부트스트랩과 산술 회로판 경도 증폭(불리언 hardness magnification 에 대응하는 것을 이 글이 제안함)을 "약한 하한 → 강한 하한" 증폭기로 재정식화하고, 희소 다항식 합-곱·깊이-3 파워링 회로 등 극히 제한된 모델에서의 미세 개선이 각각 어떤 증폭 결론을 주는지 조건부 정리 목록을 만든다.
  4. 접합: 2의 개선된 하한이 3의 증폭기 전제를 충족하도록 맞물려, "현행 기법 + ε 개선 → VP⁰≠VNP⁰"가 성립하는 최소 ε을 명시하는 조건부 정리를 목표로 한다. permanent 대 determinant의 행렬식 복잡도 하한과의 함의·등가 관계도 병기한다.
  5. 이전 모듈 A(τ-경로): 상수 없는 회로 분리가 Shub–Smale τ-추측·Koiran 실 τ-추측과 갖는 함의 구조(τ-추측 쪽이 대수 분리를 낳는 방향)를 정리하고, τ-계열 결론(P_C≠NP_C, 퍼머넌트 경도)을 불리언 세계로 내리는 알려진 정리는 없으므로, 그런 이전이 가능하려면 무엇이 더 필요한지를 후보 가정과 함께 정리한 의존성 그래프를 만든다.
  6. 이전 모듈 B(불리언 부분 경로): 유한체, 특히 F_2 위에서 VNP의 불리언 부분과 ⊕P의 관계를 정리한다. 알려진 관계(유한체 위에서도 VP=VNP 이면 해당 mod-p 계수 클래스가 붕괴)는 「불리언 분리 ⇒ 대수 분리」 방향이므로, Valiant–Vazirani와 Toda 정리를 지렛대로 삼아 「유한체 VP≠VNP + α」에서 불리언 분리를 끌어낼 수 있는 α 가 있는지를 이 글의 가설로 탐색한다. Bürgisser 의 GRH 조건부 붕괴 정리(VP=VNP ⇒ 불리언 붕괴)는 방향이 반대라 그대로는 쓸 수 없으므로, 그 역이 어떤 추가 가정 아래 성립할 수 있는지를 조사 대상으로 삼는다.
  7. 장벽 점검: 각 모듈이 대수적 자연 증명 장벽(Forbes–Shpilka–Volk, Grochow–Kumar–Saks–Saraf)과 불리언 쪽 자연 증명·상대화·대수화 장벽에 걸리는지 사례별로 검사하고, LST 증명이 대수적으로 "자연"한 형태이면서도 성공했다는 사실이 장벽의 실효 범위에 주는 시사점을 정리한다. 이는 모순이 아니다 — 대수적 자연 증명 장벽(조건부)은 VP 전체에 대한 것이고 LST 는 상수 깊이 회로를 대상으로 한다.
  8. 산출물 설계: (a) 간극·문턱 정량화 서베이, (b) 조건부 증폭 정리 1건 이상, (c) 이전 경로 A/B의 최적 조건부 정리, (d) 병목 연결부 판정 보고서. 각 단계를 독립 논문으로 분리 가능하게 구성한다.

  왜 해볼 만한 가치가 있는가

  1. LST 결과는 "상수 깊이 산술 하한은 요원하다"는 통념을 깬 최근 돌파구인데, 이를 VNP 분리와 불리언 이전까지 잇는 전체 파이프라인을 정량적으로 명세한 연구는 드물다. 병목이 하한 쪽인지 이전 쪽인지 판정하는 것만으로도 분야의 지도가 갱신된다.
  2. 산술 회로 하한은 상대화·대수화 장벽의 직접 사정권 밖이라고 보며(1단에 한함 — 2단의 불리언 결론은 세 장벽의 사정권 안이다), 대수적 자연 증명 장벽은 불리언 자연 증명보다 전제(의사난수 다항식 족의 존재)가 훨씬 불확실하다고 본다. 즉 1단에 대해서는 P≠NP의 알려진 3대 장벽을 정면 돌파하지 않고 우회할 실질적 여지가 있는 방향이라는 것이 이 글의 판단이다.
  3. 깊이 축소 정리 덕분에 목표가 「VNP 다항식에 대한 깊이 4(또는 깊이 3) 하한을 캐즘 문턱 위로」라는 구체적인 기술 문제로 환원된다. 다만 LST 지수와 문턱 사이의 간극은 아직 크다. 전면적 공략과 달리 부분 성과(개선된 하한, 새로운 복잡도 측도)도 그 자체로 독립적 가치가 있어 실패 위험이 분산된다.
  4. 경도 증폭·부트스트랩은 불리언 세계에서는 자연 증명 장벽과 긴장 관계에 있으나 산술 세계에서는 그 긴장이 약해 증폭기 설계의 자유도가 크다고 본다. 두 세계의 증폭 이론을 나란히 비교하는 작업 자체가 장벽 현상의 이해에 기여한다.
  5. 본 경로는 GCT(기하 복잡도 이론)와 상보적이다. GCT가 표현론적 정공법으로 permanent 경도를 노린다면, 이 경로는 하한 증폭과 조건부 이전으로 같은 목표에 접근하므로, 최종 목표에 실패하더라도 측도·문턱 정리 등 GCT와 후속 연구에 재사용 가능한 부품을 남긴다.

  이 글이 보는 세 장벽과의 관계 — 아이디어 쪽의 판단이며 검증된 결론이 아니다

  장벽	이 글의 판단
  상대화	산술 회로 하한은 상대화 장벽의 직접 사정권 밖이라고 본다. (1단에 한함 — 2단의 불리언 결론은 세 장벽의 사정권 안이다)
  자연 증명	대수적 자연 증명 장벽은 불리언 자연 증명보다 전제(의사난수 다항식 족의 존재)가 훨씬 불확실하다고 본다. LST 증명이 대수적으로 「자연」한 형태이면서도 성공했다는 사실의 시사점을 7단계에서 정리한다. 대수적 자연 증명 장벽(조건부)은 VP 전체에 대한 것이고 LST 는 상수 깊이 대상이라 둘은 모순되지 않는다.
  대수화	산술 회로 하한은 대수화 장벽의 직접 사정권 밖이라고 본다. (1단에 한함 — 2단의 불리언 결론은 세 장벽의 사정권 안이다)

  참고 문헌

  • 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. — LIPIcs
  • M. Agrawal, S. Ghosh, N. Saxena, Bootstrapping variables in algebraic circuits, STOC 2018. — ECCC TR18-035 · PDF
  • 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. — 대수 복잡도 클래스 개관: arXiv 1307.3863
  • P. Bürgisser, On defining integers and proving arithmetic circuit lower bounds, Computational Complexity 18:81–103, 2009. — DOI
  • 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. — τ-추측 관련 자료: arXiv 1806.00417
  • 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, 2017. — arXiv 1701.01717
  • S. Aaronson, A. Wigderson, Algebrization: a new barrier in complexity theory, STOC 2008. — ECCC TR08-005
  답 달기