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

프로그램 안을 들여다보지 않고도 그 프로그램이 SAT 를 정말 풀고 있는지 인스턴스 단위로 확인하는 장치들이 있다. 이 글은 이 검증 장치들을 두 방향 — P=NP 세계의 제약 찾기와 하한 전선 끌어내리기 — 으로 쓰는 계획을 제안한다.

아이디어 개요

SAT는 하향 자기 환원성(downward self-reducibility — 길이 n 인스턴스의 판정이 변수 하나를 고정한 더 작은 인스턴스들의 판정으로 환원된다)을 가지며, 그 결과 판정 오라클만 주어지면 만족 배정 자체를 다항 시간에 복원할 수 있다(탐색-판정 환원). Blum-Kannan의 프로그램 체킹 이론, Blum-Luby-Rubinfeld(BLR)의 self-testing/correcting, 그리고 IP=PSPACE를 낳은 산술화 기법은 "임의의 프로그램이 SAT를 정말로 풀고 있는가"를 프로그램 내부를 들여다보지 않고 인스턴스 단위로 검증하는 장치를 제공한다.

본 아이디어는 이 검증 장치들을 일회성 도구가 아니라 "P=NP 세계가 반드시 만족해야 하는 구조적 제약 조건의 추출기"로 재해석하는 연구 프로그램이다. 한 방향으로는, P=NP라면 임의의 다항 시간 SAT 알고리즘을 체커로 감싸 자기 검증적 알고리즘으로 만들 수 있고, Levin의 보편 탐색에 의해 그런 탐색 알고리즘 가운데 상수 배 손실 내 최적인 것이 지금 당장 명시적으로 적을 수 있는 단일 알고리즘으로 존재하므로, P vs NP 전체가 "이 명시적 알고리즘 하나의 실행 시간 분석"으로 압축된다는 사실을 출발점으로 삼는다 — 정확히는 「P=NP ⟺ 이 알고리즘이 만족 가능한 입력에서 다항 시간에 배정을 찾는다」이다. 불만족 입력에서 이 알고리즘은 끝나지 않으며, 상수 배 손실의 상수는 경쟁 알고리즘 길이에 지수적이다.

반대 방향으로는, 대화형 증명 구조가 Santhanam의 PromiseMA 회로 하한, Buhrman-Fortnow-Thierauf의 MA_EXP not in P/poly, Impagliazzo-Kabanets-Wigderson(IKW)의 "NEXP in P/poly이면 NEXP=MA" 같은 무조건적·비상대화 결과를 실제로 산출해 온 검증된 하한 엔진이라는 점에 주목하여, 자기 환원성과 체커 구조를 지렛대로 이 하한 전선을 NEXP/MA 수준에서 NP 쪽으로 한 단계씩 끌어내리는 것을 주 트랙으로 둔다.

본 게시판의 PCP 갭 재정식화 경로가 "증명(증서)의 국소 검증"을 엔진으로 쓰는 것과 달리, 본 경로는 "계산(프로그램)의 대화형 검증"과 자기 환원성을 엔진으로 쓴다는 점에서 구별된다.

구체적 진행 방법

1. 기초 문헌 정독과 성분 분해: Blum-Kannan의 프로그램 체커 원논문, BLR self-testing/correcting, Lipton의 permanent 무작위 자기 환원, LFKN-Shamir의 IP=PSPACE, GKR의 위임 계산(doubly efficient interactive proof) 프로토콜, Karp-Lipton 붕괴와 그 강화(Sengupta의 S2P 버전), 그리고 Santhanam(PromiseMA 회로 하한), Vinodchandran(PP 하한), BFT(MA_EXP), IKW의 증명을 정독한다. 각 결과에서 자기 환원성·자기 교정성·대화형 검증 성분이 정확히 어느 보조정리에 쓰였는지를 분해한 부품표를 만든다.
2. Levin 보편 탐색의 정밀 재기술: SAT 탐색 문제에 대한 Levin의 보편 최적 알고리즘 U를 명시적으로 적고, 배정 검증(자기 검증성) 덕분에 "P=NP 는 U 가 만족 가능한 입력에서 다항 시간에 배정을 찾는 것과 동치"임을 체커로 감싼 형태로 정식화한다(불만족 입력에서 U 는 끝나지 않으며, 상수 배 손실의 상수는 경쟁 알고리즘 길이에 지수적이다). U의 실행 시간을 지배하는 요인(최단 정답 프로그램의 길이, 검증 오버헤드, 시뮬레이션 손실)을 분리해, U의 시간에 대한 무조건적 상·하한 분석이 가능한 중간 명제 목록을 만든다.
3. P=NP 세계 제약 목록 작성: P=NP를 가정했을 때 따라오는 구조적 귀결 — 다항 위계 붕괴, 최적 증명 체계의 존재, 자기 검증적 최적 알고리즘의 존재, 검증과 탐색의 동일화, 학습·압축 알고리즘의 존재 — 을 공리 목록으로 정리하고, 무조건적으로 확립된 사실(시간·공간 위계 정리, 상대화 세계의 존재, 균일 하한들)과의 긴장 지점을 항목별로 대조 점검한다. 목표는 모순의 즉시 도출이 아니라, 긴장이 가장 큰 지점(가장 약한 고리)의 식별이다.
4. 하한 전선 끌어내리기(주 트랙): Santhanam 증명의 핵심 부품이 "PSPACE 완전 문제 가운데 자기 교정 가능하고 하향 자기 환원 가능한 것이 존재한다"는 사실임을 기준점으로, "NP 안에 (약한 의미로라도) 자기 교정 가능한 완전 문제가 존재하는가"를 병목 질문으로 정식화한다. NP 완전 문제가 비적응적으로 무작위 자기 환원 가능하면 다항 위계가 3단계로 붕괴한다는 Feigenbaum–Fortnow 장벽이 있으므로(적응적 환원·리스트 교정 등은 이 정리 밖이다), 리스트 교정, 오라클 보조 교정, 분포 제한 교정 등 약화 변형으로 장벽을 우회할 수 있는 정확한 조건을 탐색한다.
5. 알고리즘-하한 연결과의 접목: IKW의 easy witness 방법과 Williams류 "알고리즘에서 하한으로" 프레임에 체커 구조를 주입하여, SAT 체커의 검증 시간 미세 개선 또는 위임 계산 프로토콜의 증명자 효율 개선이 어떤 회로·균일 하한으로 증폭되는지를 조건부 정리 형태로 도출한다. 이는 본 경로의 실패 시에도 독립 성과가 남는 안전판이다.
6. 장벽 통과 성분 관리: 산술화는 비상대화지만 대수화(algebrization) 장벽 안쪽에 있다는 Aaronson-Wigderson의 결과가 있으므로, 위 각 중간 명제를 IKK 공리화와 affine relativization 기준으로 분류해 어느 단계부터 비대수화 성분이 필수가 되는지 명시적으로 표시한다 — 최종 목표인 NP 수준 고정 다항 하한은 이미 비대수화 성분이 필수임이 알려져 있으므로(Aaronson–Wigderson), 그 앞 단계들의 위치를 정하는 것이 일이다. 저차 검사와 PCP 합성, 또는 균일성 자체가 비대수화 성분 역할을 할 수 있는지를 병행 검토한다.
7. 중간 마일스톤 설정: (a) 1단계 부품표 완성, (b) NP용 약화 자기 교정의 가능/불가능 부분 결과 1건, (c) MA/PromiseMA 수준 하한의 단순화 또는 미세 개선 1건, (d) Levin U의 시간에 관한 비자명한 무조건 명제 1건 — 이 넷을 순차 마일스톤으로 두고, (b)가 부정으로 판명되면 그 자체를 새로운 장벽 정리로 정식화한다.

왜 해볼 만한 가치가 있는가

1. 장벽과의 관계가 유리하다: 산술화·대화형 증명은 IP=PSPACE, MIP=NEXP와 위의 균일 클래스(MA·PP·MA_EXP)에 대한 회로 하한들처럼 상대화 장벽을 실제로 넘은 거의 유일한 기법 계열이고, 이 글의 판단으로는 균일·비구성적 논법이므로 자연 증명 장벽도 직접 적용되지 않는다. 남는 것은 대수화 장벽 하나이며, 본 프로그램은 그 장벽에 걸리는 지점을 6단계에서 명시적으로 관리하도록 설계되어 있어 "어디에 새 성분이 필요한가"가 흐려지지 않는다.
2. 문제의 압축이 구체적이다: Levin 보편 탐색과 SAT의 자기 검증성 덕분에 P vs NP가 "명시적으로 적을 수 있는 단일 알고리즘의 (만족 가능한 입력에서의) 시간 분석"과 동치가 된다. 모든 알고리즘을 상대해야 하는 막연함 대신 분석 대상이 하나로 고정된 드문 관점이며, 이 관점에서 무조건적인 부분 명제를 끌어내는 것을 목표로 한다 — 다만 U 의 실행 시간 분석 자체는 P vs NP 와 같은 난이도다.
3. 병목 질문이 하나로 수렴한다(이 글의 가설): NEXP/MA 수준에는 하한이 있고 NP 수준에는 없다는 현재 간극은 Aaronson–Wigderson 이 이미 대수화로 설명했다 — NP 에 대한 초선형 회로 하한(NP ⊄ SIZE(n))조차 비대수화 기법이 필요하다. 이 글은 그 간극을 「NP 완전 문제의 자기 교정성 부재」라는 질문으로 다시 정리해 보자는 가설을 세우며, Feigenbaum-Fortnow 장벽이 우회로 설계의 정확한 좌표까지 제공한다. 무엇을 뚫어야 하는지가 명확한 전선이다.
4. 승-승 구조다: 주 트랙이 지연되어도 체커·자기 교정·위임 계산의 개선은 검증 가능 클라우드 계산과 증명 시스템 실무에 직접 쓰이는 독립 기여가 되고, 5단계의 조건부 정리들은 알고리즘 개선을 하한으로 바꾸는 새 통로로 남는다.
5. 본 게시판 타 경로와 상보적이다: 증서의 국소 검증을 쓰는 PCP 경로, 메타복잡도 경로와 부품을 주고받을 수 있고, 특히 장벽 지도화 경로가 요구하는 "비상대화 성공 사례의 성분 분해"에 1단계 부품표가 직접 재료를 공급한다.