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

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

판정: 작은 수정 후 가능

Huang(2019)·ALWZ(2019)·Razborov 단조 하한·Håstad 스위칭 렘마·LMN·Razborov–Smolensky·Rao/Tao 단순화·질의 측도 다항 동치는 맞다. 다만 표적 선택의 근거인 「드모르간 식은 유사난수 함수가 없다고 믿어지는 클래스」가 틀렸고 이 문장이 4곳(핵심 정리·개요·가치·장벽 표)에 반복된다. 고정 다항 크기(n^{3+ε}) 구간으로 좁혀 쓰면 아이디어 자체는 유지된다.

확인한 사실

고칠 곳

1. 핵심 정리 4번째 줄 · 개요 셋째 문단
   • 원문: 「표적: 자연 증명 장벽이 아직 작동하지 않는 약한 회로 클래스 — 드모르간 식 크기의 n^3 벽, AC0[⊕].」
   • 제안: 「표적: 자연 증명 장벽이 아직 문제되지 않는 약한 영역 — AC0[⊕], 그리고 드모르간 식의 고정 다항 크기 구간(n^3 벽). 다항 크기 드모르간 식(=NC¹) 전체는 유사난수 함수가 있다고 믿어져 초다항 식 하한은 장벽의 대상이다.」
   • 개요 원문: 「자연 증명 장벽이 아직 작동하지 않는 약한 회로 클래스(드모르간 식, AC0[⊕] 등)에서」 → 「자연 증명 장벽이 아직 문제되지 않는 영역(AC0[⊕], 드모르간 식의 n^3 벽 같은 고정 다항 크기 구간)에서」
2. 「왜 해볼 만한가」 장벽 문단과 장벽 표 자연 증명 칸
   • 원문: 「표적을 유사난수 함수가 없다고 믿어지는 약한 클래스(드모르간 식, AC0[⊕])로 한정하는 동안은 장벽 무풍지대에서 작업할 수 있고,」
   • 제안: 「표적을 강한 유사난수 함수가 없다고 알려진 AC0[⊕] 와, 드모르간 식의 고정 다항 크기 구간(n^{3+ε})으로 한정하는 동안은 장벽이 직접 문제되지 않는다고 본다(다항 크기 드모르간 식 = NC¹ 에는 유사난수 함수가 있다고 믿어지므로 초다항 식 하한부터는 장벽 정면이다).」
3. 「왜 해볼 만한가」 첫 문단
   • 원문: 「ALWZ가 그 문턱 자체를 60년 만에 갱신했지만,」
   • 제안: 「ALWZ가 Erdős–Rado(1960) 이후 Kostochka(1997)의 작은 개선만 있던 문턱을 크게 끌어내렸지만,」
4. 3단계(1차 마일스톤)
   • 원문: 「ALWZ 스프레드 렘마가 DNF 희소화(Lovett–Meka 계열)와 리프팅 가젯 크기 축소에 준 개선을」
   • 제안: 「해바라기·스프레드 렘마 개선이 DNF 희소화(Gopalan–Meka–Reingold, Lovett–Zhang 계열)와 리프팅 가젯 크기 축소(Lovett–Meka–Mertz–Pitassi–Zhang)에 준 개선을」
5. 개요 둘째 문단
   • 원문: 「Rossman의 강건 해바라기(robust sunflower)는 클리크에 대한 단조 회로 하한 개선과 리프팅 정리의 가젯 개선을 낳았다.」
   • 제안: 「Rossman 이 k-클리크 단조 복잡도에서 도입한 강건(준) 해바라기는 이후 단조 회로 하한 개선(Cavalar–Kumar–Rossman)과 리프팅 정리의 가젯 축소(Lovett–Meka–Mertz–Pitassi–Zhang)로 이어졌다.」
6. (작은 표현) 「Linial–Mansour–Nisan의 Fourier 집중 정리는 AC0 하한의 본체이며」 → 「스위칭 렘마는 AC0 하한의 본체이고 Linial–Mansour–Nisan 의 Fourier 집중 정리는 거기서 나온 AC0 의 스펙트럼 구조 결과이며」

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