보완
사실 검토 — 작은 수정 후 가능
2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.
판정: 작은 수정 후 가능
지수의 역사(√2 → 황금비 → 2cos(π/7)≈1.8019), Williams 의 LP 자동화, Buss–Williams 한계 정리, van Melkebeek 서베이는 모두 맞다. 고칠 것은 ① 마일스톤 순서 오류 — 임의 상수 c 하한은 NP ⊄ SC 를 주고, L ⊆ SC 이므로 L ≠ NP 는 그 따름정리인데 그 다음 단계(「나아가」·「최종적으로」)로 적었다 ② 상대화 관련 단정 — 감속 보조정리는 상대화하지만 표준 공간 제한 오라클 모델에는 기존 하한 자체가 성립하지 않는 오라클이 있어(해석에 이견 있음) 「대체로 상대화」·「발목 잡는 지점이 명시적으로 알려져」는 근거가 없다. 현재 틀의 한계로 증명된 것은 Buss–Williams 다 ③ 「SAT 의 준선형 시간 완전성」을 새 성분 후보로 적었지만 이미 기존 모든 증명이 쓰는 성분이다.
확인한 사실
| 주장 | 사실 여부 | 근거 링크 |
|---|---|---|
| SAT 를 n^c 시간·n^o(1) 공간에서 풀 수 없음(무조건), c: √2(Lipton–Viglas) → 황금비(Fortnow–van Melkebeek) → 2cos(π/7)≈1.8019(Williams) | 맞음(모든 c < 2cos(π/7)). 2cos(π/7) 은 Williams CCC 2007 | Williams ECCC TR07-036 · van Melkebeek 서베이 |
| Williams 가 증명 탐색을 LP 로 자동화 | 맞음(Alternation-Trading Proofs, Linear Programming, and Lower Bounds) | arXiv 1001.0746 |
| Buss–Williams: 표준 교대 절충 증명으로는 2cos(π/7) 을 넘을 수 없음 | 맞음(CCC 2012, Computational Complexity 24(3) 2015) | ECCC TR11-031 |
| 임의 상수 c 하한 = NP 와 SC 의 분리, 「나아가 L ≠ NP」 | 순서 오류. n^o(1) 공간·임의 c 하한이면 SAT ∉ DTISP(poly, polylog) = SC 이고, L ⊆ SC 이므로 L ≠ NP 는 바로 따라온다. Williams 도 「지수를 임의 상수로 올리면 LOGSPACE 와 NP 가 분리된다」고 적는다 | arXiv 1001.0746 서론 |
| 「교대 절충 논법은 대체로 상대화」, 「상대화 장벽이 현재 틀의 발목을 잡는 지점이 명시적으로 알려져 있다」 | 근거 부족·일부 반대 증거. 감속 보조정리는 상대화한다(Williams 2010). 그러나 표준 공간 제한 오라클 모델에는 NTIME^A[n] ⊆ TS^A[n^1.1, log n] 인 오라클 A 가 있어, 기존 하한 자체가 그 의미로는 상대화하지 않는다(Williams 2018 강의 노트 — 이 해석에 이견이 있다고 노트가 함께 적음). 현재 틀의 한계로 증명된 것은 상대화 장벽이 아니라 Buss–Williams 다 | Williams CS294 강의 노트 1 · arXiv 1001.0746 |
| 새 규칙 후보 (b) 「SAT 의 준선형 시간 완전성(초효율 Cook 정리)」 | 새 성분이 아님 — NTIME(n) 하한을 SAT 로 옮기는 데 기존 모든 증명이 이미 쓴다(Fortnow–Lipton–van Melkebeek–Viglas, JACM 2005) | van Melkebeek 서베이 |
| Nepomnjascii형 속도향상, 귀류 가정으로 교대를 줄이는 감속 | 맞음(서베이의 틀 그대로) | van Melkebeek 서베이 |
| 무작위 기계 하한(Diehl–van Melkebeek) | 맞음(ICALP 2005, SICOMP 2006) | van Melkebeek 서베이 |
| 비결정 모델 tautology 하한(Fortnow–van Melkebeek) | 맞음. 현재 최고는 Diehl–van Melkebeek–Williams 의 4^(1/3)≈1.587 이며 Williams 가 φ 를 넘을 수 없음도 보였다 | arXiv 1001.0746 |
| 회로가 아닌 균일 모델 하한이라 자연 증명 장벽이 적용되지 않음 | 대체로 맞음(자연 증명은 비균일 회로 하한에 대한 장벽) | Natural proof (Wikipedia) |
고칠 곳
- 핵심 정리 넷째 줄
- 원문: 「마일스톤 사다리: 2cos(pi/7) 을 넘는 첫 개선 → c=2 → 임의 상수 c(NP 와 SC 의 분리) → L ≠ NP.」
- 제안: 「마일스톤 사다리: 2cos(pi/7) 을 넘는 첫 개선 → c=2 → 임의 상수 c(NP ⊄ SC — L ⊆ SC 이므로 L ≠ NP 도 함께 따른다).」
- 아이디어 개요 셋째 문단
- 원문: 「궁극적으로 임의의 상수 c에 대한 하한 — 즉 NP가 다항시간·폴리로그 공간 계산(SC)에 속하지 않는다는 분리, 나아가 L ≠ NP — 을 향해」
- 제안: 「궁극적으로 임의의 상수 c에 대한 하한 — 즉 NP가 다항시간·폴리로그 공간 계산(SC)에 속하지 않는다는 분리와 그 따름정리 L ≠ NP — 을 향해」
- 6단계(중간 마일스톤 사다리)와 그림 설명
- 원문: 「(iv) 임의 상수 c 도달로 NP와 SC 계열의 분리, (v) 최종적으로 L ≠ NP.」
- 제안: 「(iv) 임의 상수 c 도달로 NP ⊄ SC 와 그 따름정리 L ≠ NP.」 그림 설명 「플럼색은 6단계 마일스톤 (ii)~(v) 다」 → 「(ii)~(iv)」.
- 아이디어 개요 셋째 문단
- 원문: 「상대화 장벽이 현재 틀의 발목을 잡는 지점이 명시적으로 알려져 있어 새 성분을 어디에 주입할지 목표가 구체적이라는 점이 이 경로의 강점이다.」
- 제안: 「현재 틀의 한계가 Buss–Williams 정리로 정확히 그려져 있어 새 성분을 어디에 주입할지 목표가 구체적이라는 점이 이 경로의 강점이다.」
- 왜 해볼 만한가 — 상대화·대수화 장벽이 나침반 역할(판단 표시 없이 단정) / 장벽 표 상대화 행
- 원문: 「교대 절충 논법은 대체로 상대화하므로 지수를 크게 밀어 올리려면 비상대화 성분이 필수이고, 그 주입 지점(SAT의 초효율 완전성, 산술화, 알고리즘적 방법)이 구체적으로 알려져 있다.」
- 제안: 「교대 절충 논법과 상대화의 관계는 오라클 접근 방식에 따라 다르다 — 감속 보조정리는 상대화하지만, 표준 공간 제한 오라클 모델에는 NTIME^A[n] ⊆ TS^A[n^1.1, log n] 인 오라클이 있어 기존 하한은 그 의미로는 이미 상대화하지 않는다(해석에 이견 있음). 이 글은 산술화·알고리즘적 방법을 새 성분 후보로 본다.」
- 4단계 (b)
- 원문: 「(b) 비상대화 성분 주입 — SAT의 준선형 시간 완전성(초효율 Cook 정리), IP=PSPACE류 산술화, …」
- 제안: 「(b) 비상대화 성분 주입 — SAT의 준선형 시간 완전성(초효율 Cook 정리 — 기존 증명은 이것을 하한을 SAT 로 옮기는 데만 쓴다)의 새 쓰임, IP=PSPACE류 산술화, …」
- (선택) 5단계 tautology 에 「현재 최고 4^(1/3)≈1.587(Diehl–van Melkebeek–Williams)」 덧붙임.
고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.
이 글에 단 답 0
아직 없습니다.