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

단조 회로 하한은 일반 회로 하한으로 자동으로 옮겨지지 않지만, 부정(NOT) 게이트를 O(log n)개까지 허용한 회로에서 하한을 보이면 그것이 곧 일반 회로 하한이 된다. 이 글은 허용하는 부정 게이트 수를 한 단계씩 늘려 가는 연구 계획을 제안한다.

아이디어 개요

Razborov의 단조 회로 초다항 하한(CLIQUE)은 회로 복잡도 분야가 낳은 가장 강력한 성과지만, 완전 매칭처럼 P에 속하면서도 단조 회로로는 초다항 크기가 필요한 함수가 있다는 것도 Razborov 자신이 보였다(1985) — 단조 함수의 단조 하한은 일반 하한으로 자동으로 옮겨지지 않는다(슬라이스 함수는 예외 — 아래 5단계).

그런데 Markov의 정리에 따르면 임의의 불리언 함수는 약 log n 개의 부정(NOT) 게이트만으로 계산 가능하고, Fischer의 결과에 의해 이 변환은 다항 크기 오버헤드 안에서 이루어진다. 따라서 "부정 게이트를 O(log n)개까지 허용한 회로"에 대해 NP 완전 문제의 초다항 크기 하한을 증명하면 그것이 곧 일반 회로 하한이며 P≠NP가 따라온다.

현재 최전선은 Amano–Maruoka가 도달한 약 (1/6)log log n 개 수준이므로, 본 연구는 부정 게이트 수 t를 독립된 계산 자원으로 취급하여 t 증가에 따른 하한의 감쇠 구조를 체계적으로 규명하고, log log n 장벽을 점진적으로 밀어 올리는 것을 목표로 한다. 자연 증명(natural proofs) 장벽이 켜지는 문턱은 Guo–Malkin–Oliveira–Rosen(2015)이 보인 log n − O(1) 로 이미 알려져 있으므로, 그 문턱 아래에서 근사법이 어디까지 살아남는지를 조사하고, 문턱 위 구간에는 Williams의 알고리즘적 방법(ACC⁰ 하한의 성공 사례)을 시도한다. 다만 그 방법의 산출물은 NEXP·NQP 하한이어서 이 트랙만으로는 P≠NP 에 이르지 않는다.

구체적 진행 방법

1. 기초 문헌 정독 단계: Razborov의 근사법 원논문과 Alon–Boppana의 강화판, Karchmer–Wigderson의 통신 복잡도적 재해석, Markov·Fischer의 부정 게이트 정리, Amano–Maruoka의 부정 제한 하한, Guo–Malkin–Oliveira–Rosen 의 부정 게이트와 PRF 결과, Jukna의 회로 복잡도 교과서 해당 장, 그리고 Williams의 NEXP⊄ACC⁰ 논문과 후속 개선(THR 게이트 확장 포함)을 읽고 각 기법의 적용 범위와 한계 조건을 표로 정리한다.
2. 정식화 단계: 부정 게이트 t개를 가진 회로를 단조 성분들로 분해하는 표준 기법을 근사법의 언어로 다시 쓰고, "t에 따른 하한 감쇠 함수"라는 개념을 명시적으로 정의한다. 기존 증명들이 정확히 어느 보조 단계에서 log log n 수준에 묶이는지, 병목이 분해 폭발 때문인지 근사자 집합의 크기 때문인지를 분리하여 진단한다.
3. 마일스톤 1(재현·통합): t=0인 Razborov 하한과 t≤(1/6)log log n인 Amano–Maruoka 하한을 하나의 통일된 프레임워크 안에서 재유도하고, 감쇠 함수의 형태를 명시한 기술 노트를 작성한다. 이 노트 자체가 서베이 겸 출발점 논문이 된다.
4. 장벽 지도화 단계: Guo–Malkin–Oliveira–Rosen(TCC 2015)은 PRF 가 log n − O(1) 개의 부정 게이트를 필요로 함을 보였다. 그래서 그보다 적은 부정을 허용하는 구간에는 PRF 가 없고 PRF 형태의 자연 증명 장벽은 직접 걸리지 않는다. 다만 그 문턱은 Markov 한계(⌈log₂(n+1)⌉)와 상수 차이뿐이라, 장벽이 켜지는 구간은 사실상 일반 회로와 같다. 이 단계는 GMOR 2015 의 문턱을 출발점으로, 근사법이 그 문턱 아래 어디까지 살아남는지를 조사한다.
5. 마일스톤 2(점근적 개선): CLIQUE 또는 다른 단조 NP 완전 함수에 대해 허용 부정 수를 c·log log n(더 큰 상수 c) 혹은 (log log n)의 다항식 수준으로 끌어올리는 어떤 점근적 개선이라도 확보한다. 보조 트랙으로 슬라이스 함수(slice function) 경로 — 슬라이스 함수에서는 단조 하한이 곧 일반 하한과 다항 동치라는 Berkowitz의 관찰 — 를 검토하여, 슬라이스 구조가 근사법의 어느 병목을 완화하는지 별도 분석한다.
6. 우회 트랙(알고리즘적 방법 결합): 장벽 문턱 위 구간을 위해, 부정 제한 회로 클래스에 대한 자명하지 않은 충족가능성(SAT) 알고리즘을 설계하고 Williams의 "빠른 알고리즘 ⇒ 하한" 연결 정리를 이 클래스에 이식할 수 있는지 정식화한다. 이 방법은 대각선 논법을 쓰므로 자연 증명 장벽을 직접 받지 않는다고 설명되지만(그래도 Williams 2013 은 NEXP ⊄ C 가 구성적 성질의 존재와 동치임을 보였다), 산출물은 NEXP·NQP 하한이어서 이 트랙만으로는 NP 완전 문제의 하한, 곧 P≠NP 에 이르지 않는다.
7. 마일스톤 3(정리·공표): 부분 결과라도 감쇠 함수 개선, 근사법이 GMOR 문턱 아래 어디까지 통하는지에 대한 결과, SAT 알고리즘 중 하나를 완결된 정리로 다듬어 ECCC 프리프린트와 CCC/FOCS 계열 학회 투고를 목표로 정리한다. 이후 감쇠 함수가 어디까지 개선 가능한지에 대한 메타 정리(불가능성 결과 포함)를 장기 과제로 설정한다.

두 트랙의 나눔

왜 해볼 만한 가치가 있는가

1. 목표 지점이 정량적으로 완결되어 있다. log log n에서 log n까지의 간극은 유한하고 명확히 측정되는 전선이며, 종착점에 도달하는 순간 Fischer의 다항 시뮬레이션에 의해 문자 그대로 P≠NP가 성립한다. 중간의 어떤 점근적 개선도 그 자체로 독립된 성과가 된다.
2. 상대화·대수화 장벽에 걸리지 않을 것으로 본다(이 글의 판단). 근사법 계열은 오라클 접근이 아니라 회로 내부 구조를 직접 다룬다. 다만 Aaronson–Wigderson 은 NEXP ⊄ P/poly 같은 회로 하한 자체가 비대수화 기법을 요구함을 보였으므로, 이 경로가 성공한다면 그 기법은 반드시 비대수화여야 한다.
3. 자연 증명 장벽의 문턱이 이미 알려져 있다. Guo–Malkin–Oliveira–Rosen(TCC 2015)은 PRF 가 log n − O(1) 개의 부정 게이트를 필요로 함을 보였다. 그래서 그보다 적은 부정을 허용하는 구간에는 PRF 가 없고 PRF 형태의 자연 증명 장벽은 직접 걸리지 않는다. 다만 그 문턱은 Markov 한계(⌈log₂(n+1)⌉)와 상수 차이뿐이라, 장벽이 켜지는 구간은 사실상 일반 회로와 같다. 근사법이 이 문턱 아래 어디까지 살아남는지 밝히는 4단계 작업은 실패해도 그 자체가 장벽 이론에 대한 기여가 된다고 본다. 문턱 위 구간에는 Williams 의 알고리즘적 방법(6단계)을 시도하지만, 그 산출물은 NEXP·NQP 하한이어서 이 트랙만으로는 P≠NP 에 이르지 않는다.
4. 성공 전례가 있는 활성 분야다. Razborov(1985), Amano–Maruoka(2005), Williams 의 ACC⁰ 하한(2011)은 제한 회로 모델에서 하한이 실제로 증명되어 온 전례이고, 증폭(hardness magnification) 정리들은 특정 문제(MCSP 변형 등)의 약한 하한이 강한 분리로 이어질 수 있음을 보였다. 본 연구의 부분 결과가 증폭 정리의 입력이 될 수 있는지는 이 글의 추측이다.
5. 실패조차 정보가 된다. 만약 어떤 t 이상에서 하한 감쇠가 증명 가능하게 붕괴한다면, 이는 부정 게이트가 계산 능력에서 수행하는 구조적 역할을 정확히 짚어내는 새로운 장벽 정리가 되어 P vs NP가 왜 어려운지에 대한 이해를 한 단계 끌어올린다.