보완
사실 검토 — 작은 수정 후 가능
2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.
판정: 작은 수정 후 가능
Blum–Kannan, BLR, LFKN·Shamir, Lipton, GKR, Sengupta, Santhanam, Vinodchandran, BFT, IKW, Feigenbaum–Fortnow, Aaronson–Wigderson, IKK, affine relativization 인용은 저자·내용이 대체로 맞다. 그러나 이 글의 주 트랙(하한 전선을 MA 에서 NP 로 끌어내리기)과 정확히 같은 지점을 Aaronson–Wigderson 이 이미 「대수화가 왜 거기서 멈췄는지를 설명한다」고 짚었고 NP ⊄ SIZE(n) 조차 비대수화 기법이 필요하다고 보였는데, 글은 이 알려진 사실 없이 간극의 원인을 「단일 질문」으로 단정한다. 문장 보완으로 해결된다.
확인한 사실
| 주장 | 사실 여부 | 근거 링크 | ||
|---|---|---|---|---|
| 「SAT 는 하향 자기 환원성을 가진다: 판정 오라클만 주어지면 만족 배정을 다항 시간에 복원」 | 정의 혼동 — 하향 자기 환원성은 「길이 n 인스턴스의 판정이 더 짧은 인스턴스들의 판정으로 환원됨」(φ 가 만족 가능 ⟺ φ | x1=0 또는 φ | x1=1 이 만족 가능)이다. 판정 오라클로 배정을 찾는 것은 그 결과인 탐색-판정 환원이다. 둘 다 SAT 에 대해 참이지만 같은 말이 아니다 | https://eccc.weizmann.ac.il/report/2022/133/revision/1/download |
| Blum–Kannan 프로그램 체킹, BLR self-testing/correcting | 맞음 (STOC 1989 / JACM 1995, STOC 1990 / JCSS 1993) | https://en.wikipedia.org/wiki/Self-testing_code | ||
| Levin 보편 탐색: 상수 배 손실 내 최적인 명시적 단일 알고리즘, 「P=NP 는 U 가 다항 시간에 도는 것과 동치」 | 단서 빠짐 — 맞는 진술은 「P=NP ⟺ U 가 만족 가능한 입력에서 다항 시간에 배정을 찾는다」이다. 불만족 입력에서는 U 가 끝나지 않으므로(아니오 답을 검증할 수단이 없음) U 는 그대로는 SAT 판정기가 아니다. 또 「상수 배」의 상수는 경쟁 알고리즘 길이에 지수적(2^{ | A | })이다 | https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms |
| 「이 관점에서 나오는 부분 명제는 모두 무조건적이다」 | 사실이 아니라 이 글의 목표 — U 의 실행 시간을 분석하는 일 자체가 P vs NP 와 같은 난이도다 | https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms | ||
| Santhanam: PromiseMA 회로 하한 | 맞음 (STOC 2007, SICOMP 2009: 모든 k 에 대해 promise-MA, MA/1 ⊄ SIZE(n^k)) | https://eccc.weizmann.ac.il/report/2007/005/download | ||
| Santhanam 증명의 핵심 부품: 자기 교정·하향 자기 환원 가능한 PSPACE 완전 문제 | 맞음 (Trevisan–Vadhan 의 언어) | https://eccc.weizmann.ac.il/report/2007/005/download | ||
| Buhrman–Fortnow–Thierauf: MA_EXP ⊄ P/poly, 비상대화 | 맞음 (CCC 1998, 반대 오라클 함께 제시) | https://eccc.weizmann.ac.il/report/2008/005/download | ||
| IKW: NEXP ⊆ P/poly 이면 NEXP = MA | 맞음 (JCSS 2002, 「In search of an easy witness」) | https://people.csail.mit.edu/rrw/circuit.pdf | ||
| Vinodchandran: PP 하한 | 맞음 (PP ⊄ SIZE(n^k), TCS 2005; Aaronson 이 비상대화임을 보임) | https://eccc.weizmann.ac.il/report/2008/005/download | ||
| Lipton 의 permanent 무작위 자기 환원, GKR 위임 계산, Sengupta 의 S2P 판 Karp–Lipton | 맞음 (1991 / STOC 2008 / Cai 2007 수록) | https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem | ||
| Feigenbaum–Fortnow: NP 완전 문제의 무작위 자기 환원은 PH 붕괴 없이는 어렵다 | 조건 빠짐 — 정리는 비적응(non-adaptive) 무작위 자기 환원에 대한 것이다(PH 가 3단계로 붕괴). 적응적 환원은 열려 있다 | https://lance.fortnow.com/papers/files/rsr.pdf | ||
| 산술화는 비상대화지만 대수화 장벽 안쪽(Aaronson–Wigderson), IKK 공리화, affine relativization | 맞음 (AW 2008/2009, IKK STOC 2009, Aydınlıoğlu–Bach 2018) | https://eccc.weizmann.ac.il/report/2008/005/download | ||
| (빠진 사실) 전선을 NP 쪽으로 내리는 데 필요한 것 | Aaronson–Wigderson 은 Ã 와 A 를 골라 NP^Ã ⊆ SIZE^A(n) 인 세계를 만들어, NP 에 대한 초선형 회로 하한조차 비대수화 기법이 필요함을 보였고 「대수화가 PromiseMA 에서는 되고 NP 에서는 안 되는 까닭을 정확히 설명한다」고 적었다. 이 글의 주 트랙 목표 지점이 바로 여기다 | https://eccc.weizmann.ac.il/report/2008/005/download | ||
| 「NEXP/MA 수준 하한과 NP 수준 하한 사이 간극의 원인이 『NP 완전 문제의 자기 교정성 부재』라는 단일 질문으로 정리된다」 | 이 글의 가설인데 사실처럼 단정함. 알려진 설명(위의 대수화)과 나란히 놓아야 한다 | https://eccc.weizmann.ac.il/report/2008/005/download | ||
| 「위의 균일 회로 하한들」 | 용어 오기 — Santhanam·BFT·Vinodchandran 결과는 균일 클래스(MA, PP, MA_EXP)에 대한 비균일 회로 하한이다 | https://eccc.weizmann.ac.il/report/2008/005/download | ||
| P=NP 귀결: PH 붕괴, 최적 증명 체계 존재 등 | 맞음 (P=NP 면 TAUT ∈ P 이므로 다항 유계 증명 체계가 존재) | https://en.wikipedia.org/wiki/Propositional_proof_system |
고칠 곳
- 핵심 정리 1번째 줄 · 개요 첫 문장
- 원문: 「SAT 는 하향 자기 환원성을 가진다: 판정 오라클만 주어지면 만족 배정 자체를 다항 시간에 복원할 수 있다.」
- 제안: 「SAT 는 하향 자기 환원성을 가진다(길이 n 인스턴스의 판정이 변수 하나를 고정한 더 작은 인스턴스들의 판정으로 환원된다). 그 결과 판정 오라클만 주어지면 만족 배정 자체를 다항 시간에 복원할 수 있다(탐색-판정 환원).」
- 개요 셋째 문단 · 2단계 · 「문제의 압축이 구체적이다」 문단(Levin)
- 원문(2단계): 「"P=NP는 U가 다항 시간에 도는 것과 동치"임을 체커로 감싼 형태로 정식화한다.」
- 제안: 「"P=NP 는 U 가 만족 가능한 입력에서 다항 시간에 배정을 찾는 것과 동치"임을 체커로 감싼 형태로 정식화한다(불만족 입력에서 U 는 끝나지 않으며, 상수 배 손실의 상수는 경쟁 알고리즘 길이에 지수적이다).」
- 원문(가치): 「이 관점에서 나오는 부분 명제는 모두 무조건적이다.」
- 제안: 「이 관점에서 무조건적인 부분 명제를 끌어내는 것을 목표로 한다 — 다만 U 의 실행 시간 분석 자체는 P vs NP 와 같은 난이도다.」
- 4단계(Feigenbaum–Fortnow)
- 원문: 「NP 완전 문제의 무작위 자기 환원은 다항 위계 붕괴 없이는 어렵다는 Feigenbaum-Fortnow 장벽이 있으므로,」
- 제안: 「NP 완전 문제가 비적응적으로 무작위 자기 환원 가능하면 다항 위계가 3단계로 붕괴한다는 Feigenbaum–Fortnow 장벽이 있으므로(적응적 환원·리스트 교정 등은 이 정리 밖이다),」
- 「병목 질문이 하나로 수렴한다」 문단 · 6단계 · 장벽 표 대수화 칸(알려진 대수화 결과 반영 — 가장 중요)
- 원문: 「NEXP/MA 수준에는 하한이 있고 NP 수준에는 없다는 현재 간극의 원인이 "NP 완전 문제의 자기 교정성 부재"라는 단일 질문으로 정리되고,」
- 제안: 「NEXP/MA 수준에는 하한이 있고 NP 수준에는 없다는 현재 간극은 Aaronson–Wigderson 이 이미 대수화로 설명했다 — NP 에 대한 초선형 회로 하한(NP ⊄ SIZE(n))조차 비대수화 기법이 필요하다. 이 글은 그 간극을 『NP 완전 문제의 자기 교정성 부재』라는 질문으로 다시 정리해 보자는 가설을 세우며,」
- 6단계 원문: 「어느 단계부터 비대수화 성분이 필수가 되는지 명시적으로 표시한다.」 → 「어느 단계부터 비대수화 성분이 필수가 되는지 명시적으로 표시한다 — 최종 목표인 NP 수준 고정 다항 하한은 이미 비대수화 성분이 필수임이 알려져 있으므로(Aaronson–Wigderson), 그 앞 단계들의 위치를 정하는 것이 일이다.」
- 「왜 해볼 만한가」 장벽 문단 · 장벽 표 상대화 칸
- 원문: 「IP=PSPACE, MIP=NEXP와 위의 균일 회로 하한들처럼」
- 제안: 「IP=PSPACE, MIP=NEXP 와 위의 균일 클래스(MA·PP·MA_EXP)에 대한 회로 하한들처럼」
고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.
이 글에 단 답 0
아직 없습니다.