HYPSVC.com
서비스 커뮤니티
  1. P vs NP 문제 풀기
  2. 3. P vs NP 증명하기
  3. 3-1 도전 아이디어
  4. 무패딩 곱셈도 GCT
보완

사실 검토 — 보완 필요

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)도 있다.」

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

이 글에 단 답 0

아직 없습니다.