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

순서가 주어진 유한 구조 위에서는 P 대 NP 가 두 논리 FO(LFP) 와 ∃SO 의 표현력을 가르는 문제와 정확히 같다. 이 글은 구조의 대칭성을 눈금으로 삼아, 하한이 증명되는 쪽과 P 를 포획하는 쪽에서 동시에 다가가는 연구 계획을 제안한다.

아이디어 개요

Fagin 정리에 의해 NP는 존재 이차논리(∃SO)로, Immerman–Vardi 정리에 의해 P는 순서가 주어진 유한 구조 위에서 최소고정점 논리 FO(LFP)로 정확히 특성화된다. 따라서 순서 구조 위에서 FO(LFP)와 ∃SO의 표현력을 분리하는 것은 P≠NP와 정확히 동치이지만, 순서가 주어지면 FO(LFP)가 P 전체를 표현하므로(그때 구조는 자기동형도 없다), 페블 게임·Cai–Fürer–Immerman 구성처럼 구별 불가능한 구조 쌍을 만드는 논리적 하한 기법이 곧 P 하한이 되어 버려 지금의 기법으로는 닿지 않는다는 것이 핵심 장벽이다.

반대로 순서 없는 구조에서는 대칭성을 지렛대로 삼은 무조건적 정의불가능성 하한이 실제로 증명되고 있으나, 그 대가로 "P를 포획하는 논리"가 무엇인지 자체가 미해결이며(Chandra–Harel/Gurevich 문제), CPT(Choiceless Polynomial Time)가 유력 후보로 남아 있다.

본 아이디어는 이 두 극단 사이에 "대칭성 사다리" — 입력 구조의 자기동형군이 얼마나 풍부한지를 매개변수로 하는 구조 클래스의 위계 — 를 놓고, 위쪽(고대칭)에서는 CPT와 대칭 회로에 대한 하한을, 아래쪽(저대칭·준순서)에서는 P 포획(capture) 결과를 각각 확장하여 양방향에서 협공하는 연구 프로그램이다. 이때 대칭 회로 하한이 말하는 「대칭」은 입력 구조의 자기동형군이 아니라 정점 이름바꾸기(대칭군 S_n)에 대한 회로의 불변성이므로, 사다리의 매개변수(2단계)와는 구별한다. 목표는 P vs NP를 "어느 대칭성 수준까지 하한 기법이 생존하는가"라는 정량적 문턱 문제로 재정식화하는 것이다.

구체적 진행 방법

1. 기반 문헌 카탈로그화: Fagin 정리, Immerman–Vardi 정리, 카운팅 고정점 논리 FPC의 한계(CFI 구성), CPT의 정의와 지지 정리(support theorem, Blass–Gurevich–Shelah), 대칭 회로 하한(Anderson–Dawar, Dawar–Wilsenach) 계열의 증명 구조를 정리하되, 각 하한 증명이 자기동형군의 어떤 성질(추이성, 최소 지지 크기, 궤도 구조)을 실제로 소비하는지 명시적으로 추출한다.
2. 대칭성 매개변수 설계: 색 클래스 크기에 상한이 있는 선주문(preorder) 구조, 궤도 수, 지지 크기 등의 후보 중에서 완전순서(강성 구조) ↔ 완전무순서(고대칭 구조) 사이를 매끄럽게 보간하는 매개변수와 그에 따른 구조 클래스 위계를 정의한다.
3. 벤치마크 문제 고정: 대칭성이 풍부한 부호화를 갖는 NP-완전 문제(3-채색, 해밀턴성 등)와, 이미 FPC를 P로부터 분리해 준 CFI형 문제·유한체 위 선형방정식계 문제를 목표 문제군으로 선정한다.
4. 하한 프론트 진행: 위계의 고대칭 구간에서 CPT(카운팅 포함) 및 대칭 다항크기 회로에 대해 목표 문제의 정의불가능성을 공략한다. 지지 정리와 전단사(bijective) 페블 게임을 대칭성 매개변수에 따라 일반화된 형태로 재구성하는 것이 기술적 핵심이다.
5. 포획 프론트 진행: 반대편 끝에서 CPT 또는 그 확장이 P를 포획하는 구조 클래스를 넓힌다. 그래프 정준화(canonization) 기법 — 배제 마이너 클래스, 유계 랭크폭 클래스 등에서 알려진 포획 결과 — 을 2단계 위계의 언어로 재배치하고 한 단계씩 위로 밀어 올린다.
6. 문턱 지도 작성: 두 프론트가 각각 어느 대칭성 수준에서 멈추는지를 정량화하여 "기법 생존 지도"를 만들고, 두 프론트 사이 갭 구간에서 실패 원인을 유형별로 분류한다.
7. 장벽 감사: 각 하한 논증이 Razborov–Rudich 자연 증명의 largeness/constructivity 조건을 만족하게 되는 지점이 어디인지, 상대화·대수화 장벽과의 관계는 어떤지를 단계별로 점검하여, 장벽을 우회하는 구간과 충돌하기 시작하는 구간을 문서화한다.
8. 중간 이정표 설정: 최종 목표 이전의 독립적 성과 단위 — 예컨대 어떤 NP-완전 문제가 CPT로 정의불가능함을 보이는 것(그 자체로 서술 복잡도의 중대한 미해결 문제), 특정 위계 구간에서의 새 포획 정리 — 를 논문 단위 목표로 설정하고 우선순위를 부여한다.

두 프론트

왜 해볼 만한 가치가 있는가

1. 기계 모형 없는 재정식화: 튜링 기계와 시간 계층 대신 논리의 표현력이라는 순수 모형론적 대상을 다루므로, 파악 불가능한 "임의의 다항시간 알고리즘" 전체가 아니라 구문적으로 닫힌 논리를 상대하게 된다. 표현력 하한은 오라클 문장으로 진술되지 않아 상대화 장벽을 피할 여지가 있다고 본다. 다만 순서 구조 위 분리는 P ≠ NP 와 정확히 동치이므로, 그것을 증명하는 논증은 결국 비상대화여야 한다.
2. 자연 증명 장벽과의 관계가 유리하다고 본다: 대칭 회로·CPT 하한은 제한된(대칭) 계산 클래스에 대한 무조건 하한이며, 대칭 회로·CPT 가 다루는 것은 동형 불변 질의라 Razborov–Rudich 틀이 직접 적용되지 않는다고 본다(이 글의 판단). 7단계의 장벽 감사는 이 판단이 대칭성을 완화할수록 어디까지 유지되는지를 추적하므로, 프로그램이 실패하더라도 "장벽 지형도"라는 독립적 부산물이 남는다.
3. 동치의 정확성: 순서 구조에서의 FO(LFP)와 ∃SO 분리는 P≠NP의 근사물이 아니라 정확한 동치다. 즉 이 경로는 우회로가 아니라 같은 문제의 다른 좌표계이며, 사다리 위에서의 모든 전진이 본 문제와의 거리 단축으로 그대로 환산된다.
4. 이정표의 독립 가치: "순서 없는 구조에서 P를 포획하는 논리가 존재하는가"(Gurevich 는 존재하지 않는다고 추측했고, 그 추측이 참이면 Fagin 정리에 의해 P ≠ NP)와 "NP-완전 문제의 CPT 정의불가능성"은 각각 유한 모형 이론 최상위의 미해결 문제이므로, 최종 목표에 도달하지 못해도 각 단계가 자체 완결적 성과가 된다.
5. 협공 구조의 리스크 분산: 하한 프론트와 포획 프론트는 실패 정보를 서로 교환한다 — 포획이 안 되는 대칭성 구간은 하한 공략의 다음 목표가 되고, 하한이 막히는 구간은 새로운 정준화 알고리즘의 후보지가 된다. 어느 쪽으로 진전이 나든 문턱 지도는 갱신되며, 두 프론트가 같은 구조 클래스에서 만나고 — 그 클래스에서 논리가 P 를 포획하며 목표 문제가 여전히 NP 완전이라면 — 그 지점이 곧 P vs NP 의 해결 지점이다.