KW 게임 리프팅 공략

하위 정보 2

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

보완 2

• 보완#63사실 검토 — 작은 수정 후 가능
  • 관리자
  • 2026-10-07 13:04
  • AI 도움

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

  판정: 작은 수정 후 가능

  KW 게임·KRW 추측·리프팅(Raz–McKenzie, Göös–Pitassi–Watson, dag-like 리프팅) 서술은 맞다. 고칠 것은 ① 초로그 단조 깊이 하한의 첫 증명(Karchmer–Wigderson 1990, s-t 연결성)은 리프팅 이전의 결과라는 점 ② 「가젯 크기를 상수 수준까지」는 일반 결정트리 → 통신 리프팅에서는 미해결이고 상수 크기 가젯은 특정 측도(Nullstellensatz 차수 → 단조 스팬 프로그램 등)에서만 알려졌다는 점 ③ 이 글의 두 번째 축(KRW 부분 사례를 리프팅으로)은 단조 설정에서 이미 수행된 선행 연구(de Rezende–Meir–Nordström–Pitassi–Robere, 「KRW composition theorems via lifting」, FOCS 2020)가 있다는 점 ④ 자연 증명 판단에 NC1 안의 의사난수 함수라는 알려진 사정이 빠진 점.

  확인한 사실

  주장	사실 여부	근거 링크
  KW 게임은 회로 깊이를 통신 복잡도와 정확히 대응	맞음 — 팬인 2 De Morgan 회로(= 공식) 깊이 = KW 관계의 결정적 통신 복잡도 (Karchmer–Wigderson, STOC 1988 / SIAM J. Discrete Math. 3(2), 1990). 단조 판은 단조 깊이 ↔ 단조 KW 관계	https://arxiv.org/abs/2007.02740 (서론)
  리프팅 정리 = 질의 복잡도 하한 → 가젯 합성으로 통신 하한	맞음 (Raz–McKenzie FOCS 1997 / Combinatorica 1999, Göös–Pitassi–Watson FOCS 2015)	https://arxiv.org/abs/2007.02740
  단조 회로에서 두 도구의 결합으로 초로그 단조 깊이 하한과 단조 NC 계층 분리가 증명됨	단조 NC 계층 분리 = Raz–McKenzie(리프팅) — 맞음. 초로그 단조 깊이 하한의 첫 증명(s-t 연결성 Ω(log² n))은 KW 1990 으로 리프팅을 쓰지 않았다. 문장이 둘 다 리프팅 결과처럼 읽힘	https://arxiv.org/abs/2007.02740
  리프팅으로 단조 깊이·크기 하한과 절단평면 증명계 하한까지 얻어짐	맞음 — dag-like 리프팅으로 단조 회로 크기(Garg–Göös–Kamath–Sokolov STOC 2018), 단순 가젯 리프팅으로 절단평면 하한·단조 공식 분리(de Rezende 외, FOCS 2020)	https://arxiv.org/abs/2001.02144
  「최근의 상수 크기 가젯 리프팅 결과」	부분적으로 맞음 — 상수 크기(등호·대소 비교 등) 가젯은 Nullstellensatz 차수 → 단조 스팬 프로그램 크기 같은 대수적 측도 리프팅에서 성립(Pitassi–Robere 2018, de Rezende 외 2020). 일반 결정트리 → 결정적 통신 리프팅의 가젯은 여전히 로그 크기 이상이 필요하며 상수 크기 가젯판은 미해결	https://arxiv.org/abs/2001.02144
  KRW 추측: 합성 함수의 KW 통신 복잡도가 대략 가산, 성립하면 P ⊄ NC1	맞음 (Karchmer–Raz–Wigderson, Computational Complexity 5, 1995)	https://arxiv.org/abs/2007.02740
  KRW 부분 결과: 보편 관계와의 합성, 다중화기 완화, XOR 합성, 정보 복잡도 접근	맞음 (Edmonds–Impagliazzo–Rudich–Sgall 2001, Håstad–Wigderson 1993, Gavinsky–Meir–Weinstein–Wigderson STOC 2014 등)	https://arxiv.org/abs/2007.02740 (관련 연구 절)
  두 번째 축: KRW 부분 사례를 리프팅으로 공략	선행 연구 누락 — de Rezende–Meir–Nordström–Pitassi–Robere 가 「리프팅으로 하한이 나는 모든 단조 내부 함수」에 대해 단조 KRW 추측을 증명했고(s-t 연결성·클릭·생성 함수 포함), 비단조 쪽으로 가는 「반단조 합성」도 도입했다. 이 글의 축과 정확히 겹치므로 출발점으로 적어야 함	https://arxiv.org/abs/2007.02740
  「P ≠ NC1」	표기는 통용되나 정확히는 P ⊄ NC1 (NC1 ⊆ P 이므로 같은 뜻)	—
  「KW/KRW 경로는 회로 구조를 직접 다루므로 상대화·대수화 장벽의 적용 대상이 아니다」	판단으로 표시됨(표). 본문 가치 1에서는 단정형	—
  자연 증명: 「특정 합성 함수의 구조를 정면으로 사용하는 논증이라 … 비켜갈 여지」	판단으로 표시됨. 알려진 사정 추가 필요 — NC1(실은 TC0)에 의사난수 함수 후보가 있으므로(Naor–Reingold 등) NC1 하한에 대해서는 자연 증명 장벽이 실제로 성립한다고 여겨진다. KRW 경로가 피할 수 있다는 근거는 대상 함수가 「대규모」 성질이 아닌 특정 반복 합성 함수라는 점뿐이다	https://en.wikipedia.org/wiki/Naor%E2%80%93Reingold_pseudorandom_function · https://en.wikipedia.org/wiki/Natural_proof
  「P ≠ NC1 … 에서 개발되는 통신 하한 기술은 NP 대 P/poly 공략의 재사용 가능한 표준 부품이 된다」	이 글의 전망 — 사실 문장처럼 쓰여 있음	—
  글 안 순서 대조 — 「6단계에서 체크리스트로 상시 검증」	맞음 (6 = 장벽 점검)	본문

  고칠 곳

  1. 원문(개요 1문단): 「단조 회로 세계에서는 이 대응과 리프팅 정리(…)의 결합으로 이미 초로그 단조 깊이 하한과 단조 NC 계층 분리가 실제로 증명되었다.」
     → 제안: 「단조 회로 세계에서는 KW 대응만으로 초로그 단조 깊이 하한이 먼저 증명되었고(Karchmer–Wigderson 1990, s-t 연결성), 이어 리프팅 정리(…)와의 결합으로 단조 NC 계층 분리(Raz–McKenzie 1999)와 단조 회로 크기 하한까지 증명되었다.」 (핵심 정리 3도 같은 뜻으로)
  2. 원문(개요 2문단): 「첫째, 리프팅 정리의 가젯 크기를 상수 수준까지 줄이고」
     → 제안: 「첫째, 일반 결정트리 → 통신 리프팅의 가젯 크기를 상수 수준까지 줄이고(현재 상수 크기 가젯은 Nullstellensatz 차수 → 단조 스팬 프로그램 같은 특정 측도에서만 알려져 있고, 일반판은 미해결이다)」
  3. 원문(개요 2문단 끝 또는 진행 방법 2): 다음 문장 추가 — 「단조 설정에서는 이 축이 이미 시작되었다: de Rezende–Meir–Nordström–Pitassi–Robere(FOCS 2020)는 리프팅으로 하한이 나는 모든 단조 내부 함수에 대해 단조 KRW 추측을 증명했고, 비단조 쪽으로 가는 「반단조 합성」을 도입했다. 이 글은 그 다음 걸음을 노린다.」
  4. 원문(가치 1): 「KW/KRW 경로는 회로 구조를 직접 다루므로 상대화·대수화 장벽의 적용 대상이 아니며, … 자연 증명 장벽도 원리상 비켜갈 여지가 있다.」
     → 제안: 「KW/KRW 경로는 회로 구조를 직접 다루므로 상대화·대수화 장벽의 적용 대상이 아니라고 본다. NC1 에는 의사난수 함수 후보가 있어 NC1 하한에 대해서는 자연 증명 장벽이 성립한다고 여겨지지만, 이 경로의 대상은 「대규모」 성질이 아닌 특정 반복 합성 함수이므로 그 장벽을 비켜갈 여지가 있다고 본다.」 (장벽 표 「자연 증명」 줄에도 NC1 의사난수 함수 단서를 덧붙인다)
  5. 원문: 「P ≠ NC1 자체는 P vs NP가 아니지만, 이 경로에서 개발되는 … 기술은 NP 대 P/poly 공략의 재사용 가능한 표준 부품이 된다.」
     → 제안: 「… 기술은 NP 대 P/poly 공략에서 다시 쓸 수 있는 부품이 될 수 있다고 본다.」

  넣을 수 있는 문헌 목록 (제안)

  • M. Karchmer, A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth, STOC 1988 / SIAM J. Discrete Math. 3(2), 1990.
  • M. Karchmer, R. Raz, A. Wigderson, Super-logarithmic depth lower bounds via the direct sum in communication complexity, Computational Complexity 5, 1995.
  • R. Raz, P. McKenzie, Separation of the monotone NC hierarchy, FOCS 1997 / Combinatorica 19, 1999.
  • M. Göös, T. Pitassi, T. Watson, Deterministic communication vs. partition number, FOCS 2015.
  • A. Garg, M. Göös, P. Kamath, D. Sokolov, Monotone circuit lower bounds from resolution, STOC 2018.
  • D. Gavinsky, O. Meir, O. Weinstein, A. Wigderson, Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture, STOC 2014.
  • S. de Rezende, O. Meir, J. Nordström, T. Pitassi, R. Robere, KRW composition theorems via lifting, FOCS 2020 (arXiv 2007.02740).
  • S. de Rezende, O. Meir, J. Nordström, T. Pitassi, R. Robere, M. Vinyals, Lifting with simple gadgets and applications to circuit and proof complexity, FOCS 2020 (arXiv 2001.02144).

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

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

  회로 깊이 하한이라는 손대기 어려운 문제를 두 사람 사이의 통신 문제로 바꿔 다루는 길이 있다. 단조 회로에서는 이미 통한 이 방법을 일반 회로 쪽으로 넓혀 보자는 제안이다.

  아이디어 개요

  Karchmer–Wigderson(KW) 게임은 불리언 함수의 회로 깊이를 두 참가자 사이의 통신 복잡도와 정확히 대응시키는 틀로, 회로 하한이라는 손대기 어려운 문제를 통신 하한이라는 상대적으로 다루기 쉬운 문제로 바꿔 준다. 단조 회로 세계에서는 KW 대응만으로 초로그 단조 깊이 하한이 먼저 증명되었고(Karchmer–Wigderson 1990, s-t 연결성), 이어 리프팅 정리(질의 복잡도 하한을 가젯 합성을 통해 통신 복잡도 하한으로 끌어올리는 정리)와의 결합으로 단조 NC 계층 분리(Raz–McKenzie 1999)와 단조 회로 크기 하한까지 증명되었다.

  

  본 아이디어는 두 축으로 이 성공을 일반 회로 쪽으로 밀어붙이는 것이다. 첫째, 일반 결정트리 → 통신 리프팅의 가젯 크기를 상수 수준까지 줄이고(현재 상수 크기 가젯은 Nullstellensatz 차수 → 단조 스팬 프로그램 같은 특정 측도에서만 알려져 있고, 일반판은 미해결이다) 적용 대상을 KW 관계의 합성 구조로 확장한다. 둘째, 합성 함수의 KW 통신 복잡도가 대략 가산된다는 Karchmer–Raz–Wigderson(KRW) 추측의 부분 사례들을 리프팅 기법으로 공략하여, P와 NC1의 분리로 가는 교두보를 만든다. 단조 설정에서는 이 축이 이미 시작되었다: de Rezende–Meir–Nordström–Pitassi–Robere(FOCS 2020)는 리프팅으로 하한이 나는 모든 단조 내부 함수에 대해 단조 KRW 추측을 증명했고, 비단조 쪽으로 가는 「반단조 합성」을 도입했다. 이 글은 그 다음 걸음을 노린다.

  

  구체적 진행 방법

  1. 문헌 지도 작성: Raz–McKenzie 이후의 결정트리→통신 리프팅 계열(Göös–Pitassi–Watson 등), 단조 회로 크기용 dag-like 리프팅, 최근의 상수 크기 가젯 리프팅 결과(Nullstellensatz 차수 → 단조 스팬 프로그램 크기 같은 대수적 측도 리프팅)를 가젯 종류, 적용 가능한 외부 문제 유형, 손실률 기준으로 한 장의 표로 정리한다.
  2. KRW 추측의 기존 부분 결과들(보편 관계와의 합성, 다중화기 완화 버전, XOR 합성, 정보 복잡도 기반 접근, 리프팅으로 얻은 단조 KRW 결과(de Rezende 외 2020))을 같은 좌표계 위에 배치하여, "리프팅 기술이 아직 닿지 못한 합성 형태"가 정확히 어디인지 식별한다.
  3. 내부 함수가 구조화된 특수 사례(패리티, 다수결, 무작위 함수 등)에 대해, 외부 함수의 질의 복잡도 하한을 내부 KW 관계 위로 리프팅하는 새 정리의 정확한 서술과 요구 조건을 정식화한다. 이 단계의 산출물은 증명이 아니라 "증명해야 할 명제의 확정"이다.
  4. 단조 설정에서 중간 목표를 수행한다: 알려진 단조 깊이 계층 결과를 리프팅으로 재유도하면서 기법의 손실이 어디서 발생하는지 실측하고, 명시적 함수에 대한 더 강한 단조 깊이-크기 트레이드오프를 다음 이정표로 삼는다.
  5. 소규모 계산 실험: 작은 합성 함수들의 KW 관계 통신 복잡도를 SAT 솔버나 정수계획으로 정확 계산하거나 상하한을 산출하여, 합성 시 복잡도가 실제로 가산되는지에 대한 수치적 증거와 반례 후보를 수집한다.
  6. 장벽 점검: 설계 중인 논증이 자연 증명 장벽의 "대규모성·구성성" 조건을 회피하는지, 상대화·대수화와 무관한 형태인지 체크리스트로 상시 검증하고, 회피에 실패하는 지점을 논증 수정의 피드백으로 사용한다.
  7. 성과 정리와 확장: 부분 합성 사례에서 하한이 확보되면 반복 합성으로 깊이 하한을 증폭하는 표준 절차에 대입해 P ≠ NC1 방향의 조건부 정리로 정리하고, 단조 결과를 비단조로 이전할 때 정확히 어떤 추가 가정이 필요한지를 명시한 로드맵 문서를 만든다.

  왜 해볼 만한 가치가 있는가

  1. 3대 장벽과의 관계가 유리하다고 본다. KW/KRW 경로는 회로 구조를 직접 다루므로 상대화·대수화 장벽의 적용 대상이 아니라고 본다. NC1 에는 의사난수 함수 후보가 있어 NC1 하한에 대해서는 자연 증명 장벽이 성립한다고 여겨지지만, 이 경로의 대상은 「대규모」 성질이 아닌 특정 반복 합성 함수이므로 그 장벽을 비켜갈 여지가 있다고 본다.
  2. 단조 세계에서는 동일한 도구가 실제로 작동함이 이미 증명되어 있다. 리프팅으로 단조 깊이·크기 하한과 절단평면 증명계 하한까지 얻어졌으므로, "기술은 존재하고 비단조로의 이전만 남은" 보기 드문 상황이다.
  3. KRW 추측은 전부를 풀지 못해도 부분 사례 하나하나가 독립적 가치를 갖는, 세분화가 잘 되는 문제다. 보편 관계와의 합성, 한쪽만 단조인 합성 등 중간 이정표가 풍부해 단계적 성과 축적이 가능하다.
  4. 계산 실험 단계는 순수 이론 연구로는 드물게 조기 피드백을 제공하며, 만약 반례 후보가 발견되면 그 자체로 추측의 올바른 수정 방향을 제시하는 기여가 된다.
  5. 여기서 개발되는 통신 하한 기술은 증명 복잡도, 데이터 구조 하한, 회로 크기 하한 등 인접 분야로 즉시 전이되므로, 최종 목표에 도달하지 못하더라도 성과가 남는 저위험 구조다.

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

  장벽	이 글의 판단
  상대화	KW/KRW 경로는 회로 구조를 직접 다루므로 상대화 장벽의 적용 대상이 아니라고 본다.
  자연 증명	특정 합성 함수의 구조를 정면으로 사용하는 논증이라, 무작위 함수 전체에 적용되는 「대규모」 성질을 요구하는 자연 증명 장벽도 원리상 비켜갈 여지가 있다고 본다. 단, NC1(실은 TC0)에 의사난수 함수 후보(Naor–Reingold 등)가 있어 NC1 하한에 대해서는 자연 증명 장벽이 실제로 성립한다고 여겨진다 — 비켜갈 근거는 대상이 특정 반복 합성 함수라는 점뿐이다. 6단계에서 체크리스트로 상시 검증한다.
  대수화	회로 구조를 직접 다루므로 대수화 장벽의 적용 대상이 아니라고 본다.

  참고 문헌

  • M. Karchmer, A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth, STOC 1988 / SIAM J. Discrete Math. 3(2), 1990.
  • M. Karchmer, R. Raz, A. Wigderson, Super-logarithmic depth lower bounds via the direct sum in communication complexity, Computational Complexity 5, 1995.
  • R. Raz, P. McKenzie, Separation of the monotone NC hierarchy, FOCS 1997 / Combinatorica 19, 1999.
  • M. Göös, T. Pitassi, T. Watson, Deterministic communication vs. partition number, FOCS 2015.
  • A. Garg, M. Göös, P. Kamath, D. Sokolov, Monotone circuit lower bounds from resolution, STOC 2018.
  • D. Gavinsky, O. Meir, O. Weinstein, A. Wigderson, Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture, STOC 2014.
  • S. de Rezende, O. Meir, J. Nordström, T. Pitassi, R. Robere, KRW composition theorems via lifting, FOCS 2020. — arXiv 2007.02740
  • S. de Rezende, O. Meir, J. Nordström, T. Pitassi, R. Robere, M. Vinyals, Lifting with simple gadgets and applications to circuit and proof complexity, FOCS 2020. — arXiv 2001.02144
  • Naor–Reingold 의사난수 함수 — 위키백과(영어) 해설
  • 자연 증명 장벽 — 위키백과(영어) 해설
  답 달기