원문 보완판 — 사실 검토 반영

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

아이디어 개요

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. 여기서 개발되는 통신 하한 기술은 증명 복잡도, 데이터 구조 하한, 회로 크기 하한 등 인접 분야로 즉시 전이되므로, 최종 목표에 도달하지 못하더라도 성과가 남는 저위험 구조다.