사실 검토 — 보완 필요

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

판정: 보완 필요

근거(요약):

1. 4단계의 「자연 증명 장벽이 켜지는 t 의 문턱」은 이미 알려져 있다 — Guo–Malkin–Oliveira–Rosen(TCC 2015)이 PRF 는 log n − O(1) 개의 부정 게이트가 필요하다(Markov 상한과 덧셈 상수 차)를 증명했다. 글은 이를 미해결 조사 과제·독립 결과로 제시하고, 「저부정 회로에는 PRF 가 있다고 믿을 근거가 희박」을 믿음으로 적었다. 실제로는 t < log n − O(1) 에서 PRF 가 없다는 것은 정리이고, 문턱은 사실상 Markov 한계(⌈log₂(n+1)⌉) 바로 아래다 — 「문턱 위 구간」은 상수 개 차이뿐이고 그 구간은 Fischer 에 의해 일반 회로와 같다. 그림 설명(점선 상자 = 4단계에서 추정할 문턱)과 「두 트랙의 나눔」 구도가 이 사실과 맞지 않는다.
2. 우회 트랙(Williams 의 알고리즘적 방법)이 주는 것은 NEXP·NQP 같은 큰 클래스의 하한이지 NP 완전 문제의 하한이 아니다. 따라서 「문턱 위 구간을 Williams 방법으로 우회」해도 P≠NP 로 이어지지 않는다 — 글은 두 트랙이 같은 종착점(P≠NP)을 향하는 것처럼 적고 이 차이를 표시하지 않았다.
3. 「자연 증명이 아님이 알려진 알고리즘적 방법」은 과장이다. Williams(STOC 2013 / SICOMP 2016)는 전형적 회로 클래스 C 에 대해 NEXP ⊄ C ⇔ C 에 유용한 구성적(constructive) 성질의 존재임을 보였다(구성성은 피할 수 없다). 대개 「대각선 논법을 써서 자연 증명 장벽을 직접 받지 않는다」고 설명하지만 「자연 증명이 아님이 알려졌다」는 정리는 없다.

확인한 사실

고칠 곳

1. 핵심 정리 1번째 줄·아이디어 개요 첫 문단
   • 원문: 「단조 하한만으로는 P≠NP 에 도달할 수 없다는 것도 Razborov 자신이 보였다.」
   • 제안: 「완전 매칭처럼 P 에 속하면서도 단조 회로로는 초다항 크기가 필요한 함수가 있다는 것도 Razborov 자신이 보였다(1985) — 단조 함수의 단조 하한은 일반 하한으로 자동으로 옮겨지지 않는다. (슬라이스 함수는 예외 — 아래 5단계)」
2. 4단계(장벽 지도화)와 「왜 해볼 만한」 3번째 항목·장벽 표 「자연 증명」 칸
   • 원문: 「단조 및 저부정 회로 클래스에는 PRF 가 존재한다고 믿을 근거가 희박해 이 구도에서는 약하고」
   • 제안: 「Guo–Malkin–Oliveira–Rosen(TCC 2015)은 PRF 가 log n − O(1) 개의 부정 게이트를 필요로 함을 보였다. 그래서 그보다 적은 부정을 허용하는 구간에는 PRF 가 없고 PRF 형태의 자연 증명 장벽은 직접 걸리지 않는다. 다만 그 문턱은 Markov 한계(⌈log₂(n+1)⌉)와 상수 차이뿐이라, 장벽이 켜지는 구간은 사실상 일반 회로와 같다.」
   • 4단계의 목표(문턱 추정)는 「GMOR 2015 의 문턱을 출발점으로, 근사법이 그 문턱 아래 어디까지 살아남는지 조사」로 바꾸기를 권한다. 그림 설명의 「점선 상자는 4단계에서 추정할 … 문턱」도 「GMOR 2015 가 보인 문턱(log n − O(1))」으로.
3. 6단계·「두 트랙의 나눔」·「왜」 3번째 항목
   • 원문: 「문턱 위 구간은 자연 증명이 아님이 알려진 알고리즘적 방법(6단계)으로 우회하도록 이중화되어 있다.」
   • 제안: 「문턱 위 구간에는 Williams 의 알고리즘적 방법을 시도한다. 이 방법은 대각선 논법을 쓰므로 자연 증명 장벽을 직접 받지 않는다고 설명되지만(그래도 Williams 2013 은 NEXP ⊄ C 가 구성적 성질의 존재와 동치임을 보였다), 산출물은 NEXP·NQP 하한이어서 이 트랙만으로는 NP 완전 문제의 하한, 곧 P≠NP 에 이르지 않는다.」
4. 「왜」 2번째 항목
   • 원문: 「상대화·대수화 장벽에 걸리지 않는다. … 대수화 장벽의 적용 대상도 아니다. 즉 세 대장벽 중 실질적 위협은 자연 증명 하나로 압축된다.」
   • 제안: 「상대화·대수화 장벽에 걸리지 않을 것으로 본다(이 글의 판단). 근사법 계열은 회로 내부 구조를 직접 다룬다. 다만 Aaronson–Wigderson 은 NEXP ⊄ P/poly 같은 회로 하한 자체가 비대수화 기법을 요구함을 보였으므로, 이 경로가 성공한다면 그 기법은 반드시 비대수화여야 한다.」
5. 「왜」 4번째 항목
   • 원문: 「Razborov(1985), Amano–Maruoka, Williams의 ACC⁰ 하한, 최근의 경도 증폭(hardness magnification) 정리들은 제한 회로 모델의 약해 보이는 하한이 주요 분리 결과로 증폭될 수 있음을 보여 주며, 본 연구의 부분 결과들도 증폭 정리의 입력이 될 수 있다.」
   • 제안: 「Razborov(1985), Amano–Maruoka(2005), Williams 의 ACC⁰ 하한(2011)은 제한 회로 모델에서 하한이 실제로 증명되어 온 전례이고, 증폭(hardness magnification) 정리들은 특정 문제(MCSP 변형 등)의 약한 하한이 강한 분리로 이어질 수 있음을 보였다. 본 연구의 부분 결과가 증폭 정리의 입력이 될 수 있는지는 이 글의 추측이다.」

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