보완
사실 검토 — 작은 수정 후 가능
2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.
판정: 작은 수정 후 가능
SAT 알고리즘 계보(Monien–Speckenmeyer → Schöning → PPSZ → 편향 PPSZ), CSP 이분법(Bulatov·Zhuk), SETH 서술은 맞다. 문제는 이 글의 핵심 근거인 「양면 보상」 문장들이다: ① Williams 연결은 회로 SAT(Circuit-SAT, 특정 회로 클래스 C 의 SAT) 알고리즘에 대한 것이고 3-SAT/k-SAT 밑수 개선은 그 연결로 새 하한을 주지 않는다 ② 미세 복잡도의 환원은 「SAT 개선이 다른 문제로 전파」되는 방향이 아니라 반대 방향이다 ③ 이분법상 P 밖의 CSP 템플릿에 준지수·준다항 알고리즘이 생기면 그것은 곧 ETH 반증이라는 점이 빠져 있다.
확인한 사실
| 주장 | 사실 여부 | 근거 링크 |
|---|---|---|
| 3-SAT 상계: 2^n → 분기(Monien–Speckenmeyer) → 국소탐색(Schöning) → PPSZ 계열 | 맞음 (Monien–Speckenmeyer, Discrete Appl. Math. 1985, 약 1.619^n / Schöning FOCS 1999, (4/3)^n / Paturi–Pudlák–Saks–Zane FOCS 1998·J. ACM 2005) | https://en.wikipedia.org/wiki/Exponential_time_hypothesis |
| 「편향 PPSZ」 | 맞음 — Hansen–Kaplan–Zamir–Zwick, 「Faster k-SAT algorithms using biased-PPSZ」, STOC 2019 (모든 k≥3 에서 PPSZ 개선, Unique 3-SAT 1.308^n → 1.307^n) | https://people.csail.mit.edu/virgi/6.1420/papers/fasterksat.pdf |
| 「다항식 방법(polynomial method)에 이르는 k-SAT/CSP 지수 상계 개선사」 | 부정확 — 다항식 방법(Williams 계열)은 ACC0-SAT·직교 벡터·APSP·유한체 다항식 연립 등의 개선에 쓰였고, k-SAT 지수 밑수의 계보는 PPSZ 계열이 이끈다 | https://people.csail.mit.edu/rrw/improved-algs-lbs2.pdf (Williams 계열 개관) |
| Williams 의 「알고리즘에서 회로 하한으로」 — 충분히 빠른 SAT류 알고리즘이 회로 하한을 함의 | 조건을 붙이면 맞음 — 일반 회로 SAT 를 2^n/n^{ω(1)} 시간에 풀면 NEXP ⊄ P/poly (STOC 2010 / SICOMP 2013), ACC0 회로 SAT 의 비자명 알고리즘 → NEXP ⊄ ACC0 (2011). 대상은 회로 클래스 C 의 SAT 이며 결론은 NEXP(이후 NQP·E^NP) 대 C 하한이다. CNF(3-SAT·k-SAT)는 깊이 2 클래스라 그 SAT 개선은 이 연결로 새 하한을 주지 않는다 | https://people.csail.mit.edu/rrw/improved-algs-lbs2.pdf · https://arxiv.org/abs/1311.3171 |
| 「부분 성공에 그쳐도 하한 쪽 증거가 축적」 | 과장 — 위 사유로 k-SAT 밑수 개선 자체는 하한을 주지 않는다. 회로 클래스 SAT 가속(진행 방법 7의 예)일 때만 해당 | 위 링크 |
| CSP 이분법 — Bulatov–Zhuk | 맞음 (Bulatov arXiv 1703.03021, Zhuk arXiv 1704.01914, 둘 다 FOCS 2017; Feder–Vardi 추측 해결). 유한 정의역 템플릿 CSP(Γ)는 P 이거나 NP-완전 | https://arxiv.org/abs/1704.01914 · https://arxiv.org/abs/1703.03021 |
| 「CSP 이분법은 다항 시간 섬의 경계를 대수 조건으로 완결해 준 희귀한 사례」 | 맞음 (약한 근사 만장일치 WNU 다형사상 유무) | https://arxiv.org/abs/1704.01914 |
| 「다항 시간을 보장하는 대수 조건보다 약한 조건 아래에서 준지수·준다항 알고리즘이 성립하는 계층」·「지수와 다항 사이의 중간 계층을 조밀하게 채우는 것」 | 표시 없는 어긋남 — 이분법상 그런 템플릿은 NP-완전이므로 준다항 알고리즘은 곧 NP ⊆ QP(ETH 반증)이고, 3-SAT 에서 선형 크기 환원(희소화 + pp-구성)이 있으므로 2^{o(n)} 알고리즘도 ETH 반증이다(검토자 추론 — 표준 논증). 즉 템플릿 축의 「중간 계층」은 ETH 가 거짓일 때만 존재한다. 인스턴스 구조 축(트리폭·백도어)의 중간 계층은 문제없음 | https://en.wikipedia.org/wiki/Exponential_time_hypothesis |
| SETH: k 가 커져도 사라지지 않는 절약을 금지 | 맞음 (모든 ε>0 에 대해 어떤 k 에서 k-SAT 가 2^{(1-ε)n} 시간에 안 풀린다 — Impagliazzo–Paturi 2001) | https://en.wikipedia.org/wiki/Exponential_time_hypothesis |
| 「미세 복잡도 분야의 환원 네트워크 덕분에 하나의 개선이 수십 개 문제로 전파」 | 방향이 반대 — SETH 기반 환원은 CNF-SAT → (직교 벡터·편집 거리 등)이므로 「그 문제들의 개선 → SETH 반증」이다. SAT(특히 3-SAT 밑수)의 개선은 그 문제들의 알고리즘을 빠르게 하지 않는다. SETH 가 반증되면 그 문제들의 조건부 하한의 근거가 사라질 뿐 | https://en.wikipedia.org/wiki/Exponential_time_hypothesis |
| 「성공하면 ETH/SETH 반증 또는 그 이상」 | 맞음 (방향 3·SETH 우선 공략 자체가 그 목표) | — |
| 글 안 순서 대조 — 「6·7단계에 의해 장벽의 정식화와 회로 하한 증거」 | 맞음 (6 = 장벽 대장, 7 = 알고리즘-하한 변환) | 본문 |
| 「장벽 대장 자체가 P≠NP 쪽 증거 자산」 | 이 글의 제안·판단 — 사실 문장처럼 쓰여 있음 | — |
고칠 곳
- 원문(핵심 정리 3): 「Williams 의 「알고리즘에서 회로 하한으로」 연결: 충분히 빠른 SAT류 알고리즘의 존재 자체가 회로 하한을 함의한다.」
→ 제안: 「Williams 의 「알고리즘에서 회로 하한으로」 연결: 어떤 회로 클래스 C 의 회로 SAT 를 전수탐색보다 초다항 배 빠르게 푸는 알고리즘이 있으면 NEXP ⊄ C 같은 회로 하한이 따른다. 3-SAT·k-SAT(CNF) 밑수 개선은 이 연결만으로는 새 하한을 주지 않는다.」 (아이디어 개요 3문단의 같은 문장도) - 원문(요약·핵심 정리 4·개요): 「부분 성공에 그쳐도 하한 쪽 증거가 축적된다」
→ 제안: 「부분 성공이 회로 클래스 SAT 의 가속으로 이어지면 하한 쪽 성과가 된다(이 글의 기대이며, k-SAT 밑수 개선만으로는 해당하지 않는다).」 - 원문(진행 방법 1): 「2^n에서 분기 알고리즘, 국소탐색, PPSZ, 편향 PPSZ, 다항식 방법(polynomial method)에 이르는 k-SAT/CSP 지수 상계 개선사」
→ 제안: 「2^n 에서 분기 알고리즘, 국소탐색, PPSZ, 편향 PPSZ 에 이르는 k-SAT 지수 상계 개선사와, 다항식 방법이 연 회로 클래스 SAT·CSP 변형의 개선사」 - 원문(진행 방법 3): 「다항 시간을 보장하는 대수 조건보다 약한 조건 아래에서 준지수·준다항 알고리즘이 성립하는 계층이 있는지 탐색한다.」
→ 제안 뒤에 한 문장 추가: 「단, 이분법에 따라 그런 템플릿은 NP-완전이므로 여기서 준다항 또는 2^{o(n)} 알고리즘을 얻으면 그것은 곧 ETH 반증이다 — 이 단계는 사실상 3번 경로(ETH 반증)의 한 형태다.」 - 원문(가치 3): 「미세 복잡도(fine-grained complexity) 분야의 환원 네트워크 덕분에 하나의 개선이 수십 개 문제로 전파된다.」
→ 제안: 「미세 복잡도 분야의 환원 네트워크에서 SAT 는 수십 개 문제의 조건부 하한의 출발점이어서, SETH 가 반증되면 그 하한들의 근거가 한꺼번에 사라진다(환원 방향상 SAT 개선이 그 문제들의 알고리즘을 직접 빠르게 하지는 않는다).」 - 원문(진행 방법 6): 「이 장벽 대장 자체가 P≠NP 쪽 증거 자산으로 기능한다.」
→ 제안: 「이 장벽 대장이 P≠NP 쪽 증거 자산이 될 수 있다고 본다.」
넣을 수 있는 문헌 목록 (제안)
- B. Monien, E. Speckenmeyer, Solving satisfiability in less than 2^n steps, Discrete Applied Mathematics 10(3), 1985.
- U. Schöning, A probabilistic algorithm for k-SAT and constraint satisfaction problems, FOCS 1999.
- R. Paturi, P. Pudlák, M. Saks, F. Zane, An improved exponential-time algorithm for k-SAT, FOCS 1998 / J. ACM 52(3), 2005.
- T. D. Hansen, H. Kaplan, O. Zamir, U. Zwick, Faster k-SAT algorithms using biased-PPSZ, STOC 2019.
- R. Impagliazzo, R. Paturi, On the complexity of k-SAT, J. Comput. Syst. Sci. 62(2), 2001.
- A. Bulatov, A dichotomy theorem for nonuniform CSPs, FOCS 2017. / D. Zhuk, A proof of the CSP dichotomy conjecture, FOCS 2017 / J. ACM 2020.
- R. Williams, Improving exhaustive search implies superpolynomial lower bounds, STOC 2010 / SIAM J. Comput. 2013.
- R. Williams, Nonuniform ACC circuit lower bounds, CCC 2011 / J. ACM 2014.
고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.
이 글에 단 답 0
아직 없습니다.