PCP 갭 재정식화 경로

하위 정보 2

이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.

보완 2

• 보완#70사실 검토 — 보완 필요
  • 관리자
  • 2026-10-07 13:04
  • AI 도움

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

  판정: 보완 필요

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

  확인한 사실

  주장	사실 여부	근거 링크
  PCP 정리(Arora–Safra, Arora–Lund–Motwani–Sudan–Szegedy): NP = PCP(log n, O(1))	맞음(1992 FOCS, 1998 JACM 두 편). 표기는 보통 PCP(O(log n), O(1))	https://en.wikipedia.org/wiki/PCP_theorem
  P≠NP 는 「특정 갭-CSP 를 다항 시간에 푸는 알고리즘이 없다」와 정확히 같다	맞음 — 갭-3SAT(만족 가능 대 1−ε 이하)는 PCP 정리로 NP-난해하고 NP 에 속하므로 P≠NP ⟺ 그 갭 문제 ∉ P	https://en.wikipedia.org/wiki/PCP_theorem
  「PCP 정리는 MAX-3SAT 를 7/8+ε 보다 잘 근사하는 것이 NP-난해하다는 갭 문제 난해성과 동치」	틀림 — PCP 정리와 동치인 것은 「어떤 상수 ρ<1 에 대해 MAX-3SAT ρ-근사가 NP-난해」다. 7/8+ε 문턱은 Håstad(2001 JACM)의 별도 정리이며 PCP 정리보다 강하다. 글이 괄호에서 Håstad 를 따로 언급해 앞뒤가 엉켰다	https://theory.cs.princeton.edu/complexity/hastadchap.pdf · https://en.wikipedia.org/wiki/MAX-3SAT
  Håstad 3-비트 PCP(롱 코드 + 푸리에 분석), 7/8 최적 비근사성	맞음 (Håstad, "Some optimal inapproximability results", JACM 2001)	https://theory.cs.princeton.edu/complexity/hastadchap.pdf
  Dinur 의 조합적 갭 증폭 증명	맞음 (Dinur, JACM 2007)	https://en.wikipedia.org/wiki/PCP_theorem
  Raz 의 병렬 반복, Holenstein·Rao 의 개선	맞음 (Raz SICOMP 1998, Holenstein STOC 2007, Rao STOC 2008)	https://www.wisdom.weizmann.ac.il/~oded/MC/002.html
  「Braverman–Garg 의 한계」	틀림(공로 오기) — Braverman–Garg(ECCC TR14-095, STOC 2015)는 일반 게임의 작은 값 병렬 반복 정리(긍정 결과)이고 Holenstein·Rao 정리의 대체 증명도 준다. 병렬 반복의 대표적 「한계」는 Feige–Verbitsky 예와 Raz(2008)의 강한 병렬 반복 반례다	https://eccc.weizmann.ac.il/report/2014/095 · https://epubs.siam.org/doi/10.1137/090747270
  Khot–Minzer–Safra 의 2-대-2 게임 정리, 그라스만 그래프	맞음(완전성 불완전판). 다만 증명은 Khot–Minzer–Safra(2017), Dinur–Khot–Kindler–Minzer–Safra(2018), Barak–Kothari–Steurer, Khot–Minzer–Safra(FOCS 2018 / Annals 2023)로 이어진 연작이다	https://annals.math.princeton.edu/2023/198-1/p01
  2-대-2 정리가 유니크 게임 본체(완전성 1−ε)에는 아직 닿지 못함	맞음 — 2-대-2 정리는 완전성 약 1/2 의 유니크 게임 NP-난해성을 주며 1−ε 영역(UGC 본체)은 미해결	https://annals.math.princeton.edu/2023/198-1/p01
  UGC 가 참이면 Raghavendra 정리에 의해 기본 SDP 가 모든 CSP 에 대해 최적	맞음, 조건부로 표시됨 (Raghavendra, STOC 2008)	https://cs.utexas.edu/~danama/courses/projection/raghavendra.pdf
  「그래서 모든 다항 알고리즘의 배제가 단일 알고리즘 군의 실패 증명으로 압축된다」	틀림(정리의 귀결을 잘못 읽음) — Raghavendra 정리가 주는 것은 「UGC 아래에서, 기본 SDP 보다 잘 근사하는 다항 알고리즘이 있으면 P=NP」, 즉 SDP 의 최적성은 P≠NP 를 전제로 한 결론이다. SDP 가 실패한다는 것(적분성 갭 사례)은 이미 무조건 알려져 있고, 그것으로는 P≠NP 가 나오지 않는다. 「다른 어떤 다항 알고리즘도 SDP 를 못 넘는다」를 보이는 일이 곧 P≠NP(UGC 아래) 자체다	https://cs.utexas.edu/~danama/courses/projection/raghavendra.pdf
  Arora–Barak–Steurer 의 준지수 알고리즘	맞음 (FOCS 2010, JACM 2015) — exp(n^{ε^c}) 시간	https://en.wikipedia.org/wiki/Unique_games_conjecture
  소집합 확장 가설(SSE)과 UGC 의 함의 관계	맞음 (Raghavendra–Steurer 2010: SSE ⇒ UGC)	https://en.wikipedia.org/wiki/Unique_games_conjecture
  준선형 크기 PCP (Ben-Sasson–Sudan 계열)	맞음 (Ben-Sasson–Sudan SICOMP 2008, 크기 n·polylog n)	https://en.wikipedia.org/wiki/PCP_theorem
  갭-ETH (Dinur, Manurangsi–Raghavendra)	맞음 (Dinur ECCC 2016, Manurangsi–Raghavendra ICALP 2017)	https://en.wikipedia.org/wiki/Exponential_time_hypothesis
  PCP 정리의 증명은 산술화에 기반한 비상대화 성과, IP=PSPACE 와 같은 뿌리	원래의 대수적 증명(AS·ALMSS)에 대해서는 맞음. PCP 정리가 상대화하지 않는다는 것도 맞음. 그러나 글 스스로 1단계에서 든 Dinur 의 조합적 증명은 산술화에 기대지 않으므로 「PCP 정리의 증명 자체가 산술화에 기반」은 지나친 일반화	https://www.cs.berkeley.edu/%7Evazirani/pubs/relativizing.pdf · https://lance.fortnow.com/papers/files/relative.pdf
  SoS 차수·LP/SDP 확장 정식화 하한이 갭-CSP 에 대해 무조건 존재	맞음 (Grigoriev 2001, Schoenebeck 2008, Chan–Lee–Raghavendra–Steurer, Lee–Raghavendra–Steurer 2015). 단 「정확 판정보다 갭 판정에서 훨씬 강하고 깔끔하게 성립한다」는 사실이 아니라 이 글의 관찰·가설이다	https://en.wikipedia.org/wiki/Sum-of-squares_optimization

  고칠 곳

  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단계에서 점검한다」를 덧붙이면 오해가 줄어든다.

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

  답 달기
• 보완#90원문 보완판 — 사실 검토 반영
  • 관리자
  • 2026-10-07 13:28
  • AI 도움
  • 빨간 표시 안보이게

  PCP 정리는 P 대 NP 를 「정확한 판정」이 아니라 「상수 갭이 있는 근사 판정」의 문제로 손실 없이 다시 쓰게 해 준다. 이 글은 그렇게 다시 쓴 명제를 표적으로 삼아 하한 기법과 잇는 계획을 제안한다.

  아이디어 개요

  PCP 정리(Arora–Safra, Arora–Lund–Motwani–Sudan–Szegedy)는 NP = PCP(log n, O(1)), 즉 NP의 모든 증명을 O(log n) 무작위 비트와 상수 개의 비트 조회만으로 확률적으로 검증되는 형태로 다시 쓸 수 있음을 말한다. 이는 P vs NP를 "정확한 판정"이 아니라 "상수 갭이 있는 근사 판정"의 문제로 무손실 재정식화하게 해 준다. 실제로 PCP 정리는 「어떤 상수 ρ<1 에 대해 MAX-3SAT 를 ρ 비율로 근사하는 것이 NP-난해하다」는 갭 문제 난해성과 동치이며, Håstad(2001)는 그 문턱을 7/8+ε 로 끌어올려 갭의 위치를 최적으로 고정했다. 따라서 P≠NP는 "특정 갭-CSP를 다항 시간에 푸는 알고리즘이 존재하지 않는다"는 강건(robust)한 명제와 정확히 같다.

  PCP 정리(증명된 정리 · Arora–Safra, Arora–Lund–Motwani–Sudan–Szegedy) — NP = PCP(log n, O(1)).

  UGC 아래의 최적성(조건부 · UGC 는 아직 추측이다) — UGC 가 참이라면 Raghavendra 정리에 의해 모든 CSP 근사에 대해 기본 SDP 완화가 사실상 최적 알고리즘이 된다 — 정확히는 「기본 SDP 보다 잘 근사하는 다항 알고리즘이 있으면 P=NP」라는 뜻이며, 이 최적성은 P≠NP 를 전제로 한다.

  본 아이디어는 이 갭 재정식화를 표적 명제로 채택하고, Dinur의 조합적 갭 증폭, Raz의 병렬 반복, Khot–Minzer–Safra의 2-대-2 게임 정리로 정점에 이른 UGC 계열 구조(그라스만 그래프 전개, 소집합 확장)를 갭을 다루는 표준 연장통으로 삼아, "어떤 갭 구간까지의 난해성이 어떤 하한 기법과 접속 가능한가"를 체계적으로 규명하는 프로그램이다. 특히 UGC 가 참이라면 Raghavendra 정리에 의해 모든 CSP 에서 기본 SDP 가 (P≠NP 아래) 최적이 되므로, 갭 지도의 경계가 하나의 알고리즘 군의 성능 곡선으로 정확히 그려진다. 다만 이것은 P≠NP 를 단일 알고리즘의 실패로 바꿔 주지 않는다 — SDP 를 넘는 다항 알고리즘이 없음을 보이는 일이 곧 (UGC 아래) P≠NP 이기 때문이다. PCP 정리(원래의 대수적 증명은 산술화에 기반한다)가 대표적 비상대화 결과라는 점, 그리고 갭 문제의 강건성이 정확 판정 기반 논법의 취약점을 우회할 여지를 준다는 점이 이 경로의 지렛대라고 이 글은 본다.

  

  구체적 진행 방법

  1. 성분표 작성 단계: PCP 정리의 두 증명 경로 — 대수적 원증명(저차 검사, 합 검사 프로토콜, 증명 합성)과 Dinur의 조합적 증명(확장 그래프 위 거듭제곱에 의한 갭 증폭 + 알파벳 축소) — 을 정독하고, 각 증명의 어느 단계에서 산술화·확장성·합성이라는 비상대화 성분이 주입되는지 단계별 성분표를 만든다. Håstad의 3-비트 PCP(롱 코드 + 푸리에 분석)와 Raz 병렬 반복(및 Holenstein·Rao 의 개선, Braverman–Garg 의 작은 값 병렬 반복, Feige–Verbitsky·Raz(2008)의 강한 병렬 반복 반례라는 한계)도 같은 표에 편입한다.
  2. 재정식화의 정본화: "P≠NP ⟺ 갭-CSP 난해"의 동치를 갭 위치, 알파벳 크기, 질의 수, 완전성(perfect/near-perfect completeness) 매개변수까지 명시한 정확한 명제로 적고, 매개변수 공간 위에 NP-난해 확정 영역 / UG-난해(조건부) 영역 / 다항 알고리즘 존재 영역의 3색 지도를 그린다. Raghavendra 정리에 의해 UGC 하에서 경계선이 기본 SDP의 적분성 갭 곡선과 일치한다는 사실을 지도의 기준선으로 삼는다 — 이 기준선은 경계를 그리는 도구일 뿐이며, 경계 너머에 다항 알고리즘이 없다는 것은 UGC 와 P≠NP 를 함께 전제로 한다.
  3. 장벽 상호작용의 형식적 검토: 갭 재정식화된 명제에 대해 상대화·자연 증명·대수화 장벽이 각각 어떻게 작동하는지 검토한다. 특히 오라클 세계에서 PCP 특성화가 깨지는 사례를 정리해 "갭 명제는 상대화하지 않는 형태로 표현된다"는 관찰을 정리 수준으로 다듬고, Aaronson–Wigderson의 대수화 틀에서 갭 명제가 어느 위치에 놓이는지 분류한다.
  4. 갭 문제와 무조건 하한의 접속: 갭-CSP에 대해 이미 존재하는 무조건적 제한 모델 하한들 — SoS 차수 하한, 낮은 차수 다항식 하한, LP/SDP 확장 정식화 하한 — 을 "갭 위치별"로 카탈로그화한다. 정확 판정보다 갭 판정에서 제한 모델 하한이 더 강하고 깔끔하게 성립하는지(이 글의 가설)를 정량화하고, SoS 프로그램(별도 아이디어로 등록된 SoS 하한 트랙)과의 인터페이스를 "이쪽은 검증자·갭 구조 공급, 저쪽은 알고리즘 모델 하한 공급"으로 명시적으로 정의한다.
  5. UGC 본체의 공략 상태 정리: 소집합 확장 가설(SSE)과 UGC의 함의 관계, Arora–Barak–Steurer의 준지수 알고리즘이 만드는 긴장(UGC가 참이어도 그 난해성의 결이 표준 NP-완전성과 다를 수 있음), 그리고 2-대-2 정리를 성립시킨 그라스만 그래프의 유사무작위성 분석이 유니크 게임 본체(완전성 1-ε 영역)로 확장되지 못하는 병목 지점을 식별한다. 이 병목이 본 프로그램의 최대 단일 미해결 부품이다.
  6. 짧은 PCP와 미세 복잡도 연결: 준선형 크기 PCP(Ben-Sasson–Sudan 계열)와 갭-ETH(Dinur, Manurangsi–Raghavendra)를 정리해, "갭 난해성의 정량적 강화"가 ETH/SETH 기반 미세 복잡도 하한과 어떻게 맞물리는지 지도화한다. 이는 갭 재정식화가 다항/비다항 경계뿐 아니라 지수 시간 영역의 정밀 하한과도 호환되는 부품임을 보여 주는 마일스톤이다.
  7. 종합 명제 산출: 최종적으로 "갭 재정식화(정리) + 알고리즘 최적성(UGC 조건부) + 제한 모델 무조건 하한"의 세 부품을 맞물렸을 때 무엇이 여전히 P≠NP 와 동치인 채로 남는지를 명제 형태로 명시한다. 제한 모델 하한(SoS·LP·SDP)은 특정 알고리즘 군에 대한 하한이고 Raghavendra 최적성은 P≠NP 를 전제로 하므로, 세 부품이 맞물린다고 그대로 P≠NP 가 닫히지는 않는다. 남는 간극을 이루는 하위 문제 목록을 산출한다. 실제 증명 시도가 아니라, 어디가 여전히 열려 있는지의 청사진을 만드는 것이 이 단계의 산출물이다.

  왜 해볼 만한 가치가 있는가

  1. 기초가 추측이 아니라 정리다: 갭 재정식화는 PCP 정리라는 이미 증명된 사실에 의해 보장되는 무손실 번역이다. 즉 이 경로는 "P vs NP를 다른 미해결 추측으로 바꿔치기"하는 것이 아니라, 같은 명제를 알고리즘 실패가 더 구조적으로 드러나는 좌표계로 옮기는 것이다.
  2. 상대화 장벽에 대한 내장 우회: PCP 정리는 대표적 비상대화 성과이며(원래의 대수적 증명은 IP=PSPACE 와 같은 뿌리의 산술화 기법에 기반한다), 갭 특성화 자체가 오라클에 대해 강건하지 않다. 따라서 이 글의 판단으로는 이 좌표계에서 출발하는 논법은 Baker–Gill–Solovay 장벽을 시작점부터 피해 갈 소지가 크고, 남는 문제는 대수화 장벽과의 관계로 좁혀진다 — 이를 3단계에서 정면으로 분류한다. 다만 출발점이 비상대화라는 것만으로 이후 논법이 상대화 장벽을 피하는 것은 아니며, 비상대화 성분이 최종 논법에 실제로 쓰이는지를 3단계에서 점검한다.
  3. 자연 증명 장벽의 직접 적용 대상이 아니다: 이 글의 판단으로는 갭-CSP 난해성은 균일 알고리즘에 대한 명제로, 회로에 대한 구성적·대규모 판별 성질을 요구하지 않는다. 물론 최종적으로 회로 하한 형태로 내려가면 장벽과 다시 만나지만, "어느 지점에서 다시 만나는가"를 갭 매개변수의 언어로 정밀하게 위치시킬 수 있다는 것 자체가 기존 접근에 없던 해상도다.
  4. 경계선의 통일 원리: UGC + Raghavendra 최적성은 근사 난이도의 경계를 「기본 SDP 한 개의 성능」으로 정확히 그려 주는, 현재 알려진 거의 유일한 통일 원리다(단 이는 P≠NP 를 전제로 한 최적성이다). UGC가 거짓으로 판명되더라도 그 반증 알고리즘(ABS 계열의 확장)은 스펙트럴·SDP 위계 기법의 대약진을 뜻하므로, 어느 쪽으로 결론이 나든 프로그램은 성과를 남긴다.
  5. 부분 성과가 그대로 독립 기여가 된다: 갭 지도의 빈칸 채우기(새 비근사성 결과, 병렬 반복 정량 개선, 2-대-2에서 1-대-1로의 확장 시도, 갭-ETH 정련)는 근사 알고리즘·미세 복잡도 분야의 표준 미해결 문제들이어서, P vs NP 본체에 닿지 못해도 각 단계의 산출물이 그 자체로 출판 가능한 기여로 남는다.

  이 글이 보는 세 장벽과의 관계 — 아이디어 쪽의 판단이며 검증된 결론이 아니다

  장벽	이 글의 판단
  상대화	PCP 정리는 비상대화 성과이고(원래의 대수적 증명은 IP=PSPACE 와 같은 뿌리의 산술화 기법에 기반한다) 갭 특성화 자체가 오라클에 대해 강건하지 않으므로, 이 좌표계에서 출발하는 논법은 Baker–Gill–Solovay 장벽을 시작점부터 피해 갈 소지가 크다고 본다. 다만 출발점이 비상대화라는 것만으로 이후 논법이 상대화 장벽을 피하는 것은 아니며, 비상대화 성분이 최종 논법에 실제로 쓰이는지를 3단계에서 점검한다.
  자연 증명	갭-CSP 난해성은 균일 알고리즘에 대한 명제로, 회로에 대한 구성적·대규모 판별 성질을 요구하지 않으므로 직접 적용 대상이 아니라고 본다. 회로 하한 형태로 내려가면 다시 만나며, 그 지점을 갭 매개변수의 언어로 위치시킨다.
  대수화	남는 문제는 대수화 장벽과의 관계로 좁혀진다고 보고, 3단계에서 정면으로 분류한다.

  참고 문헌

  • PCP 정리 개관 — Arora–Safra, Arora–Lund–Motwani–Sudan–Szegedy(1992 FOCS, 1998 JACM), Dinur(JACM 2007), Ben-Sasson–Sudan(SICOMP 2008): PCP theorem
  • Håstad, 「Some optimal inapproximability results」, JACM 2001: 해설 PDF · MAX-3SAT
  • Raz, 병렬 반복 정리(SICOMP 1998) · Holenstein(STOC 2007) · Rao(STOC 2008): 해설
  • Braverman–Garg, 작은 값 병렬 반복(ECCC TR14-095, STOC 2015): ECCC
  • Raz, 강한 병렬 반복 반례(2008): SIAM
  • Khot–Minzer–Safra, 2-대-2 게임 정리(FOCS 2018 / Annals 2023): Annals of Mathematics
  • Raghavendra, STOC 2008(UGC 아래 모든 CSP 에서 기본 SDP 최적성): PDF
  • UGC 개관 — Arora–Barak–Steurer(FOCS 2010, JACM 2015), Raghavendra–Steurer(2010, SSE ⇒ UGC): Unique games conjecture
  • 갭-ETH — Dinur(ECCC 2016), Manurangsi–Raghavendra(ICALP 2017): Exponential time hypothesis
  • 상대화하는 기법과 하지 않는 기법: berkeley.edu PDF · fortnow.com PDF
  • SoS·확장 정식화 하한 — Grigoriev(2001), Schoenebeck(2008), Chan–Lee–Raghavendra–Steurer, Lee–Raghavendra–Steurer(2015): Sum-of-squares optimization
  답 달기