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

「P=NP 가능성을 진지하게 탐색하는 알고리즘 연구는 실패해도 손해가 아니다」라는 관점에서 출발하는 아이디어다. SAT 를 푸는 지수 시간 알고리즘의 개선 이력을 사다리로 보고 그 끝을 더 밀어 본다.

아이디어 개요

3-SAT의 지수 상계는 전수탐색 2^n에서 출발해 분기 알고리즘(Monien–Speckenmeyer), 확률적 국소탐색(Schöning), PPSZ 계열로 밑수가 꾸준히 내려온 역사가 있다. 이 개선 이력을 우연한 트릭의 나열이 아니라 하나의 사다리로 보고, (1) 상계 밑수를 더 끌어내리는 일반 원리의 발굴, (2) CSP 이분법(dichotomy)이 그려 준 다항 시간 섬들을 대수적·스펙트럴 방법으로 바깥쪽으로 확장, (3) 그 결과를 SETH·ETH 반증 시도로 수렴시키는 3중 경로를 제안한다.

핵심 관점은 "P=NP 가능성을 진지하게 탐색하는 알고리즘 연구는 실패해도 손해가 아니다"라는 점이다. Williams 의 「알고리즘에서 회로 하한으로」 연결에 따르면 어떤 회로 클래스 C 의 회로 SAT 를 전수탐색보다 초다항 배 빠르게 푸는 알고리즘이 있으면 NEXP ⊄ C 같은 회로 하한이 따른다. 3-SAT·k-SAT(CNF) 밑수 개선은 이 연결만으로는 새 하한을 주지 않는다. 그래서 이 프로그램은 성공하면 복잡도 이론 최대의 성과이고, 부분 성공이 회로 클래스 SAT 의 가속으로 이어지면 하한 쪽 성과가 되는(이 글의 기대이며, k-SAT 밑수 개선만으로는 해당하지 않는다) 양면 보상 구조를 가진다.

구체적 진행 방법

1. 상계 개선 이력의 계보화: 2^n 에서 분기 알고리즘, 국소탐색, PPSZ, 편향 PPSZ 에 이르는 k-SAT 지수 상계 개선사와, 다항식 방법이 연 회로 클래스 SAT·CSP 변형의 개선사를 기법 계열별로 분류하고, 각 기법이 어떤 구조적 여유를 소비해 밑수를 깎았는지 명세화한 대장을 만든다. 어떤 여유가 아직 소비되지 않았는지가 다음 개선의 후보가 된다.
2. 구조 파라미터 사다리 구축: 트리폭, 백도어 크기, 절-변수 발생 횟수 제한, CSP 다형사상(polymorphism)의 풍부성 등 구조 파라미터로 인스턴스 공간을 계층화하고, 각 층에 알려진 최선 알고리즘(다항/준다항/준지수/지수)을 배치해 다항 시간 섬의 해안선이 정확히 어디서 끊기는지 지도를 만든다.
3. 대수적 확장 시도: Bulatov–Zhuk의 CSP 이분법이 제시한 다형사상 조건을 출발점으로, 다항 시간을 보장하는 대수 조건보다 약한 조건 아래에서 준지수·준다항 알고리즘이 성립하는 계층이 있는지 탐색한다. 단, 이분법에 따라 그런 템플릿은 NP-완전이므로 여기서 준다항 또는 2^{o(n)} 알고리즘을 얻으면 그것은 곧 ETH 반증이다 — 이 단계는 사실상 3번 경로(ETH 반증)의 한 형태다. 목표는 당장 P 섬을 넓히지 못하더라도 지수와 다항 사이의 중간 계층을 조밀하게 채우는 것이다(템플릿 축의 중간 계층은 ETH 가 거짓일 때만 존재하며, 2단계의 인스턴스 구조 축 — 트리폭·백도어 등 — 의 중간 계층은 이 제약을 받지 않는다).
4. 스펙트럴 경로: 절 구조를 하이퍼그래프·텐서로 인코딩하고, 스펙트럴 완화가 해를 증명 가능하게 복원하는 인스턴스 족을 특정한다. 랜덤 인스턴스에서 작동하는 스펙트럴 인증서를 최악 케이스에 가까운 구조화된 족으로 얼마나 밀어붙일 수 있는지가 관건이며, 실패 지점은 그 자체로 평균-최악 격차의 증거가 된다.
5. SETH 우선 공략: P=NP 직접 공략 이전의 현실적 1차 목표로, k가 커져도 사라지지 않는 절약(savings)을 갖는 k-SAT 알고리즘 설계를 시도한다. 다항식 방법과 행렬곱 알고리즘의 발전 등 최근 도구를 조합해, SETH가 금지하는 형태의 개선이 어느 지점에서 처음 막히는지 정밀하게 측정한다.
6. 실패의 정식화(장벽 대장): 각 경로가 막힐 때마다 왜 막혔는가를 장벽 명제 형태로 정식화하고, 상대화·자연 증명·대수화 장벽과의 관계를 표기해 목록화한다. 이 장벽 대장이 P≠NP 쪽 증거 자산이 될 수 있다고 본다.
7. 알고리즘-하한 변환의 상시 가동: 연구 중 얻어진 모든 부분 개선(예: 특정 회로 클래스에 대한 SAT의 미세 가속)을 Williams식 연결을 통해 회로 하한 명제로 번역하는 절차를 연구 루틴에 내장해, 알고리즘 쪽 진전이 자동으로 하한 쪽 성과로도 기록되게 한다.
8. 실험 하네스 구축: 구조 파라미터별 인스턴스 생성기와 솔버 계측기를 구현해 실측 지수 밑수의 파라미터 의존성을 측정하고, 이론적 추측들의 공략 우선순위를 데이터로 정한다.

왜 해볼 만한 가치가 있는가

1. 양면 보상 구조: 성공하면 ETH/SETH 반증 또는 그 이상이고, 실패해도 6·7단계에 의해 장벽의 정식화와 회로 하한 증거(7단계에서 회로 클래스 SAT 가속이 나온 경우)가 남는다. 연구 자원이 어느 방향으로든 손실 없이 축적되는 드문 설계다.
2. 완성된 지도 위에서 출발: CSP 이분법은 다항 시간 섬의 경계를 대수 조건으로 완결해 준 희귀한 사례다. 따라서 확장 시도가 막연한 탐색이 아니라 명확한 경계 조건에서 출발하는 잘 정의된 문제가 된다.
3. 중간 성과의 독립적 가치: 지수 밑수의 작은 개선조차 SAT 솔버, 형식 검증, 암호 파라미터 산정에 실용적 파급이 있고, 미세 복잡도(fine-grained complexity) 분야의 환원 네트워크에서 SAT 는 수십 개 문제의 조건부 하한의 출발점이어서, SETH 가 반증되면 그 하한들의 근거가 한꺼번에 사라진다(환원 방향상 SAT 개선이 그 문제들의 알고리즘을 직접 빠르게 하지는 않는다).
4. 도구의 시대적 성숙: 다항식 방법, 스펙트럴 알고리즘, 대수적 CSP 이론이 최근 20년 사이 급성장하여, 과거에는 시도 자체가 불가능했던 기법 조합이 지금은 실행 가능한 연구 프로그램이 되었다.
5. 현실적 마일스톤: P=NP 직접 증명과 달리 특정 회로 클래스에 대한 SAT 가속, 특정 파라미터 층의 준지수화처럼 단계별로 검증 가능한 목표가 있어 실패 판정과 방향 수정이 빠르다.