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

기하 복잡도 이론(GCT)은 permanent 대 determinant 문제를 표현론의 장애물 찾기로 바꾸는 프로그램이다. 이 글은 가장 다루기 쉬운 발생 장애물만으로는 패딩된 permanent 와 determinant 를 가를 수 없다는 2016년의 부정 결과를 피해 가는 수정 경로를 제안한다.

아이디어 개요

기하 복잡도 이론(GCT)은 Mulmuley–Sohoni가 제안한 프로그램으로, permanent 대 determinant 문제(VBP 대 VNP 와 동치인 발리언트류 가설)를 일반선형군 GL의 궤도 폐포(orbit closure) 두 개를 표현론적 장애물(obstruction)로 분리하는 문제로 번역한다. 이 분리(발리언트류 가설)는 비균일 P≠NP 의 대수적 대응물이다 — Bürgisser(2000)에 따르면 GRH 하에서 NP ⊄ P/poly 이면 VP ≠ VNP 이므로, 대수 쪽 분리는 P≠NP 로 가는 길에서 먼저 넘어야 할(그러나 그것만으로 P≠NP 를 주지는 않는) 관문이다.

그러나 Bürgisser–Ikenmeyer–Panova(2016)는 가장 다루기 쉬운 유형인 발생(occurrence) 장애물 — 어떤 기약표현이 한쪽 좌표환에는 등장하고 다른 쪽에는 전혀 등장하지 않는 유형 — 만으로는 "패딩된 permanent" 대 determinant 궤도 폐포를 분리할 수 없음을 증명했다. 이어 Gesmundo–Ikenmeyer–Panova(2017)는 패딩이 필요 없는 행렬 거듭제곱 대각합 모델로 GCT 를 정식화하고, 이 무패딩 정식화에서도 궤도 발생 장애물로는 permanent 의 초선형 하한조차 증명할 수 없음을 보였다.

본 아이디어는 이 부정 결과의 원인을 (a) 패딩이 궤도 폐포 좌표환의 표현 스펙트럼을 포화시켜 발생 정보를 무력화하는 구조적 병리(Kadish–Landsberg 계열 관찰) — 다만 무패딩 설정에서도 발생 장애물이 실패하므로(GIP 2017) 패딩만이 원인은 아니다 —, (b) 발생/비발생이라는 0-1 정보 자체의 빈약함, 두 가지로 진단한다. 그래서 패딩이 필요 없는 동차(homogeneous) 모델 — 행렬 거듭제곱(GIP 2017 이 정식화) 또는 반복 행렬곱(IMM) — 대 permanent 설정에서 곱셈도(multiplicity) 격차 부등식 장애물을 찾는 수정 GCT 경로를 제안한다. GIP 2017 이 이 무패딩 설정에서도 발생 장애물로는 초선형 하한조차 얻을 수 없음을 보였으므로, 곱셈도로 올리는 것이 이 설정에서 필수다. 소규모 사례의 전산 검증과 점근 표현론을 결합해 장애물 후보를 체계적으로 생산·선별하는 파이프라인을 구축하는 것이 실행의 축이다.

구체적 진행 방법

1. 모델 교체의 정식화: determinant 대신 동차 보편 모델(IMM 또는 행렬 거듭제곱)을 쓰는 GCT 설정을 정의하고(행렬 거듭제곱 설정은 GIP 2017 이 이미 정식화했다), 이 설정에서의 분리가 발리언트류 가설(VBP 대 VNP 등)과 P≠NP 연결 사슬에서 갖는 위치를 명확히 정리한다. GIP 2017 의 무패딩 정식화와 그 발생 장애물 부정 결과를 출발점으로, 곱셈도 정보가 그 부정 결과를 피하는지 작은 차수에서 먼저 확인한다.
2. 곱셈도 장애물의 일반 이론 정비: 특정 기약표현 λ에 대해 "permanent 측 곱셈도가 모델 측 곱셈도보다 크다"는 부등식형 장애물의 성립 조건·전이 성질을 정리한다. Dörfler–Ikenmeyer–Panova가 제한된 모델에서 보인 곱셈도 장애물 개념증명을 본 설정으로 확장하는 것이 출발점이다.
3. 전산 파이프라인 구축: 크로네커 계수, 플레티즘 계수, 궤도 폐포 좌표환의 곱셈도를 작은 크기(n=3~5)에서 계산하는 도구를 기존 표현론 소프트웨어와 자체 코드로 구성한다. perm_3의 행렬식 복잡도 확정, 경계(border) 복잡도 하한의 전산 증명 등 알려진 소규모 결과를 재현하며 파이프라인을 검증한다.
4. 데이터 기반 후보 발굴: 소규모 계산에서 곱셈도 격차가 실제로 관측되는 분할 λ의 패턴을 수집하고, 격차가 n이 커질수록 벌어지는 계열을 우선순위로 분류한다.
5. 점근 표현론으로 외삽: 관측된 패턴을 계수의 안정화 현상, 모멘트 폴리토프, 곱셈도 반군(semigroup) 구조 등 점근 도구로 일반 n에 대한 장애물 후보군으로 정제한다.
6. 경계 기하 연구: 곱셈도 장애물의 최대 난점은 모델 측 곱셈도의 상한 확보이므로, determinant 궤도 폐포 경계 성분 분석(Landsberg–Manivel–Ressayre 2013, Hüttenhain–Lairez 2016)을 IMM류 모델로 이식해 경계 성분 분류와 좌표환 상한 도구를 개발한다.
7. 인접 문제에서 방법론 보정: 발생 장애물이 실제 하한을 낸 성공 사례인 행렬곱 텐서의 경계 랭크 하한(Bürgisser–Ikenmeyer)에서, 곱셈도 장애물이 기존 결과를 재현·개선하는지 시험해 도구의 힘을 측정한다.
8. 장벽·no-go 병행 점검: 개발된 기법이 relativization, natural proofs, algebrization 장벽과 맺는 관계를 문서화하고, 곱셈도 장애물에 대한 새로운 no-go 정리가 성립할 위험을 능동적으로 탐색한다(성립한다면 그 자체가 중요한 성과). 마지막으로 분리 성과 → VNP ⊄ (경계) VBP 까지의 고리를 정리하고, 거기서 불리언 쪽(NP ⊄ P/poly)으로 넘어가는 알려진 함의는 반대 방향뿐(GRH 하 NP ⊄ P/poly ⇒ VP ≠ VNP)임을 밝혀, 대수 분리에서 P≠NP 로 가려면 무엇이 더 필요한지를 정리한다.

왜 해볼 만한 가치가 있는가

1. BIP 부정 결과는 GCT 전체의 사망 선고가 아니라 "패딩 + 발생 장애물" 조합에 대한 사망 선고다. 곱셈도 장애물은 BIP 가 명시적으로 배제하지 않은 경로이며(무패딩 모델에서도 발생 장애물은 GIP 2017 이 배제했다), 제한된 설정에서 곱셈도 장애물이 실제로 분리를 이룬 개념증명이 이미 존재한다.
2. 기존 3대 장벽과의 관계가 유리하다고 본다. 대수기하·표현론 기반 하한 기법은 relativization과 algebrization 장벽의 적용 범위 밖이라고 보지만, 목표 사슬 끝의 P≠NP 단계에는 두 장벽이 그대로 적용된다. GCT 장애물은 대칭성이라는 극히 특수한 성질을 이용하므로 natural proofs의 대량성(largeness) 조건을 회피할 여지가 있다는 분석(Grochow 등)이 있다. 반대로 대수적 자연 증명 장벽이 있을 수 있다는 근거(Forbes–Shpilka–Volk 2017, Grochow–Kumar–Saks–Saraf 2017)도 있다.
3. 최종 목표에 실패하더라도 산출물이 남는다. 크로네커·플레티즘 계수의 조합적 이해(대수적 조합론의 오랜 난제), 궤도 폐포 경계 성분 분류, 곱셈도 장애물에 대한 no-go 정리 등은 각각 독립적인 논문 가치가 있다.
4. P vs NP 접근법 중 드물게 전산으로 검증 가능한 중간 이정표(소규모 곱셈도 계산, 소규모 복잡도 확정)가 촘촘히 존재해, 진척을 측정하며 방향을 수정할 수 있는 공학적 프로그램이다.
5. 같은 도구 상자가 인접 문제(행렬곱 텐서의 경계 랭크 하한)에서 실제 하한을 산출한 전력이 있어, 방법론의 현실성이 이미 부분적으로 입증되어 있다.