보완
사실 검토 — 작은 수정 후 가능
2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.
판정: 작은 수정 후 가능
인용 문헌 자체(저자·결과)는 대부분 맞다. 다만 LRS 하한을 「대칭 SDP」 한정 결과로 잘못 적었고, 그 오기를 전제로 2단계 마일스톤과 「가치」 절의 「비대칭 SDP 로 확장」이 세워져 있다(LRS 는 이미 임의 SDP 에 대한 결과다). 같은 글 안의 「가치」 절 첫 문장은 대칭 없이 「다항 크기 SDP 완화 전부」라고 적어 앞뒤가 어긋난다.
확인한 사실
| 주장 | 사실 여부 | 근거 링크 |
|---|---|---|
| SoS/Lasserre 위계가 스펙트럴·LP·SDP·대다수 근사 알고리즘을 포섭, 「이 모델의 하한은 그 알고리즘 클래스 전체의 실패」 | 과장. Sherali–Adams·기본 SDP 는 저차 SoS 에 포섭되지만 「스펙트럴 방법 전부」가 포섭된다는 일반 정리는 없다. SoS 차수 d 하한은 그 차수의 SoS 와 그로 표현되는 알고리즘의 실패를 뜻할 뿐이다 | Fleming–Kothari–Pitassi 서베이 |
| Grigoriev·Schoenebeck 의 무작위 3-SAT 차수 하한 | 대체로 맞음. Grigoriev(2001)는 패리티(Tseitin·3-XOR)에 대한 선형 차수 하한, Schoenebeck(FOCS 2008)는 3-XOR 에 함의되는 술어(3-SAT 포함)의 무작위 k-CSP 에 Ω(n) 단계 Lasserre 하한 | Schoenebeck 2008 |
| 유사보정에 의한 심은 클리크 하한(BHKKMP) | 맞음. Barak–Hopkins–Kelner–Kothari–Moitra–Potechin, 차수 d=o(log n) 에서 n^(1/2−o(1)) | arXiv 1604.03084 |
| LRS 가 「다항 크기 대칭 SDP 완화 전부」를 배제 | 틀림. Lee–Raghavendra–Steurer(STOC 2015)는 대칭 가정 없는 임의 SDP 에 대해 cut·TSP·안정 집합 다면체의 SDP 확장 복잡도 2^(n^δ) 하한, 최대 CSP 에서 다항 크기 SDP ≡ 상수 차수 SoS 를 증명. 대칭 한정 결과는 그 전의 Lee–Raghavendra–Steurer–Tan(CCC 2014) | LRS arXiv 1411.6317 · LRST 2014 |
| SoS 가 가우스 소거(패리티)를 놓친다(Grigoriev) | 맞음 | Schoenebeck 2008 서론 |
| Grigoriev 의 냅색 차수 하한 | 맞음(Computational Complexity 10, 2001) | Fleming–Kothari–Pitassi |
| Raghavendra 의 UGC 하 CSP 최적성 | 맞음(STOC 2008, 조건부 — UGC) | Fleming–Kothari–Pitassi |
| Kothari–Meka–Raghavendra 의 LP 하한 | 맞음(STOC 2017, CSP 의 LP 완화에 대한 준지수 하한) | Fleming–Kothari–Pitassi |
| Fleming–Kothari–Pitassi 준대수 증명·알고리즘 설계 서베이 | 맞음(FnT TCS 14(1–2), 2019) | nowpublishers TCS-086 |
| 「차수 하한을 크기 하한으로 승격하는 기계장치」를 정비해야 한다 | 일부 이미 있음. 증명 체계 쪽은 Atserias–Hakoniemi(CCC 2019) 크기-차수 절충으로, 선형 차수 하한(무작위 3-CNF·Tseitin)에서 SoS 지수 크기 하한이 이미 나온다 | arXiv 1811.01351 |
| 「크기(비트 복잡도) 하한」 | 용어 혼동. SDP 확장 정식화의 크기는 PSD 콘 차원, 증명 체계의 크기는 단항식 수이며, 비트 복잡도는 별개 축이다 | LRS · Atserias–Hakoniemi |
| IP=PSPACE 의 산술화가 「장벽 밖에서 작동하는 기법」 | 반만 맞음. 산술화는 상대화 장벽 밖이지만 대수화 장벽 안이다(대수화 장벽이 바로 산술화를 겨냥) | Aaronson–Wigderson |
| 유사보정·저차수 방법이 원웨이 함수류 가정과 「연결된다」 | 단정할 근거 부족 — 연구 방향(추측)이다 | — |
| SoS 로 강건 통계·텐서 분해 알고리즘이 발굴됨 | 맞음 | Fleming–Kothari–Pitassi |
고칠 곳
- 아이디어 개요 첫 문단
- 원문: 「Lee–Raghavendra–Steurer(LRS)의 SDP 확장 정식화 하한처럼 "다항 크기 대칭 SDP 완화 전부"를 배제하는 무조건적 결과들이 이미 축적되어 있다.」
- 제안: 「Lee–Raghavendra–Steurer(LRS, STOC 2015)의 SDP 확장 정식화 하한처럼 "최대 CSP 근사와 cut·TSP·안정 집합 다면체에 대해 다항 크기 SDP 완화 전부"(대칭성 가정 없음)를 배제하는 무조건적 결과들이 이미 축적되어 있다.」
- 구체적 진행 방법 2단계(차수-크기 대장)
- 원문: 「LRS 기계장치가 차수 하한을 어떤 손실로 크기 하한으로 변환하는지, 어디서 대칭성 가정이 필수로 쓰이는지 명세화한다. 중간 마일스톤: 비대칭 SDP 완화가 현재 하한을 빠져나가는 정확한 지점을 서술한 기술 노트.」
- 제안: 「LRS 기계장치가 차수 하한을 어떤 손실로 일반 SDP 의 크기 하한으로 변환하는지, 대칭성 가정이 필요했던 이전 결과(Lee–Raghavendra–Steurer–Tan, CCC 2014)와 무엇이 달라졌는지 명세화한다. 중간 마일스톤: LRS 하한이 덮지 않는 문제군과 크기 지수(2^(n^δ))의 손실을 서술한 기술 노트.」
- 같은 단계의 「차수 하한인가, 크기(비트 복잡도) 하한인가」 → 「차수 하한인가, 크기 하한인가(SDP 확장 정식화의 차원과 증명 체계의 단항식 수를 구분하고, 비트 복잡도는 별도 축으로 둔다)」.
- 왜 해볼 만한가 — 무조건적 성과의 축적
- 원문: 「같은 종류의 확장(비대칭 SDP, 더 넓은 문제군)은 그 자체로 일급 성과가 된다.」
- 제안: 「같은 종류의 확장(더 넓은 문제군, 더 강한 크기 지수)은 그 자체로 일급 성과가 된다.」
- 핵심 정리 첫 줄과 개요의 같은 문장
- 원문: 「— 이 모델의 하한은 그 알고리즘 클래스 전체의 실패를 뜻한다.」 / 「이 모델에 대한 차수·크기 하한은 곧 그 방대한 알고리즘 클래스 전체의 실패를 뜻한다.」
- 제안: 「— 이 모델의 하한은 그 위계로 표현되는 알고리즘들(해당 차수 이하)의 실패를 뜻한다. 스펙트럴 방법 전반이 저차 SoS 로 포획된다는 것은 많은 사례에서 확인된 경향이지 일반 정리는 아니다.」
- 5단계(증명 복잡도 다리 놓기) — 이미 알려진 결과 표시
- 원문 끝에 덧붙임: 「무작위 3-CNF·Tseitin 식에 대한 SoS 지수 크기 하한은 Atserias–Hakoniemi(CCC 2019)의 크기-차수 절충과 Grigoriev·Schoenebeck 차수 하한으로 이미 알려져 있다.」
- 왜 해볼 만한가 — 장벽 프로필
- 원문: 「IP=PSPACE의 산술화가 그랬듯 "장벽 밖에서 실제로 작동하는 기법"을 키우는 일이며」
- 제안: 「IP=PSPACE의 산술화가 상대화 장벽 밖에서 작동했듯(산술화 자체는 대수화 장벽 안에 있다) "장벽 밖에서 실제로 작동하는 기법"을 키우는 일이라고 본다.」
- 왜 해볼 만한가 — 평균 사례·암호와의 접점
- 원문: 「유사보정과 저차수 방법의 대응은 심은 문제의 평균 사례 난이도, 나아가 원웨이 함수류 가정과 연결된다.」
- 제안: 「유사보정과 저차수 방법의 대응은 심은 문제의 평균 사례 난이도와 연결되며, 원웨이 함수류 가정과도 이어질 수 있다는 것이 이 글의 기대다.」
- (선택) 「Grigoriev와 Schoenebeck의 무작위 3-SAT 차수 하한」 → 「Grigoriev(2001, 패리티·3-XOR)와 Schoenebeck(2008, 3-SAT 포함)의 선형 차수 하한」.
고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.
이 글에 단 답 0
아직 없습니다.