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

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

판정: 작은 수정 후 가능

정보 복잡도 쪽 인용(Chakrabarti–Shi–Wirth–Yao, BJKS, Braverman–Rao, BBCR, Ganor–Kol–Raz, GMWW, BGPW 정확한 상수)과 Razborov 의 submodular 측도 한계는 맞다. 고칠 것은 비교차성 하한의 공로, 공식 하한 수치의 기저 구분, 대수화 장벽 설명 오류다.

확인한 사실

고칠 곳

1. 핵심 정리 1번째 줄 · 개요 첫 문장
   • 원문: 「정보 복잡도는 집합 비교차성의 Ω(n) 하한, Braverman–Rao 의 「정보 비용 = 상각 통신 비용」 정리, direct sum 정리를 실제로 만들어 낸 가장 성숙한 의미론적 하한 도구다.」
   • 제안: 「정보 복잡도는 집합 비교차성 Ω(n) 하한의 새 증명(Bar-Yossef–Jayram–Kumar–Sivakumar)과 정확한 상수(Braverman–Garg–Pankratov–Weinstein), Braverman–Rao 의 「정보 비용 = 상각 통신 비용」 정리, direct sum 결과들을 낸 가장 성숙한 의미론적 하한 도구다(비교차성 Ω(n) 하한 자체는 Kalyanasundaram–Schnitger·Razborov 가 1992년에 먼저 증명했다).」
2. 「왜 해볼 만한가」 첫 문단
   • 원문: 「정보 복잡도는 통신 복잡도에서 추측으로만 떠돌던 direct sum 문제를 실제로 해결하고 비교차성의 정확한 상수까지 결정한,」
   • 제안: 「정보 복잡도는 통신 복잡도의 direct sum 문제를 상각 형태로 특성화하고(Braverman–Rao) 그 한계까지 확정했으며(Ganor–Kol–Raz) 비교차성의 정확한 상수까지 결정한,」
   • 같은 문단 「회로 쪽에는 이런 의미론적 측도가 사실상 없으므로」 → 「일반 회로 쪽에는 이런 의미론적 측도가 사실상 없으므로」
3. 핵심 정리 4번째 줄 · 개요 「중간 마일스톤」 문단
   • 원문: 「공식 크기 하한을 Nechiporuk형 상한(약 n²/log n)과 수축 기반 세제곱 하한 너머로 미는 것」
   • 제안: 「공식 크기 하한을, 전 이진 기저에서는 Nechiporuk 방법의 한계(약 n²/log n) 너머로, 드모르간 기저에서는 수축 기반 n^{3−o(1)} 너머로 미는 것」
4. 「왜 해볼 만한가」 장벽 문단과 장벽 표 대수화 칸
   • 원문: 「엔트로피는 저차 다항식 성질이 아니어서 대수화 논법에 그대로 포섭되지도 않는다.」
   • 제안: 「대수화 장벽은 측도의 모양이 아니라 증명이 오라클과 그 저차 확장을 준 세계에서도 그대로 성립하는지를 묻는다. 절단-정보 논법이 그런 세계에서 어떻게 되는지는 7단계에서 점검한다.」
5. (선택) 「열등모듈러」는 국내에서 드문 표기다(일본어 劣モジュラ 의 직역). 첫 등장(핵심 정리 3번째 줄)에도 「(submodular)」를 병기하면 독자가 원 문헌을 찾기 쉽다.

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