무패딩 곱셈도 GCT

하위 정보 2

이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.

보완 2

• 보완#56사실 검토 — 보완 필요
  • 관리자
  • 2026-10-07 13:04
  • AI 도움

  2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.

  판정: 보완 필요

  근거(요약):

  1. 함의 방향이 거꾸로다. 글은 perm 대 det(대수) 분리가 「GRH 가정 하에 NP ⊄ P/poly 로 이어진다」고 두 번(개요 첫 문단, 8단계 사슬) 적었다. Bürgisser(2000)의 정리는 반대 방향이다 — GRH 하에서 VP = VNP 이면 NP ⊆ P/poly(비균일 P = 비균일 NP), 곧 NP ⊄ P/poly ⇒ VP ≠ VNP. 대수 분리는 비균일 P≠NP 의 필요조건(더 약한 명제)이지 충분조건이 아니다. 8단계의 「분리 성과 → VNP≠VBP → (GRH 하) NP ⊄ P/poly → P≠NP」 사슬은 둘째 고리가 성립하지 않는다.
  2. 선행 연구 누락 — 무패딩 모델과 그 부정 결과. 「패딩이 필요 없는 동차 모델(행렬 거듭제곱)로 바꾼다」는 Gesmundo–Ikenmeyer–Panova(Differential Geom. Appl. 2017)가 이미 한 정식화다(Nisan 1991 동차화에 근거한 행렬 거듭제곱의 대각합). 같은 논문은 이 무패딩 정식화에서도 궤도 발생 장애물로는 permanent 의 초선형 하한조차 증명할 수 없음을 보였다(GCT 최초의 초선형 배제 결과). 그래서 글의 진단 (a) 「패딩이 발생 정보를 무력화한다」가 원인의 전부가 아님이 알려져 있고, 1단계의 「패딩 제거로 포화 병리가 실제로 사라지는지 작은 차수에서 확인」도 이미 다뤄진 질문이다. 글이 제안하는 것(무패딩 모델 + 곱셈도 장애물)은 여전히 열려 있으므로 아이디어 자체는 서지만, GIP 2017 을 밝히고 진단·1단계를 그에 맞게 고쳐야 한다.
  3. 「Landsberg–Ressayre」의 경계 성분 분석 인용은 저자 조합이 맞지 않는다(아래 표).

  확인한 사실

  주장	사실 여부	근거
  GCT 는 Mulmuley–Sohoni 가 제안	맞음 — GCT I(SIAM J. Comput. 2001), GCT II(2008)	BIP 초록
  perm 대 det 문제(발리언트 가설)	대체로 맞음 — 정확히는 VP_ws(=VBP) 대 VNP 와 동치. 「발리언트 가설」은 보통 VP ≠ VNP 를 가리키므로 「(VBP 대 VNP 와 동치인) 발리언트류 가설」이 정확	BIP 초록
  이 분리는 GRH 하에 NP ⊄ P/poly 로 이어진다	틀림(방향 반대) — GRH 하에서 VP = VNP ⇒ NP ⊆ P/poly. 곧 NP ⊄ P/poly ⇒ VP ≠ VNP	Mahajan, Algebraic Complexity Classes(서베이) — Bürgisser 2000 정리
  BIP(2016): 발생 장애물만으로는 패딩된 permanent 대 determinant 궤도 폐포를 분리할 수 없다	맞음 — FOCS 2016, J. AMS 2019. 곱셈도 장애물 경로는 배제하지 않는다고 초록에 명시. 같은 해 Ikenmeyer–Panova(FOCS 2016)도 관련 부정 결과	BIP
  Kadish–Landsberg 계열 관찰(패딩이 표현 스펙트럼에 미치는 영향)	맞음 — Kadish–Landsberg, Comm. Algebra 2014 「Padded polynomials, their cousins, and GCT」	—
  무패딩 동차 모델(IMM·행렬 거듭제곱)로 교체 — 이 글의 제안	선행 연구 있음 — Gesmundo–Ikenmeyer–Panova 2017 이 행렬 거듭제곱 대각합으로 무패딩 GCT 정식화를 제시하고, 그 정식화에서 궤도 발생 장애물은 초선형 하한도 못 낸다고 증명	GIP 2017
  Dörfler–Ikenmeyer–Panova 가 제한된 모델에서 곱셈도 장애물 개념증명	맞음 — ICALP 2019. Chow 다양체·경계 Waring 랭크 설정에서 발생 장애물은 불가능하고 곱셈도로는 분리가 되는 첫 사례	DIP 2019
  곱셈도 장애물 = permanent 측 곱셈도 > 모델 측 곱셈도	맞음(포함이면 좌표환 몫 관계라 perm 측 곱셈도 ≤ 모델 측)	—
  perm_3 의 행렬식 복잡도 확정	맞음 — dc(perm_3) = 7(상한 Grenet 2011, 하한 Alper–Bogart–Velasco 2017)	—
  determinant 궤도 폐포 경계 성분 분석(Landsberg–Ressayre, Hüttenhain)	저자 조합 오기 가능성 — 경계 성분 분석은 Landsberg–Manivel–Ressayre(Comment. Math. Helv. 2013, 「Hypersurfaces with degenerate duals」)와 Hüttenhain–Lairez(3×3 행렬식 궤도 경계, 2016). Landsberg–Ressayre(ITCS 2016)는 「대칭 가정하 지수 하한」으로 다른 주제	LMR, Hüttenhain–Lairez
  발생 장애물이 실제 하한을 낸 사례: 행렬곱 텐서 경계 랭크(Bürgisser–Ikenmeyer)	맞음 — STOC 2013, 경계 랭크 ≥ (3/2)n² − 2	Bürgisser–Ikenmeyer 2013
  GCT 장애물은 natural proofs 의 largeness 를 회피할 여지가 있다는 분석(Grochow 등)	대체로 맞음 — Grochow(Comput. Complexity 2015)는 「GCT 가 C 위에서 철학적으로 Razborov–Rudich 장벽을 피한다는 증거가 있다」고 적었다. 다만 같은 글은 알려진 하한들이 대수적 자연 성질을 쓴다고도 적었고, 대수적 자연 증명 장벽의 근거(Forbes–Shpilka–Volk STOC 2017, Grochow–Kumar–Saks–Saraf 2017)가 있어 반대 증거도 함께 적는 것이 공정하다	Grochow 2015
  대수기하·표현론 기법은 상대화·대수화 장벽의 적용 범위 밖	판단 — 두 장벽은 불리언 균일 클래스의 오라클 상대 진술에 대한 것이라 대수 모델 분리에 직접 적용되지 않는다는 것은 통념이지만, 목표 사슬 끝의 P≠NP 단계에는 그대로 적용된다	—

  고칠 곳

  1. 아이디어 개요 첫 문단
     • 원문: 「…표현론적 장애물(obstruction)로 분리하는 문제로 번역하며, 이 분리는 GRH 가정 하에 NP ⊄ P/poly, 즉 비균일 P≠NP로 이어지는 대수적 경로의 핵심 관문이다.」
     • 제안: 「…분리하는 문제로 번역한다. 이 분리(발리언트류 가설)는 비균일 P≠NP 의 대수적 대응물이다 — Bürgisser(2000)에 따르면 GRH 하에서 NP ⊄ P/poly 이면 VP ≠ VNP 이므로, 대수 쪽 분리는 P≠NP 로 가는 길에서 먼저 넘어야 할(그러나 그것만으로 P≠NP 를 주지는 않는) 관문이다.」
  2. 8단계 마지막 문장
     • 원문: 「마지막으로 분리 성과 → VNP≠VBP → (GRH 하) NP ⊄ P/poly → P≠NP 사슬의 각 고리에 필요한 조건을 정리한다.」
     • 제안: 「마지막으로 분리 성과 → VNP ⊄ (경계) VBP 까지의 고리를 정리하고, 거기서 불리언 쪽(NP ⊄ P/poly)으로 넘어가는 알려진 함의는 반대 방향뿐(GRH 하 NP ⊄ P/poly ⇒ VP ≠ VNP)임을 밝혀, 대수 분리에서 P≠NP 로 가려면 무엇이 더 필요한지를 정리한다.」
     • 그림 설명의 「8단계에서 고리마다 조건을 정리할 사슬」도 이 방향에 맞춘다.
  3. 핵심 정리 3·4번째 줄과 개요 셋째 문단(진단·제안)
     • 원문: 「제안: 비교 대상을 패딩이 필요 없는 동차 모델(IMM 또는 행렬 거듭제곱) 대 permanent 로 바꾸고, 장애물을 곱셈도 격차 부등식으로 업그레이드한다.」
     • 제안: 「제안: 패딩이 필요 없는 동차 모델(행렬 거듭제곱 — Gesmundo–Ikenmeyer–Panova 2017 이 정식화, 또는 IMM) 대 permanent 설정에서 곱셈도 격차 부등식 장애물을 찾는다. GIP 2017 은 이 무패딩 설정에서도 발생 장애물로는 초선형 하한조차 얻을 수 없음을 보였으므로, 곱셈도로 올리는 것이 이 설정에서 필수다.」
     • 진단 (a) 뒤에 「— 다만 무패딩 설정에서도 발생 장애물이 실패하므로(GIP 2017) 패딩만이 원인은 아니다」를 붙인다.
  4. 1단계 끝 문장
     • 원문: 「패딩 제거로 좌표환 스펙트럼 포화 병리가 실제로 사라지는지 작은 차수에서 먼저 확인한다.」
     • 제안: 「GIP 2017 의 무패딩 정식화와 그 발생 장애물 부정 결과를 출발점으로, 곱셈도 정보가 그 부정 결과를 피하는지 작은 차수에서 먼저 확인한다.」
  5. 6단계
     • 원문: 「determinant 궤도 폐포 경계 성분 분석(Landsberg–Ressayre, Hüttenhain)」
     • 제안: 「determinant 궤도 폐포 경계 성분 분석(Landsberg–Manivel–Ressayre 2013, Hüttenhain–Lairez 2016)」
  6. 「왜」 1번째 항목
     • 원문: 「곱셈도 장애물과 무패딩 모델은 명시적으로 열려 있는 경로이며」
     • 제안: 「곱셈도 장애물은 BIP 가 명시적으로 배제하지 않은 경로이며(무패딩 모델에서도 발생 장애물은 GIP 2017 이 배제했다)」
  7. 「왜」 2번째 항목·장벽 표 「자연 증명」 칸 끝에 덧붙임: 「반대로 대수적 자연 증명 장벽이 있을 수 있다는 근거(Forbes–Shpilka–Volk 2017, Grochow–Kumar–Saks–Saraf 2017)도 있다.」

  고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.

  답 달기
• 보완#76원문 보완판 — 사실 검토 반영
  • 관리자
  • 2026-10-07 13:28
  • AI 도움
  • 빨간 표시 안보이게

  기하 복잡도 이론(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 의 초선형 하한조차 증명할 수 없음을 보였다.

  발생 장애물

  어떤 기약표현이 한쪽 좌표환에는 등장하고 다른 쪽에는 전혀 등장하지 않는 유형의 장애물. 가장 다루기 쉬운 유형이다.

  곱셈도 장애물

  특정 기약표현 λ 에 대해 「permanent 측 곱셈도가 모델 측 곱셈도보다 크다」는 부등식형 장애물(2단계).

  본 아이디어는 이 부정 결과의 원인을 (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. 같은 도구 상자가 인접 문제(행렬곱 텐서의 경계 랭크 하한)에서 실제 하한을 산출한 전력이 있어, 방법론의 현실성이 이미 부분적으로 입증되어 있다.

  이 글이 보는 세 장벽과의 관계 — 아이디어 쪽의 판단이며 검증된 결론이 아니다

  장벽	이 글의 판단
  상대화	대수기하·표현론 기반 하한 기법은 상대화 장벽의 적용 범위 밖이라고 본다. 다만 목표 사슬 끝의 P≠NP 단계에는 그대로 적용된다.
  자연 증명	GCT 장애물은 대칭성이라는 극히 특수한 성질을 이용하므로 natural proofs 의 대량성(largeness) 조건을 회피할 여지가 있다는 분석(Grochow 등)이 있다. 반대로 대수적 자연 증명 장벽이 있을 수 있다는 근거(Forbes–Shpilka–Volk 2017, Grochow–Kumar–Saks–Saraf 2017)도 있다.
  대수화	대수화 장벽의 적용 범위 밖이라고 본다. 다만 목표 사슬 끝의 P≠NP 단계에는 그대로 적용된다. 8단계에서 개발한 기법과 세 장벽의 관계를 문서화한다.

  참고 문헌

  • Mulmuley, Sohoni, Geometric Complexity Theory I, SIAM J. Comput. 2001 · GCT II, 2008
  • Bürgisser, Ikenmeyer, Panova, No occurrence obstructions in geometric complexity theory, FOCS 2016 / J. AMS 2019 — https://arxiv.org/abs/1604.06431
  • Ikenmeyer, Panova, FOCS 2016 (관련 부정 결과)
  • Gesmundo, Ikenmeyer, Panova, Geometric complexity theory and matrix powering, Differential Geom. Appl. 2017 — https://arxiv.org/abs/1611.00827
  • Nisan, 동차화(행렬 거듭제곱 정식화의 근거), 1991
  • Bürgisser, 2000 (GRH 하 VP = VNP ⇒ NP ⊆ P/poly) — Mahajan, Algebraic Complexity Classes 서베이에 인용 — https://arxiv.org/abs/1307.3863
  • Kadish, Landsberg, Padded polynomials, their cousins, and geometric complexity theory, Comm. Algebra 2014
  • Dörfler, Ikenmeyer, Panova, ICALP 2019 — https://arxiv.org/abs/1901.04576
  • Grenet, dc(perm_3) ≤ 7, 2011 · Alper, Bogart, Velasco, dc(perm_3) ≥ 7, 2017
  • Landsberg, Manivel, Ressayre, Hypersurfaces with degenerate duals, Comment. Math. Helv. 2013 — https://arxiv.org/abs/1004.4802
  • Hüttenhain, Lairez, 3×3 행렬식 궤도의 경계, 2016 — https://arxiv.org/abs/1512.02437
  • Bürgisser, Ikenmeyer, 행렬곱 텐서 경계 랭크 ≥ (3/2)n² − 2, STOC 2013 — https://arxiv.org/abs/1210.8368
  • Grochow, Unifying known lower bounds via geometric complexity theory, Comput. Complexity 2015 — https://arxiv.org/abs/1304.6333
  • Forbes, Shpilka, Volk, STOC 2017 · Grochow, Kumar, Saks, Saraf, 2017 (대수적 자연 증명 장벽의 근거)
  답 달기