사실 검토 — 작은 수정 후 가능

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

판정: 작은 수정 후 가능

강성 정의, Valiant(1977) 문턱, 무작위 행렬의 강성, Alman–Williams·Dvir–Edelman·Dvir–Liu·Kivva 의 비강성, Alman–Chen·BHPT 의 준명시적 구성은 맞다. 고칠 것은 ① Valiant 정리의 결론을 「선형 회로」가 아니라 일반 회로처럼 쓴 것 ② 「2016년 이후 … 아직 5년 남짓」(글 날짜 2026 기준 10년) ③ Dvir–Golovnev–Weinstein 의 방향 반대(데이터 구조 하한 ⇒ 강성) ④ Goldreich–Tal 을 「NP 오라클·PCP 기반」으로 묶은 것(무작위 Toeplitz) ⑤ 최고 명시적 하한의 저자에 Pudlák 을 넣은 것(표준 귀속은 Friedman·Shokrollahi–Spielman–Stemann) ⑥ 크로네커 비강성의 저자 누락(Alman 2021).

확인한 사실

고칠 곳

1. 핵심 정리 첫 줄
   • 원문: 「… 명시적 행렬 족을 하나만 구성해도, 선형 크기·로그 깊이 회로에 대한 무조건적 하한이 따라온다.」
   • 제안: 「… 명시적 행렬 족을 하나만 구성해도, 선형 크기·로그 깊이 선형 회로(linear circuit)에 대한 무조건적 하한이 따라온다.」
2. 아이디어 개요 첫 문단
   • 원문: 「그 행렬이 정의하는 선형 변환은 선형 크기·로그 깊이 회로로 계산될 수 없다는 무조건적 하한이 따라오며」
   • 제안: 「그 행렬이 정의하는 선형 변환은 선형 크기·로그 깊이 선형 회로로 계산될 수 없다는 무조건적 하한이 따라오며」
3. 핵심 정리 둘째 줄
   • 원문: 「2016년 이후 Walsh–Hadamard(Alman–Williams), 순환·DFT·크로네커 구조 후보(Dvir–Edelman, Dvir–Liu 계열)가 대부분 비강성으로 판명되었다.」
   • 제안: 「2016년 이후 Walsh–Hadamard(Alman–Williams, Dvir–Edelman), 순환·DFT·Toeplitz(Dvir–Liu), 크로네커 곱(Alman 2021, Kivva 2021) 구조 후보가 Valiant 의미에서 비강성으로 판명되었다.」 (개요 둘째 문단의 같은 문장도 Alman 을 더한다.)
4. 아이디어 개요 넷째 문단
   • 원문: 「Goldreich–Tal, Alman–Chen, Bhangale–Harsha–Paradise–Tal이 연 준명시적(NP 오라클·PCP 기반 시간 제한 구성) 강성 행렬」
   • 제안: 「Goldreich–Tal(무작위 비트 n 개의 무작위 Toeplitz), Alman–Chen(P^NP 구성), Bhangale–Harsha–Paradise–Tal(직사각 PCP 기반 FNP 구성)이 연 준명시적 강성 행렬(뒤의 둘은 무한히 많은 N 에서, Valiant 문턱보다 훨씬 낮은 랭크에서 성립)」
5. 1단계(기초 문헌 정독)
   • 원문: 「현재 최고 명시적 하한인 (n^2/r)log(n/r) 급 결과(Friedman, Shokrollahi–Spielman–Stemann, Pudlák)」
   • 제안: 「현재 최고 명시적 하한인 Ω((n²/r)log(n/r)) 결과(Friedman 1993 — 유한체, Shokrollahi–Spielman–Stemann 1997 — 임의 체)」 (Pudlák 을 넣으려면 해당 논문을 특정해 확인한다.)
6. 5단계(명시성 사다리)
   • 원문: 「무작위(비명시적) → PH·PCP 기반 준명시적 → NP 오라클 다항시간 → 결정적 다항시간(완전 명시적)」
   • 제안: 「무작위(비명시적) → 제한된 무작위성(Goldreich–Tal) → P^NP·FNP(Alman–Chen, 직사각 PCP 기반 BHPT) → 결정적 다항시간(완전 명시적)」
7. 6단계(문턱 이하 성과 트랙)
   • 원문: 「Valiant 문턱에 못 미치는 약한 강성 매개변수 영역이 함의하는 하한들 — Dvir–Golovnev–Weinstein의 정적 데이터 구조 하한 연결, 깊이-2 선형 회로 하한, Razborov·Wunderlich 계열의 통신 복잡도 다항 위계 분리 연결 —」
   • 제안: 「Valiant 문턱과 다른 강성 매개변수 영역과 이어진 하한들 — 정적 데이터 구조(강성 ⇔ 체계적 선형 데이터 구조 하한: Ramamoorthy–Rashtchian 2020, 데이터 구조 하한 ⇒ 강성: Dvir–Golovnev–Weinstein 2019), 깊이-2 선형 회로 하한, 낮은 랭크·거의 n² 변경 영역의 강성이 주는 Razborov·Wunderlich 계열의 통신 복잡도 다항 위계 분리 —」
8. 왜 해볼 만한가 — 최근의 부정 결과
   • 원문: 「2016년 이후 비강성 기법은 아직 5년 남짓 된 새 도구이고」
   • 제안: 「2016년 이후 비강성 기법은 아직 10년 남짓 된 새 도구이고」
9. (선택) 장벽 표 자연 증명 행에 덧붙임: 「다만 행렬의 강성을 계산하는 일 자체가 NP-어려워 '구성성' 조건이 성립하는지도 분명하지 않다.」

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