보완
사실 검토 — 작은 수정 후 가능
2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.
판정: 작은 수정 후 가능
인용 저자·결과(Oliveira–Santhanam, McKay–Murray–Williams, Chen–Jin–Williams, CHOPRS 지역성 장벽, Liu–Pass, CIKK, Hirahara, Ilango)는 정확하다. 고칠 것은 (1) 증폭의 결과를 일괄 「P≠NP 급」으로 쓴 곳, (2) Liu–Pass 동치의 조건, (3) 자연 증명 「구조적으로 우회」·「로그 인자 수준만 개선하면 되는 거의 유일한 프레임」 같은 단정문이다.
확인한 사실
| 주장 | 사실 여부 | 근거 |
|---|---|---|
| MCSP·MKtP 의 아주 약한 하한이 「P≠NP 급」 분리로 증폭 | 일반화 과장 — 결과는 문제·모델마다 다르다: MCSP 변형 → NP ⊄ P/poly, NP ⊄ NC¹(Oliveira–Santhanam FOCS 2018), 스트리밍 하한 → P ≠ NP(McKay–Murray–Williams STOC 2019), MKtP → EXP ⊄ P/poly·EXP ≠ NC¹(EXP 분리는 P≠NP 급이 아님, Oliveira–Pich–Santhanam CCC 2019), 희소 NP 언어 → NP ⊄ SIZE[n^k](Chen–Jin–Williams FOCS 2019) | OS 2018, MMW 2019, OPS 2019, CJW 2019 |
| MKtP = 시간제한 콜모고로프 복잡도 문제 | 맞음 — Levin 의 Kt(= 설명 길이 + log 시간) | OPS 2019 |
| Liu–Pass 계열: OWF 존재 ⇔ MKtP 의 평균적 어려움(정확히 동치) | 조건 생략 — FOCS 2020 은 다항 시간 제한 K^t 의 「약한(mild) 평균 어려움」과 동치. MKtP 판은 CRYPTO 2021: 무한히 자주(io) OWF ⇔ MKtP 가 양측 오류 약한 평균 어려움(MKtP ∉ Heur_neg BPP). 무오류 판은 EXP ≠ BPP 와 동치 | Liu–Pass CRYPTO 2021 |
| CIKK: 자연 증명적 하한 → 학습 알고리즘 | 맞음 — Carmosino–Impagliazzo–Kabanets–Kolokolova CCC 2016(AC0[p] 를 포함하는 클래스, 균등 분포·소속 질의) | — |
| 지역성 장벽(Chen–Hirahara–Oliveira–Pich–Rajgopal–Santhanam) 설명 | 맞음 — ITCS 2020 / J. ACM 2022. 증폭 대상 문제는 작은 팬인 오라클 게이트를 붙인 회로로 효율적으로 풀리고, 기존 하한 기법은 그런 회로에도 그대로 통한다 | CHOPRS |
| 증폭 기반 하한은 largeness 를 피해 간다 → 「이 경로는 가장 유명한 장벽을 구조적으로 우회한다」 | 절반 맞음 — CHOPRS 는 일부 MCSP 판의 초선형 하한이 자연 증명의 부재를 함의함을 보였다. 곧 그 하한은 자연 증명으로는 얻을 수 없는 하한이라는 뜻이며, 이 경로가 장벽을 자동으로 우회한다는 뜻은 아니다(바로 그 지점에 지역성 장벽이 있다) | CHOPRS |
| 「현재 하한에서 로그 인자 수준만 개선하면 되는」 거의 유일한 프레임 | 과장 — 문턱이 기존 하한에 아주 가까운 경우가 있음은 맞다(OPS 2019 는 한 모델에서 문턱이 기존 하한 아래임을 보임, MMW 스트리밍은 polylog 공간). 그러나 많은 경우 간극은 n^{1+ε} 대 n^{1+o(1)} 같은 다항 간극이고, 「거의 유일한 프레임」은 출처 없는 평가 | OPS 2019, MMW 2019 |
| 지역성 장벽은 상대화·대수화처럼 사후적으로 발견된 장벽이 아니다 | 해석 — 지역성 장벽도 「기존 기법이 왜 증폭 문턱에서 멈추는가」를 설명하려고 정식화된 장벽이다. 「설계 명세에 가깝다」는 이 글의 관점으로 표시하면 충분 | CHOPRS |
| Hirahara 최악-평균 환원 | 맞음 — Hirahara FOCS 2018(GapMINKT, 비블랙박스) | — |
| Hirahara 부분함수 MCSP NP-난해성 | 맞음 — FOCS 2022(무작위 환원) | — |
| Ilango 의 공식 버전 결과 | 맞음 — 상수 깊이 공식·부분함수 MCSP 난해성(FOCS 2020), MFSP 의 ETH 난해성(FOCS 2021) | — |
고칠 곳
- 핵심 정리 1번째 줄·개요 첫 문단
- 원문: 「MCSP·MKtP 에 대한 「아주 약한」 회로 하한만 증명해도 P≠NP 급의 강한 분리로 증폭된다.」
- 제안: 「MCSP·MKtP 에 대한 「아주 약한」 회로 하한만 증명해도 NP ⊄ P/poly·NP ⊄ NC¹(MCSP 변형)이나 EXP ⊄ NC¹(MKtP) 같은 강한 분리로 증폭된다(문제·모델마다 따라 나오는 분리가 다르다).」
- 서두 요약의 「아주 약해 보이는 하한 하나가 P≠NP 급 분리로 증폭될 수 있다」도 「강한 분리로」로.
- 핵심 정리 2번째 줄·개요 첫 문단
- 원문: 「원웨이 함수의 존재는 MKtP 의 평균적 어려움과 정확히 동치다.」
- 제안: 「(무한히 자주 성립하는) 원웨이 함수의 존재는 MKtP 의 양측 오류 약한 평균적 어려움과 정확히 동치다(Liu–Pass 2021; 다항 시간 제한 K^t 판은 Liu–Pass 2020).」
- 「왜」 2번째 항목
- 원문: 「증폭 기반 증명과 메타복잡도 문제 자체에 대한 하한은 이 largeness 조건을 피해 가는 것으로 이해되고 있다. 즉 이 경로는 가장 유명한 장벽을 구조적으로 우회한다.」
- 제안: 「CHOPRS(2020)는 일부 MCSP 판에 대한 초선형 하한이 자연 증명의 부재를 함의함을 보였다 — 이 경로가 요구하는 하한은 자연 증명으로는 얻을 수 없는 종류라는 뜻이다. 그래서 이 경로는 자연 증명 장벽을 비켜 갈 여지가 있다고 논의되지만, 그 자리에 지역성 장벽이 있다.」
- 「왜」 1번째 항목
- 원문: 「hardness magnification은 P≠NP 공략에 필요한 하한을 "현재 알려진 하한에서 로그 인자 수준만 개선하면 되는" 목표로 끌어내린 거의 유일한 프레임이다.」
- 제안: 「hardness magnification은 강한 분리에 필요한 하한을, 경우에 따라 현재 알려진 하한과 아주 작은 차이(어떤 모델에서는 문턱이 기존 하한보다 아래 — Oliveira–Pich–Santhanam 2019)만 남긴 목표로 끌어내렸다.」
- 「왜」 3번째 항목
- 원문: 「지역성 장벽은 상대화·대수화처럼 사후적으로 발견된 장벽이 아니라, 증폭 프런티어에서 무엇이 필요한지를 알려주는 설계 명세에 가깝다.」
- 제안: 「이 글은 지역성 장벽을, 증폭 프런티어에서 무엇이 필요한지를 알려주는 설계 명세로 읽는다.」
고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.
이 글에 단 답 0
아직 없습니다.