사실 검토 — 보완 필요

2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.

판정: 보완 필요

근거:

1. 갈래 1 의 알려진 상한이 빠졌다. ADV±(f) ≤ Q(f) ≤ n 이므로 「ADV± 제곱 ≤ 식 크기」 경로로 얻는 식 크기 하한은 n² 를 넘을 수 없다. 알려진 최고 명시적 De Morgan 식 하한은 n^(3−o(1))(Håstad·Tal, Andreev 함수)이라, 이 갈래가 「새 하한」을 낼 수 있는 범위는 n² 이하 영역뿐이다. 글은 마일스톤 B 에서 「Khrapchenko류 … 가 처리하지 못하는 영역에서 새 하한」을 목표로 하면서 이 상한을 말하지 않는다.
2. 갈래 2 의 연결이 알려진 정리처럼 쓰였다. KW 관계로 옮겨지는 현재의 리프팅 정리는 결정 트리 깊이·Nullstellensatz 차수 등을 들어 올리는 것이고, 근사 차수(쌍대 증인)를 KW 관계의 결정적 통신 하한으로 옮기는 정리는 알려져 있지 않다 — 이 연결이 바로 이 글의 제안인데 표시가 없다.
3. 사실 오기 다섯: Aaronson 귀속(원정리는 Vinodchandran), Reichardt 「정확히」(상수배), 「다항식 방법이 대수화 장벽의 전형 기법」(반대로 장벽을 증명하는 도구), 「식 크기 목표에는 PRF 후보가 없다」(NC1 에 있다), 「단조 스팬 프로그램 크기」(ADV± 는 증인 크기에 대응).

확인한 사실

고칠 곳

1. 핵심 정리 첫 줄·개요 첫 문단
   • 원문: 「Reichardt의 정리에 의해 ADV±는 양자 질의 복잡도를 SDP 쌍대성으로 정확히 특성화하며 스팬 프로그램(span program)과도 동치를 이룬다.」
   • 제안: 「Reichardt(2009·2011)와 Lee–Mittal–Reichardt–Špalek–Szegedy(2011)에 의해 ADV±(그 자체가 SDP)는 양자 질의 복잡도를 상수배 이내로 특성화하며, 그 쌍대가 스팬 프로그램의 증인 크기와 같다.」
2. 핵심 정리 둘째 줄·개요 첫 문단
   • 원문: 「Aaronson의 "PP는 크기 n^k 회로를 갖지 않는다"는 정리」
   • 제안: 「Vinodchandran(2005)의 "PP는 크기 n^k 회로를 갖지 않는다"는 정리를 Aaronson(2006)이 PostBQP=PP 로 다시 증명해 양자 회로·양자 조언까지 강화한 일」
3. 개요 첫 문단
   • 원문: 「Kerenidis-de Wolf의 국소 복호 가능 부호(LDC) 지수 하한」
   • 제안: 「Kerenidis–de Wolf의 2-질의 국소 복호 가능 부호(LDC) 지수 하한」
4. 핵심 정리 「갈래 1」·개요 둘째 문단(보완 필요의 핵심)
   • 원문: 「ADV± 의 제곱이 불리언 식 크기의 하한이 된다는 관계로, SDP 쌍대 증인에서 명시적 함수의 식 하한을 직접 생산한다.」
   • 제안: 「ADV± 의 제곱이 불리언 식 크기의 하한이 된다는 관계(상수배까지)로 SDP 쌍대 증인에서 명시적 함수의 식 하한을 생산한다. 단 ADV±(f) ≤ Q(f) ≤ n 이라 이 경로의 하한은 n² 를 넘지 못하며, 알려진 최고 하한 n^(3−o(1))(Håstad·Tal)보다 낮다 — 목표는 기록 경신이 아니라 n² 이하에서 기존 기법이 다루지 못하는 함수족이다.」
   • 마일스톤 B 의 「목표는 Khrapchenko류 하한이나 Håstad의 수축(shrinkage) 논법이 이미 잘 처리하는 영역이 아니라, …」 문장에도 같은 n² 상한을 적는다.
5. 마일스톤 B
   • 원문: 「특정 함수족의 식 크기 하한 또는 단조 스팬 프로그램 크기 하한을 도출한다.」
   • 제안: 「특정 함수족의 식 크기 하한(상한 n²) 또는 스팬 프로그램 증인 크기 하한을 도출한다(단조 스팬 프로그램의 '크기'는 ADV± 와 다른 측도다).」
6. 핵심 정리 「갈래 2」·개요 둘째 문단·마일스톤 C
   • 원문: 「근사 차수의 쌍대 증인을 리프팅 정리로 Karchmer–Wigderson형 통신 하한까지 끌어올려 회로 깊이 하한의 부품으로 만든다.」
   • 제안: 「근사 차수의 쌍대 증인을 Karchmer–Wigderson형 통신 하한까지 끌어올리는 리프팅을 새로 찾아 회로 깊이 하한의 부품으로 만든다(지금 알려진 KW 리프팅은 결정 트리 깊이 등에서 출발하며, 근사 차수에서 KW 관계로 가는 정리는 아직 없다 — 이 글의 제안이다).」
7. 이식 사전 작성(2단계)
   • 원문: 「근사 차수 → 패턴 행렬 → 양자·고전 통신 하한 → 부호 계수(sign-rank)·문턱 회로 하한」
   • 제안: 「근사 차수 → 패턴 행렬 → 양자·고전 유계 오차 통신 하한, 그리고 매끄러운 쌍대 증인을 가진 문턱 차수 → 부호 계수(sign-rank)·문턱 회로 하한(Razborov–Sherstov)」
8. 3단계(고전 어드버서리의 사거리) 끝에 덧붙임: 「전함수에서는 모든 고전 어드버서리 하한이 분수 블록 민감도와 같다는 것이 이미 알려져 있다(Ambainis–Kokainis–Prūsis–Vihrovs, STACS 2018) — 정식화의 대상은 부분함수 쪽 간극이다.」
9. 7단계(장벽 감사)·장벽 표 대수화 행
   • 원문: 「다항식 방법이 대수화 장벽의 전형 기법으로 지목된 만큼」 / 「다항식 방법은 대수화 장벽의 전형 기법으로 지목되었으므로」
   • 제안: 「Aaronson–Wigderson 이 다항식 구성과 통신 복잡도 하한으로 대수화 장벽(대수적 오라클 분리)을 증명했고 대수화하는 기법의 전형은 산술화이므로, 다항식 방법 기반 산출물이 어느 단계에서 대수화하는지와 어떤 변형(치트시트 결합 등)이 그 밖에 놓일 여지가 있는지 기록한다.」
10. 왜 해볼 만한가 — 장벽 관리·장벽 표 자연 증명 행
    • 원문: 「자연 증명 장벽은 식 크기·AC0급 목표에서는 해당 클래스에 유사난수 함수 후보가 없어 약하게만 작동하며」
    • 제안: 「AC0 에는 유사난수 함수 후보가 없어 자연 증명 장벽이 작동하지 않지만, 다항 크기 식(NC1)에는 TC0 의 Naor–Reingold 후보가 들어 있어 초다항 식 크기 하한 목표에서는 장벽이 그대로 작동한다. n² 이하를 다루는 갈래 1 에서는 이 장벽의 영향이 약하다고 본다.」
11. (선택) 7단계 「KW 대응을 통해 회로 세계로 진입하는 단계가 비상대화 성분의 주입 지점임을 명시하고」 → 「… 주입 지점이라고 보고(이 글의 판단)」. KW 대응은 조합적 동치이고, 비균일 명시적 하한에는 상대화 개념이 그대로 적용되지 않으므로 단정은 피한다.

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