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

정답을 내는 연구가 아니라, 정답이 어디에 숨을 수 있는지를 보여 주는 지형도를 만드는 연구다. 회로 하한이나 P≠NP 가 어떤 공리계에서 증명될 수 없는지를 체계적으로 정리하자는 제안이다.

아이디어 개요

P vs NP를 정면으로 공격하는 대신, "이 명제가 현재 우리가 쓰는 공리계에서 애초에 증명 가능한가"라는 메타 수준의 질문을 체계적으로 파고드는 연구다. 구체적으로는 유계 산술(bounded arithmetic)의 약한 이론들 — PV₁, S¹₂, T¹₂, APC₁ 등 — 에서 회로 하한 명제의 증명 불가능성을 보인 기존 결과들 — 암호 가정 아래의 조건부 결과(Razborov 1995, Krajíček 1997)와, 준지수·근사 불가·공비결정 회로 같은 강한 형태의 하한 명제에 대한 무조건 결과(Pich–Santhanam 2021 등) — 을 하나의 지도로 통합하고(P≠NP 의 표준 형식화가 PV₁ 에서 증명 불가능한지는 아직 모른다), 자연 증명(natural proofs) 장벽을 증명 불가능성의 언어로 옮기는 형식적 다리를 정비한다.

아울러 "P≠NP 가 PA+Π₁(PA 에 참인 Π₁ 문장을 모두 더한 체계)로부터 독립이라면 NP 는 크기 n^{α(n)}(α 는 역 아커만 함수처럼 아주 느리게 자라는 함수)인 회로를 가지며, 균일하게도 무한히 많은 긴 구간의 n 에서 SAT 를 n^{α(n)} 시간에 푸는 알고리즘이 있다"는 Ben-David–Halevi(와 Kurtz–O'Donnell–Royer)의 정리 — 알려진 독립성 증명 기법은 모두 PA+Π₁ 로부터의 독립을 보이므로, 그 기법으로 독립을 보이면 이 귀결이 따른다 — 를 재검토하여, 독립성 시나리오 자체가 갖는 계산적 함의를 정밀하게 다듬는다.

최종 목표는 독립성의 완결된 증명이 아니라, "어느 이론까지 증명 불가능이 확립되어 있고, 그 경계를 한 단계 올리려면 정확히 무엇이 필요한가"를 명시한 프로그램형 정리와 미해결 보조 문제 목록을 산출하는 것이다. 즉 정답을 내는 연구가 아니라, 정답이 어디에 숨을 수 있는지를 보여 주는 지형도를 만드는 연구다.

구체적 진행 방법

1. 문헌 지도 작성: Buss의 유계 산술 위계와 각 이론이 포착하는 계산 능력(다항시간 함수, 다항 위계의 각 층 등)의 대응 관계를 정리하고, "어떤 이론이 어떤 하한 명제를 증명할 수 없다"는 기존 결과들을 이론 × 명제의 격자 위에 배치한다.
2. 형식화 비교: P≠NP를 산술 문장으로 형식화하는 표준 방식과 그 변형들(초다항 회로 하한 형태, 특정 알고리즘의 실패를 말하는 형태 등)을 나란히 놓고, 어느 형식화가 어느 이론에서 표현 가능하며 형식화 간 동치가 어느 이론에서 성립하는지 표로 정리한다. 독립성 논의는 형식화 선택에 민감하므로 이 단계가 이후 모든 논의의 기준점이 된다.
3. 기존 증명 불가능성 결과의 재서술: Razborov의 자연 증명–유계 산술 연결, Krajíček의 실행 가능 보간(feasible interpolation), Pich·Santhanam 계열의 최근 결과를 하나의 공통 프레임(가정 – 대상 이론 – 증명 불가능한 명제)으로 다시 쓰고, 각 결과가 실제로 커버하는 범위와 자주 과장되는 범위를 구분한다.
4. 자연 증명 장벽의 형식적 대응물 세분화: "강한 의사난수 생성기가 존재하면 특정 유계 산술 이론은 초다항 회로 하한을 증명할 수 없다"는 유형의 조건부 결과에서, 암호학적 가정을 약화하거나 대상 이론을 넓힐 수 있는 지점을 후보로 추려 각각의 장애물을 기술한다.
5. 독립성의 계산적 함의 경계 긋기: Ben-David–Halevi 논증과 Aaronson의 독립성 서베이를 구조 분해하여, "독립이라면 실질적으로는 P=NP에 가까운 세계"라는 함의가 어떤 형식화, 어떤 기저 이론(PA+Π₁ 로부터의 독립이 전제이며 PA 만으로부터의 독립은 이 귀결을 주지 않는다), 어떤 추가 가정에 의존하는지 정확히 명시하고, 함의가 무너지는 시나리오도 함께 목록화한다.
6. 경계 상승 시도 설계: PV₁/S¹₂ 수준에서 확립된 증명 불가능성을 더 강한 유계 산술 이론, 나아가 유계가 아닌 귀납을 가진 PA 단편(IΣ₁ 등)으로 끌어올리기 위한 후보 전략(증명 복잡도 하한과의 연동, 위트니스 추출 실패 사례 구성 등)을 나열하고, 각 전략이 요구하는 전제 조건과 예상 난관을 점검한다. 이 단계는 실제 증명이 아니라 공격 계획서 수준으로만 작성한다.
7. 산출물 정리: "증명 불가능성 지도 + 형식화 의존성 표 + 시나리오별 계산적 귀결 + 미해결 보조 문제 목록"의 4부 구성 프로그램 논문으로 묶고, 각 보조 문제에 예상 난이도와 해결 시 파급력을 주석으로 달아 후속 연구의 진입점을 만든다.

왜 해볼 만한 가치가 있는가

1. 알려진 직접 증명 기법 대부분이 상대화·자연 증명·대수화 장벽에 걸리는 상황에서, 메타 수준 접근은 "왜 어려운가"를 추측이 아닌 정리의 형태로 축적할 수 있는 몇 안 되는 경로라고 본다.
2. 유계 산술에서의 증명 불가능성은 증명 복잡도 하한과 밀접히 대응해서(보편 유계 문장에 대해 PV ↔ Extended Frege, 유계 깊이 이론 ↔ 유계 깊이 Frege), 중간 산출물 하나하나가 그 자체로 독립적 가치를 갖는다. 최종 목표에 도달하지 못해도 성과가 남는 구조다.
3. 독립성 시나리오의 계산적 함의는 역설적으로 강력하다. "PA+Π₁ 로부터 독립이라면 NP 가 다항에 거의 붙은 n^{α(n)} 크기 회로를 가진다"는 유형의 결과는 독립성 가능성을 좁히는 동시에, P≠NP에 대한 통상의 믿음을 정량화하는 도구가 된다.
4. 새로운 수학을 통째로 발명하기보다 기존 결과들을 정밀하게 잇고 경계를 명시하는 작업이 중심이라, 단계별로 검증 가능한 산출물이 나오고 실패 위험이 분산된다.
5. 형식화 의존성 표와 보조 문제 목록은 이 방향의 후속 연구자들이 공통으로 쓸 수 있는 기반 자료가 되므로, 단일 논문 이상의 공공재적 가치가 있다.