양자 하한의 고전 이식

하위 정보 2

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

보완 2

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

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

  판정: 보완 필요

  근거:

  1. 갈래 1 의 알려진 상한이 빠졌다. ADV±(f) ≤ Q(f) ≤ n 이므로 「ADV± 제곱 ≤ 식 크기」 경로로 얻는 식 크기 하한은 n² 를 넘을 수 없다. 알려진 최고 명시적 De Morgan 식 하한은 n^(3−o(1))(Håstad·Tal, Andreev 함수)이라, 이 갈래가 「새 하한」을 낼 수 있는 범위는 n² 이하 영역뿐이다. 글은 마일스톤 B 에서 「Khrapchenko류 … 가 처리하지 못하는 영역에서 새 하한」을 목표로 하면서 이 상한을 말하지 않는다.
  2. 갈래 2 의 연결이 알려진 정리처럼 쓰였다. KW 관계로 옮겨지는 현재의 리프팅 정리는 결정 트리 깊이·Nullstellensatz 차수 등을 들어 올리는 것이고, 근사 차수(쌍대 증인)를 KW 관계의 결정적 통신 하한으로 옮기는 정리는 알려져 있지 않다 — 이 연결이 바로 이 글의 제안인데 표시가 없다.
  3. 사실 오기 다섯: Aaronson 귀속(원정리는 Vinodchandran), Reichardt 「정확히」(상수배), 「다항식 방법이 대수화 장벽의 전형 기법」(반대로 장벽을 증명하는 도구), 「식 크기 목표에는 PRF 후보가 없다」(NC1 에 있다), 「단조 스팬 프로그램 크기」(ADV± 는 증인 크기에 대응).

  확인한 사실

  주장	사실 여부	근거 링크
  다항식 방법(Beals–Buhrman–Cleve–Mosca–de Wolf)	맞음(FOCS 1998, JACM 2001)	Drucker–de Wolf 서베이
  어드버서리 방법(Ambainis), 음수 가중치 확장 ADV±(Høyer–Lee–Špalek)	맞음(STOC 2000 / STOC 2007)	Reichardt arXiv 0904.2759
  Reichardt 의 정리로 ADV± 가 양자 질의 복잡도를 「정확히」 특성화, 스팬 프로그램과 동치	「정확히」는 과장. Reichardt(2009)는 로그 인자까지, 이후 Reichardt(2011)·Lee–Mittal–Reichardt–Špalek–Szegedy(2011)가 상수배까지 특성화. 최적 스팬 프로그램의 증인 크기가 ADV± 와 같다	arXiv 0904.2759 · arXiv 1011.3020
  Kerenidis–de Wolf 의 LDC 지수 하한	맞음, 단 2-질의 LDC(STOC 2003)	arXiv quant-ph/0208062
  Aaronson 의 「PP 는 크기 n^k 회로를 갖지 않는다」 정리	귀속 오류. 원정리는 Vinodchandran(2005, 고전적 증명). Aaronson(2006)은 PostBQP=PP 로 다른 증명을 주고 양자 회로·양자 조언까지 강화했으며, 이 결과가 상대화하지 않음을 보였다	Vinodchandran ECCC TR04-056 · Aaronson arXiv cs/0504048
  Sherstov 패턴 행렬 방법으로 근사 차수 → 통신 하한, AC0 관련 분리	맞음. 다만 AC0 sign-rank 하한(Razborov–Sherstov)은 근사 차수가 아니라 매끄러운 쌍대 증인을 가진 문턱 차수에서 온다	Razborov–Sherstov ECCC TR08-016
  ADV± 의 제곱이 식 크기의 하한	상수배까지 맞음(양의 가중치판은 Laplante–Lee–Szegedy 가 직접 증명). ADV±² ≤ n² 라는 상한이 함께 따른다	Laplante–Lee–Szegedy arXiv quant-ph/0501057
  「단조 스팬 프로그램 크기 하한」을 ADV± 쌍대 증인에서 도출	측도 혼동. ADV± 에 대응하는 것은 스팬 프로그램 증인 크기이고, 단조 스팬 프로그램 크기(행 수, Karchmer–Wigderson)는 다른 측도다	arXiv 0904.2759
  근사 차수 쌍대 증인을 리프팅으로 KW형 통신 하한까지	알려진 정리 아님(이 글의 제안). 알려진 KW 리프팅은 결정 트리 깊이 등에서 출발한다	—
  Bun–Thaler AC0 근사 차수 하한	맞음(FOCS 2017, Ω(n^(1−δ)))	Drucker–de Wolf (배경)
  Aaronson–Ben-David–Kothari 치트시트	맞음(STOC 2016)	—
  Laplante–Magniez 콜모고로프 어드버서리	맞음(CCC 2004, SICOMP 2008)	AKPV ECCC TR17-150
  고전 어드버서리가 분수 블록 민감도 등 어느 측도와 일치하는지 「정식화한다」	전함수에서는 이미 알려져 있음 — 모든 고전 어드버서리 하한 = 분수 블록 민감도(Ambainis–Kokainis–Prūsis–Vihrovs, STACS 2018)	ECCC TR17-150
  BBBV 「NP 를 푸는 데 그로버가 최적」 유형 오라클 분리	맞음(1997)	—
  「다항식 방법이 대수화 장벽의 전형 기법으로 지목」	틀림. Aaronson–Wigderson 은 적대적 다항식 구성과 통신 복잡도 하한을 써서 대수적 오라클 분리, 즉 장벽 자체를 증명했다. 대수화하는 기법의 전형은 산술화(IP=PSPACE)다	Aaronson–Wigderson
  「식 크기·AC0급 목표에서는 PRF 후보가 없다」	AC0 는 맞음, 식 크기는 틀림. 다항 크기 식 = NC1 ⊇ TC0 이고 TC0 에 Naor–Reingold PRF 후보가 있어 초다항 식 하한에는 자연 증명 장벽이 작동한다	Natural proof (Wikipedia)
  양자 도구로 고전 정리를 증명한 사례 축적	맞음	Drucker–de Wolf arXiv 0910.3376

  고칠 곳

  1. 핵심 정리 첫 줄·개요 첫 문단
     • 원문: 「Reichardt의 정리에 의해 ADV±는 양자 질의 복잡도를 SDP 쌍대성으로 정확히 특성화하며 스팬 프로그램(span program)과도 동치를 이룬다.」
     • 제안: 「Reichardt(2009·2011)와 Lee–Mittal–Reichardt–Špalek–Szegedy(2011)에 의해 ADV±(그 자체가 SDP)는 양자 질의 복잡도를 상수배 이내로 특성화하며, 그 쌍대가 스팬 프로그램의 증인 크기와 같다.」
  2. 핵심 정리 둘째 줄·개요 첫 문단
     • 원문: 「Aaronson의 "PP는 크기 n^k 회로를 갖지 않는다"는 정리」
     • 제안: 「Vinodchandran(2005)의 "PP는 크기 n^k 회로를 갖지 않는다"는 정리를 Aaronson(2006)이 PostBQP=PP 로 다시 증명해 양자 회로·양자 조언까지 강화한 일」
  3. 개요 첫 문단
     • 원문: 「Kerenidis-de Wolf의 국소 복호 가능 부호(LDC) 지수 하한」
     • 제안: 「Kerenidis–de Wolf의 2-질의 국소 복호 가능 부호(LDC) 지수 하한」
  4. 핵심 정리 「갈래 1」·개요 둘째 문단(보완 필요의 핵심)
     • 원문: 「ADV± 의 제곱이 불리언 식 크기의 하한이 된다는 관계로, SDP 쌍대 증인에서 명시적 함수의 식 하한을 직접 생산한다.」
     • 제안: 「ADV± 의 제곱이 불리언 식 크기의 하한이 된다는 관계(상수배까지)로 SDP 쌍대 증인에서 명시적 함수의 식 하한을 생산한다. 단 ADV±(f) ≤ Q(f) ≤ n 이라 이 경로의 하한은 n² 를 넘지 못하며, 알려진 최고 하한 n^(3−o(1))(Håstad·Tal)보다 낮다 — 목표는 기록 경신이 아니라 n² 이하에서 기존 기법이 다루지 못하는 함수족이다.」
     • 마일스톤 B 의 「목표는 Khrapchenko류 하한이나 Håstad의 수축(shrinkage) 논법이 이미 잘 처리하는 영역이 아니라, …」 문장에도 같은 n² 상한을 적는다.
  5. 마일스톤 B
     • 원문: 「특정 함수족의 식 크기 하한 또는 단조 스팬 프로그램 크기 하한을 도출한다.」
     • 제안: 「특정 함수족의 식 크기 하한(상한 n²) 또는 스팬 프로그램 증인 크기 하한을 도출한다(단조 스팬 프로그램의 '크기'는 ADV± 와 다른 측도다).」
  6. 핵심 정리 「갈래 2」·개요 둘째 문단·마일스톤 C
     • 원문: 「근사 차수의 쌍대 증인을 리프팅 정리로 Karchmer–Wigderson형 통신 하한까지 끌어올려 회로 깊이 하한의 부품으로 만든다.」
     • 제안: 「근사 차수의 쌍대 증인을 Karchmer–Wigderson형 통신 하한까지 끌어올리는 리프팅을 새로 찾아 회로 깊이 하한의 부품으로 만든다(지금 알려진 KW 리프팅은 결정 트리 깊이 등에서 출발하며, 근사 차수에서 KW 관계로 가는 정리는 아직 없다 — 이 글의 제안이다).」
  7. 이식 사전 작성(2단계)
     • 원문: 「근사 차수 → 패턴 행렬 → 양자·고전 통신 하한 → 부호 계수(sign-rank)·문턱 회로 하한」
     • 제안: 「근사 차수 → 패턴 행렬 → 양자·고전 유계 오차 통신 하한, 그리고 매끄러운 쌍대 증인을 가진 문턱 차수 → 부호 계수(sign-rank)·문턱 회로 하한(Razborov–Sherstov)」
  8. 3단계(고전 어드버서리의 사거리) 끝에 덧붙임: 「전함수에서는 모든 고전 어드버서리 하한이 분수 블록 민감도와 같다는 것이 이미 알려져 있다(Ambainis–Kokainis–Prūsis–Vihrovs, STACS 2018) — 정식화의 대상은 부분함수 쪽 간극이다.」
  9. 7단계(장벽 감사)·장벽 표 대수화 행
     • 원문: 「다항식 방법이 대수화 장벽의 전형 기법으로 지목된 만큼」 / 「다항식 방법은 대수화 장벽의 전형 기법으로 지목되었으므로」
     • 제안: 「Aaronson–Wigderson 이 다항식 구성과 통신 복잡도 하한으로 대수화 장벽(대수적 오라클 분리)을 증명했고 대수화하는 기법의 전형은 산술화이므로, 다항식 방법 기반 산출물이 어느 단계에서 대수화하는지와 어떤 변형(치트시트 결합 등)이 그 밖에 놓일 여지가 있는지 기록한다.」
  10. 왜 해볼 만한가 — 장벽 관리·장벽 표 자연 증명 행
      • 원문: 「자연 증명 장벽은 식 크기·AC0급 목표에서는 해당 클래스에 유사난수 함수 후보가 없어 약하게만 작동하며」
      • 제안: 「AC0 에는 유사난수 함수 후보가 없어 자연 증명 장벽이 작동하지 않지만, 다항 크기 식(NC1)에는 TC0 의 Naor–Reingold 후보가 들어 있어 초다항 식 크기 하한 목표에서는 장벽이 그대로 작동한다. n² 이하를 다루는 갈래 1 에서는 이 장벽의 영향이 약하다고 본다.」
  11. (선택) 7단계 「KW 대응을 통해 회로 세계로 진입하는 단계가 비상대화 성분의 주입 지점임을 명시하고」 → 「… 주입 지점이라고 보고(이 글의 판단)」. KW 대응은 조합적 동치이고, 비균일 명시적 하한에는 상대화 개념이 그대로 적용되지 않으므로 단정은 피한다.

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

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

  양자 질의 복잡도 분야에서 정비된 하한 기법이 순수하게 고전적인 명제를 증명하는 데 이미 여러 번 성공했다. 이 글은 그런 성공을 재현 가능한 방법론으로 정리하자고 제안한다.

  아이디어 개요

  양자 질의 복잡도 분야에서는 다항식 방법(polynomial method, Beals-Buhrman-Cleve-Mosca-de Wolf)과 어드버서리 방법(adversary method, Ambainis 및 음수 가중치 확장 ADV±)이라는 두 하한 기법이 고도로 정비되어 있고, 특히 Reichardt(2009·2011)와 Lee–Mittal–Reichardt–Špalek–Szegedy(2011)에 의해 ADV±(그 자체가 SDP)는 양자 질의 복잡도를 상수배 이내로 특성화하며, 그 쌍대가 스팬 프로그램(span program)의 증인 크기와 같다. 흥미로운 사실은 이 양자 기법들이 순수하게 고전적인 명제를 증명하는 데 이미 여러 번 성공했다는 점이다 — Kerenidis-de Wolf의 2-질의 국소 복호 가능 부호(LDC) 지수 하한, Vinodchandran(2005)의 "PP는 크기 n^k 회로를 갖지 않는다"는 정리를 Aaronson(2006)이 PostBQP=PP 로 다시 증명해 양자 회로·양자 조언까지 강화한 일, Sherstov가 패턴 행렬 방법으로 근사 차수(approximate degree)를 통신 하한으로 리프팅해 얻은 AC0 관련 분리들이 대표 사례다(다만 AC0 의 sign-rank 하한은 근사 차수가 아니라 매끄러운 쌍대 증인을 가진 문턱 차수에서 온다 — Razborov–Sherstov).

  본 아이디어는 이런 산발적 성공을 "양자 측도에서 고전 하한으로 가는 이식 사전(transfer dictionary)"으로 체계화하는 연구 프로그램이다. 파이프라인은 두 갈래로, 하나는 ADV±의 제곱이 불리언 식 크기(formula size)의 하한이 된다는 관계(상수배까지)와 스팬 프로그램 증인 크기의 연결을 이용해 명시적 함수의 식 하한을 SDP 쌍대 증인(dual witness)으로부터 생산하는 것이고(단 ADV±(f) ≤ Q(f) ≤ n 이라 이 경로의 하한은 n² 를 넘지 못하며, 알려진 최고 명시적 De Morgan 식 하한 n^(3−o(1))(Håstad·Tal, Andreev 함수)보다 낮다 — 목표는 기록 경신이 아니라 n² 이하에서 기존 기법이 다루지 못하는 함수족이다), 다른 하나는 근사 차수의 쌍대 증인을 Karchmer-Wigderson형 통신 하한까지 끌어올리는 리프팅을 새로 찾아 회로 깊이 하한의 부품으로 만드는 것이다(지금 알려진 KW 리프팅은 결정 트리 깊이·Nullstellensatz 차수 등에서 출발하며, 근사 차수에서 KW 관계로 가는 정리는 아직 없다 — 이 연결이 이 글의 제안이다).

  P≠NP를 즉시 겨냥하기보다, 양자 하한 도구를 고전 하한의 재사용 가능한 표준 부품으로 승격시키는 것이 목표다.

  

  구체적 진행 방법

  1. 기초 문헌 정독: BBCMdW의 다항식 방법 원논문, Ambainis의 어드버서리 방법과 Høyer-Lee-Špalek의 음수 가중치 확장, Reichardt(2009·2011)·Lee–Mittal–Reichardt–Špalek–Szegedy(2011)의 상수배 특성화와 스팬 프로그램 증인 크기 대응, Sherstov의 패턴 행렬 리프팅, Bun-Thaler의 AC0 근사 차수 하한, Aaronson-Ben-David-Kothari의 치트시트(cheat sheet) 기법, Kerenidis-de Wolf의 2-질의 LDC 하한, Laplante-Magniez의 콜모고로프 복잡도 기반 어드버서리를 정독하고, 각 기법의 적용 조건(전함수/부분함수, 대칭성 요구 등)과 알려진 한계를 조사 노트로 정리한다.
  2. 이식 사전 작성: "양자 측도 → 고전 귀결"의 대응을 한 장의 표로 만든다. 예컨대 ADV±(f)^2 ≤ 식 크기(스팬 프로그램 경유, 상수배까지 — 따라서 이 화살표의 하한은 n² 이하), 근사 차수 → 패턴 행렬 → 양자·고전 유계 오차 통신 하한, 그리고 매끄러운 쌍대 증인을 가진 문턱 차수 → 부호 계수(sign-rank)·문턱 회로 하한(Razborov–Sherstov), 양자 통신 하한이 고전 하한을 함의하는 방향 등 각 화살표마다 손실률(다항 손실인지 로그 손실인지)과 적용 전제를 명기한다.
  3. 고전 어드버서리의 사거리 규명: 고전 결정 트리에 대한 어드버서리류 하한이 분수 블록 민감도 등 어느 조합 측도와 일치하는지 정식화하고, 양자판과의 간극(전함수에서 최대 다항 간극)이 정확히 어디서 발생하는지 표로 만든다. 이 단계가 "양자 하한을 고전 하한으로 읽을 때 얼마나 손해 보는가"의 기준선이 된다. 전함수에서는 모든 고전 어드버서리 하한이 분수 블록 민감도와 같다는 것이 이미 알려져 있다(Ambainis–Kokainis–Prūsis–Vihrovs, STACS 2018) — 정식화의 대상은 부분함수 쪽 간극이다.
  4. 마일스톤 A(수치 SDP 파일럿): 작은 n의 명시적 함수족 — 반복 NAND 합성, 재귀 다수결, st-연결성 변형 — 에 대해 ADV± SDP를 수치적으로 풀어 최적 쌍대 증인의 구조적 패턴을 관찰하고 닫힌 형식을 추측한다. 어드버서리 하한이 유한 크기 SDP라는 점 덕분에 하한 연구로는 드물게 계산 실험이 가능한 구간이다.
  5. 마일스톤 B(식 크기·스팬 프로그램 하한 생산): 추측한 쌍대 증인을 일반 n으로 확장 증명하여 특정 함수족의 식 크기 하한(상한 n²) 또는 스팬 프로그램 증인 크기 하한을 도출한다(단조 스팬 프로그램의 '크기'는 ADV± 와 다른 측도다). 목표는 Khrapchenko류 하한이나 Håstad의 수축(shrinkage) 논법이 이미 잘 처리하는 영역이 아니라, 합성 구조 때문에 기존 기법이 미끄러지는 함수족에서 새 하한을 내는 것이다. 이 경로의 하한은 ADV±(f) ≤ Q(f) ≤ n 때문에 n² 를 넘지 못하므로, 알려진 최고 하한 n^(3−o(1))(Håstad·Tal)을 경신하는 것이 아니라 n² 이하 영역에서 기존 기법이 다루지 못하는 함수족을 겨냥한다.
  6. 마일스톤 C(리프팅 결합): 다항식 방법의 쌍대인 근사 차수 쌍대 증인을 패턴 행렬·가젯 리프팅과 결합해 KW형 관계의 통신 하한으로 승격하는 리프팅을 새로 찾고(알려진 KW 리프팅은 결정 트리 깊이 등에서 출발하며 근사 차수에서 KW 관계로 가는 정리는 아직 없다 — 이 단계 자체가 이 글의 제안이다), KRW형 합성 질문의 부분 사례(내부 함수가 패리티·다수결 등으로 구조화된 경우)에 적용한다. 이 부품은 성공하면 통신 복잡도 기반 깊이 하한 프로그램과 직접 접속된다.
  7. 장벽 감사: 각 산출물에 상대화/자연 증명/대수화 통과 여부 태그를 부착한다. 질의 하한 자체는 오라클 분리(BBBV의 "NP를 푸는 데 그로버가 최적" 유형)까지만 주므로, KW 대응을 통해 회로 세계로 진입하는 단계가 비상대화 성분의 주입 지점이라고 보고(이 글의 판단), Aaronson–Wigderson 이 다항식 구성과 통신 복잡도 하한으로 대수화 장벽(대수적 오라클 분리)을 증명했고 대수화하는 기법의 전형은 산술화이므로, 다항식 방법 기반 산출물이 어느 단계에서 대수화하는지와 어떤 변형(치트시트 결합 등)이 그 밖에 놓일 여지가 있는지 기록한다.
  8. 산출물 정리와 전환 트랙: 주 트랙이 정체되더라도 중간 산출물(새 질의 측도 분리, 측도 간 관계식, 수치 실험으로 발견한 반례)이 각각 독립적 결과가 되도록 마일스톤을 자기완결적으로 설계하고, 각 단계 종료 시 다음 단계의 성공 확률을 재평가하는 관문을 둔다.

  왜 해볼 만한 가치가 있는가

  1. 이식 원리가 이미 실증되어 있다: 2-질의 LDC 지수 하한, PP의 고정 다항 크기 회로 하한의 양자적 재증명·강화(원정리는 Vinodchandran, 양자 증명은 Aaronson), AC0의 sign-rank 하한 등 "양자 도구로 고전 정리를 증명"한 사례가 실제로 축적되어 있다. 본 프로그램은 이런 개별 요행을 재현 가능한 방법론으로 바꾸는 작업이며, 성공 사례가 존재하는 경로라는 점에서 순수 신규 기법보다 위험이 낮다고 본다.
  2. 구성적·실험 가능한 하한 경로다: 어드버서리 하한은 SDP이므로 쌍대 증인이 유한한 수학적 대상이고, 작은 사례를 컴퓨터로 풀어 일반 패턴을 역추론할 수 있다. 회로 하한 연구 대부분이 순수 사고 실험에 의존하는 것과 달리, 수치 실험이 추측 생성기 역할을 하는 드문 구간이다.
  3. 기존 장벽과의 관계가 정직하게 관리된다: 질의 하한은 상대화하므로 그 자체로는 P≠NP에 도달할 수 없다는 한계가 처음부터 명확하고, 바로 그 덕분에 "장벽을 넘는 성분이 파이프라인 어디에서 들어오는가"를 국소화할 수 있다고 본다. AC0 에는 유사난수 함수 후보가 없어 자연 증명 장벽이 작동하지 않지만, 다항 크기 식(NC1)에는 TC0 의 Naor–Reingold 후보가 들어 있어 초다항 식 크기 하한 목표에서는 장벽이 그대로 작동한다. n² 이하를 다루는 갈래 1 에서는 이 장벽의 영향이 약하다고 본다. 다항식 방법은 Aaronson–Wigderson 이 대수화 장벽을 증명하는 데 쓴 도구이기도 해서, 산출물이 어디서 대수화하는지 기록하는 일은 장벽 연구 쪽에 되먹임되는 부산물 정보가 된다.
  4. 다른 경로와의 상보성이 크다: 통신 복잡도 기반 깊이 하한 프로그램(KW 게임·KRW 추측 공략)에는 근사 차수 쌍대 증인이라는 하한 공급원을 제공하고, SoS 하한 프로그램과는 SDP 쌍대성이라는 공통 언어를 공유하므로, 게시판의 다른 아이디어들과 부품을 주고받는 허브 역할을 할 수 있다.
  5. 실패해도 남는 것이 분명하다: 프로그램이 고전 하한에 도달하지 못하더라도 양자 질의 복잡도의 새 분리나 측도 관계식은 그 자체로 양자 계산 이론의 기여이며, 치트시트류 기법으로 발견되는 반례는 고전 복잡도의 측도 관계 지도를 갱신한다.

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

  장벽	이 글의 판단
  상대화	질의 하한은 상대화하므로 그 자체로는 P≠NP 에 도달할 수 없다. 그 덕분에 「장벽을 넘는 성분이 파이프라인 어디에서 들어오는가」를 국소화할 수 있다고 본다(7단계: KW 대응으로 회로 세계에 들어가는 단계).
  자연 증명	AC0 에는 유사난수 함수 후보가 없어 자연 증명 장벽이 작동하지 않지만, 다항 크기 식(NC1)에는 TC0 의 Naor–Reingold 후보가 들어 있어 초다항 식 크기 하한 목표에서는 장벽이 그대로 작동한다. n² 이하를 다루는 갈래 1 에서는 이 장벽의 영향이 약하다고 본다.
  대수화	Aaronson–Wigderson 이 다항식 구성과 통신 복잡도 하한으로 대수화 장벽(대수적 오라클 분리)을 증명했고, 대수화하는 기법의 전형은 산술화다. 그래서 다항식 방법 기반 산출물이 어느 단계에서 대수화하는지와 어떤 변형(치트시트 결합 등)이 그 밖에 놓일 여지가 있는지 기록한다.

  참고 문헌

  • Drucker, de Wolf — Quantum Proofs for Classical Theorems(서베이, 다항식 방법·Bun–Thaler 배경 포함): arXiv 0910.3376
  • Reichardt — 스팬 프로그램과 양자 질의 복잡도(2009): arXiv 0904.2759
  • Lee, Mittal, Reichardt, Špalek, Szegedy — 상수배 특성화(2011): arXiv 1011.3020
  • Kerenidis, de Wolf — 2-질의 LDC 지수 하한, STOC 2003: arXiv quant-ph/0208062
  • Vinodchandran — PP 는 크기 n^k 회로를 갖지 않는다(2005): ECCC TR04-056
  • Aaronson — PostBQP=PP 를 통한 증명과 양자 회로·양자 조언 강화(2006): arXiv cs/0504048
  • Razborov, Sherstov — AC0 의 sign-rank 하한: ECCC TR08-016
  • Laplante, Lee, Szegedy — 어드버서리 제곱과 식 크기: arXiv quant-ph/0501057
  • Ambainis, Kokainis, Prūsis, Vihrovs — 고전 어드버서리 = 분수 블록 민감도, STACS 2018(Laplante–Magniez 콜모고로프 어드버서리 포함): ECCC TR17-150
  • Aaronson, Wigderson — Algebrization: A New Barrier in Complexity Theory: scottaaronson.com
  • 자연 증명과 유사난수 함수 후보(Naor–Reingold): Wikipedia — Natural proof
  • Høyer, Lee, Špalek — 음수 가중치 어드버서리 ADV±, STOC 2007
  • Bun, Thaler — AC0 근사 차수 하한 Ω(n^(1−δ)), FOCS 2017
  • Aaronson, Ben-David, Kothari — 치트시트, STOC 2016
  • Laplante, Magniez — 콜모고로프 어드버서리, CCC 2004 · SICOMP 2008
  • Bennett, Bernstein, Brassard, Vazirani(BBBV) — 그로버 최적성 유형 오라클 분리, 1997
  • Håstad · Tal — Andreev 함수의 De Morgan 식 하한 n^(3−o(1))
  답 달기