사실 검토 — 보완 필요

2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.

판정: 보완 필요

글의 중심 논리 하나(「UGC + Raghavendra 로 모든 다항 알고리즘 배제가 단일 알고리즘 군의 실패 증명으로 압축된다」)가 알려진 정리의 내용과 어긋난다. 이 주장은 핵심 정리 3번째 줄, 개요 넷째 문단, 2단계·7단계, 「왜 해볼 만한가」의 「목표 압축의 유일한 알려진 통로」에 걸쳐 있어 문장 한두 개 교체로 끝나지 않는다. 아래 「고칠 곳」의 대체 문장으로 바꾸고 7단계 목표를 다시 적어야 한다.

확인한 사실

고칠 곳

1. 개요 첫 문단(7/8 동치 오기)
   • 원문: 「실제로 PCP 정리는 MAX-3SAT를 7/8+ε 비율보다 잘 근사하는 것이 NP-난해하다는 갭 문제 난해성과 동치이므로(Håstad의 최적 비근사성까지 포함하면 갭의 위치도 최적으로 고정된다),」
   • 제안: 「실제로 PCP 정리는 『어떤 상수 ρ<1 에 대해 MAX-3SAT 를 ρ 비율로 근사하는 것이 NP-난해하다』는 갭 문제 난해성과 동치이며, Håstad(2001)는 그 문턱을 7/8+ε 로 끌어올려 갭의 위치를 최적으로 고정했다. 따라서」
2. 핵심 정리 3번째 줄 · 개요 넷째 문단(Raghavendra 압축 — 가장 중요)
   • 원문(핵심 정리): 「UGC 가 참이라면 Raghavendra 정리에 의해 기본 SDP 완화가 사실상 최적 알고리즘이 되어, 「모든 다항 알고리즘의 배제」가 「단일 알고리즘 군의 실패 증명」으로 압축된다.」
   • 제안: 「UGC 가 참이라면 Raghavendra 정리에 의해 『기본 SDP 보다 잘 근사하는 다항 알고리즘이 있으면 P=NP』가 된다. 이 최적성은 P≠NP 를 전제로 한 결론이라 SDP 의 실패(적분성 갭)만으로 P≠NP 가 나오지는 않는다. 이 글은 이 정리를 『갭 지도의 경계선을 SDP 적분성 갭 곡선으로 고정하는 기준선』으로 쓴다.」
   • 원문(개요): 「특히 UGC가 참이라면 … "모든 다항 알고리즘의 배제"라는 막막한 목표가 "단일 알고리즘 군의 실패 증명"으로 압축되는 통로가 열린다.」
   • 제안: 「특히 UGC 가 참이라면 Raghavendra 정리에 의해 모든 CSP 에서 기본 SDP 가 (P≠NP 아래) 최적이 되므로, 갭 지도의 경계가 하나의 알고리즘 군의 성능 곡선으로 정확히 그려진다. 다만 이것은 P≠NP 를 단일 알고리즘의 실패로 바꿔 주지 않는다 — SDP 를 넘는 다항 알고리즘이 없음을 보이는 일이 곧 (UGC 아래) P≠NP 이기 때문이다.」
3. 「왜 해볼 만한가」 — 「목표 압축의 유일한 알려진 통로」 문단
   • 원문: 「UGC + Raghavendra 최적성은 "모든 다항 알고리즘"이라는 무한한 상대를 "기본 SDP 한 개"로 압축하는, 현재 알려진 거의 유일한 메커니즘이다.」
   • 제안: 「UGC + Raghavendra 최적성은 근사 난이도의 경계를 『기본 SDP 한 개의 성능』으로 정확히 그려 주는, 현재 알려진 거의 유일한 통일 원리다(단 이는 P≠NP 를 전제로 한 최적성이다).」 — 문단 제목도 「목표 압축」 대신 「경계선의 통일 원리」 등으로 바꾼다.
4. 7단계(종합 명제) — 「갭 재정식화 + 알고리즘 최적성(UGC 조건부) + 제한 모델 무조건 하한」 세 부품이 맞물려 P≠NP 에 도달한다는 그림은, 제한 모델 하한(SoS·LP·SDP)이 특정 알고리즘 군에 대한 하한이고 Raghavendra 최적성이 P≠NP 를 전제로 하므로 그대로는 닫히지 않는다. 「세 부품이 맞물려도 무엇이 여전히 P≠NP 와 동치인 채로 남는지를 명시하는 것」으로 목표 문장을 바꾸기를 권한다.
5. 1단계
   • 원문: 「Raz 병렬 반복(및 Holenstein, Rao의 개선·Braverman–Garg의 한계)」
   • 제안: 「Raz 병렬 반복(및 Holenstein·Rao 의 개선, Braverman–Garg 의 작은 값 병렬 반복, Feige–Verbitsky·Raz(2008)의 강한 병렬 반복 반례라는 한계)」
6. 개요 넷째 문단 끝
   • 원문: 「PCP 정리의 증명 자체가 산술화에 기반한 대표적 비상대화 성분이라는 점,」
   • 제안: 「PCP 정리(원래의 대수적 증명은 산술화에 기반한다)가 대표적 비상대화 결과라는 점,」 — 「왜 해볼 만한가」 「상대화 장벽에 대한 내장 우회」의 같은 문장도 「원래의 대수적 증명은」으로 맞춘다.
7. 4단계
   • 원문: 「정확 판정이 아닌 갭 판정에서는 제한 모델 하한이 훨씬 강하고 깔끔하게 성립한다는 점을 정량화하고,」
   • 제안: 「정확 판정보다 갭 판정에서 제한 모델 하한이 더 강하고 깔끔하게 성립하는지(이 글의 가설)를 정량화하고,」
8. (참고 — 판정 반영 안 함) 장벽 표의 상대화 칸: 「비상대화 정리에서 출발한다」는 것만으로 이후 논법이 비상대화가 되지는 않는다. 「판단」으로 표시돼 있어 사실 오류는 아니지만, 「출발점이 비상대화라는 것만으로 이후 논법이 상대화 장벽을 피하는 것은 아니며, 비상대화 성분이 최종 논법에 실제로 쓰이는지를 3단계에서 점검한다」를 덧붙이면 오해가 줄어든다.

고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.