보완
사실 검토 — 작은 수정 후 가능
2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.
판정: 작은 수정 후 가능
OGP 계열 인용(Gamarnik–Sudan, Huang–Sellke, Gamarnik–Jagannath–Wein, Ding–Sly–Sun, Achlioptas–Coja-Oghlan, Liu–Pass, Hirahara, Chvátal–Szemerédi)은 모두 맞다. 고칠 것은 ① 상전이 순서를 k 와 무관하게 고정해 적은 것 ② 「알려진 모든 효율적 알고리즘이 일제히 멈춘다」를 큰 k 조건 없이 쓴 것 ③ FF·BT 장벽의 조건부 성격(다항 위계 붕괴) 생략 ④ 「산술화를 안 쓰므로 대수화 장벽과 무관」이라는 논리 오류(본문에서는 판단 표시 없이 단정)다.
확인한 사실
| 주장 | 사실 여부 | 근거 링크 |
|---|---|---|
| 캐비티 방법(Mézard–Parisi–Zecchina) 예측, 이후 상당 부분 엄밀화 | 맞음 | Krzakala 외 PNAS 2007 |
| 해공간이 클러스터링 → condensation → freezing 을 「차례로」 겪음 | 순서가 k 에 따라 다르다. condensation 은 k≥4 에서 따로 나타나며(k=4: α_d 9.38, α_c 9.547, α_s 9.93), 큰 k 에서는 동결 변수가 대부분 클러스터에 생기는 밀도((1+ε)2^k ln k / k, 엄밀 증명)가 condensation(≈2^k ln 2)보다 훨씬 앞선다 | Krzakala 외 PNAS 2007 · Achlioptas–Coja-Oghlan arXiv 0803.2122 |
| 알려진 모든 효율적 알고리즘이 문턱보다 훨씬 이른 구조 변화 지점 부근에서 일제히 멈춤 | 큰 k 에 한해 맞음(Achlioptas–Coja-Oghlan 의 표현). 작은 k(예 3-SAT)에서는 서베이 전파가 클러스터링 문턱을 넘어 만족가능성 문턱 가까이까지 실험적으로 작동한다 | arXiv 0803.2122 |
| Ding–Sly–Sun 이 큰 k 에 대해 만족가능성 문턱 확정 | 맞음(STOC 2015, Annals 2022, k≥k₀) | Annals 2022 · arXiv 1411.0650 |
| Gamarnik–Sudan 의 국소 알고리즘 배제(원조) | 맞음(무작위 정규 그래프 최대 독립 집합, 1/2+1/(2√2) 배) | arXiv 1304.1831 |
| OGP 가 국소·저차수 다항식·안정·AMP·얕은 불리언 회로의 실패를 무조건 증명 | 맞음(대상 문제마다 다름). 불리언 회로는 깊이 < log n/(2 log log n)(스핀 글라스), 무작위 k-SAT 저차수 다항식은 κ*·2^k ln k / k(κ*≈4.911)에서 실패 — 알고리즘 문턱과는 상수배 간극 | GJW arXiv 2004.12063 · Bresler–Huang arXiv 2106.02129 |
| Huang–Sellke 의 타이트한 알고리즘 문턱(branching OGP) | 맞음(짝수 혼합 p-스핀, 립시츠 알고리즘) | arXiv 2110.07847 |
| Feigenbaum–Fortnow·Bogdanov–Trevisan: 최악→평균 (비적응 블랙박스) 환원이 어렵다 | 맞지만 조건부: 그런 환원이 있으면 coNP ⊆ NP/poly, 다항 위계가 3단계로 붕괴 | Bogdanov–Trevisan 서베이 arXiv cs/0606037 |
| Hirahara 의 비블랙박스 환원이 장벽을 우회 | 맞음. 단 대상은 시간제한 콜모고로프 복잡도(MINKT/GapMINKT)이며 NP 완전 문제의 최악→평균 환원은 아니다 | ECCC TR18-138 |
| Liu–Pass: 원웨이 함수 ⇔ 시간제한 콜모고로프 복잡도의 평균 난이도 | 맞음(FOCS 2020) | arXiv 2009.11514 |
| Chvátal–Szemerédi 의 무작위 k-CNF Resolution 하한 | 맞음(JACM 1988) | — (고전 결과) |
| 랜덤 XOR-SAT 는 클러스터링되어 있어도 가우스 소거로 풀림 | 맞음 | Achlioptas–Molloy arXiv 1107.5550 |
| 「산술화를 쓰지 않으므로 대수화 장벽과도 무관」 | 논리 오류. 상대화하는 기법은 모두 대수화하므로, 산술화를 안 쓴다는 것은 대수화 장벽을 벗어난다는 근거가 아니다. 무관하다고 볼 이유는 「오라클 없는 특정 알고리즘 클래스에 대한 하한이라 클래스 분리 장벽의 직접 대상이 아니다」 쪽이다 | Aaronson–Wigderson |
고칠 곳
- 핵심 정리 첫 줄
- 원문: 「절-변수 비율이 커지면 랜덤 k-SAT 의 해공간은 클러스터링 → condensation → freezing 의 상전이를 차례로 겪고, 알려진 모든 효율적 알고리즘은 만족가능성 문턱보다 훨씬 이른 구조 변화 지점 부근에서 일제히 멈춘다.」
- 제안: 「절-변수 비율이 커지면 랜덤 k-SAT 의 해공간은 클러스터링·condensation·freezing 의 상전이를 겪고(순서는 k 에 따라 다르다), 큰 k 에서는 알려진 효율적 알고리즘이 만족가능성 문턱(≈2^k ln 2)보다 훨씬 이른 구조 변화 지점(≈2^k ln k / k) 부근에서 멈춘다.」
- 아이디어 개요 첫 문단의 같은 내용
- 원문: 「이어 소수 클러스터에 측도가 집중되며(condensation), 변수들이 얼어붙는(freezing) 상전이를 차례로 겪는데, 알려진 모든 효율적 알고리즘은 … 일제히 멈춘다.」
- 제안: 「소수 클러스터에 측도가 집중되고(condensation), 변수들이 얼어붙는(freezing) 상전이도 일어나는데(두 전이의 순서는 k 에 따라 다르다 — 큰 k 에서는 freezing 이 먼저), 큰 k 에서 알려진 효율적 알고리즘은 … 이 구조 변화 지점 부근에서 멈춘다.」
- 아이디어 개요 — FF·BT 장벽
- 원문: 「"NP의 최악 사례를 평균 사례로 (비적응적 블랙박스로) 환원하기 어렵다"는 역방향 장벽」
- 제안: 「"NP 완전 문제의 최악 사례를 평균 사례로 비적응적 블랙박스 환원하면 다항 위계가 붕괴한다(coNP ⊆ NP/poly)"는 조건부 장벽」 (핵심 정리 제안 2 의 같은 표현도 맞춘다.)
- 왜 해볼 만한가 — 다리 쪽 기술
- 원문: 「Hirahara의 메타복잡도 기반 비블랙박스 환원이 실제로 이 장벽을 우회하는 사례를 만들었다.」
- 제안: 「Hirahara의 메타복잡도 기반 비블랙박스 환원이 시간제한 콜모고로프 복잡도 문제(MINKT·GapMINKT)에서 이 장벽을 우회하는 사례를 만들었다(NP 완전 문제의 최악→평균 환원은 아직 없다).」
- 왜 해볼 만한가 — 기존 장벽과의 관계(본문은 판단 표시 없음)
- 원문: 「OGP 논증은 구체적 문제의 조합적·기하적 구조를 사용하므로 대각화가 없어 상대화 장벽의 적용 대상이 아니고, 산술화를 쓰지 않으므로 대수화 장벽과도 무관하다.」
- 제안: 「OGP 하한은 오라클이 없는 특정 알고리즘 클래스에 대한 하한이므로 클래스 분리를 겨냥한 상대화·대수화 장벽의 직접 적용 대상이 아니라고 본다(산술화를 쓰지 않는다는 것만으로는 대수화 장벽을 벗어나지 못한다 — 상대화하는 기법은 모두 대수화한다).」 표의 상대화·대수화 행도 같은 근거로 고친다.
- 왜 해볼 만한가 — XOR-SAT
- 원문: 「해공간 기하만으로는 P≠NP에 도달할 수 없음을 XOR-SAT가 이미 증명해 주므로」
- 제안: 「해공간 기하만으로는 모든 다항 시간 알고리즘을 배제할 수 없음을 XOR-SAT가 이미 보여 주므로」
고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.
이 글에 단 답 0
아직 없습니다.