기하적 복잡도 이론 — 퍼머넌트 대 행렬식을 표현론으로

Mulmuley 와 Sohoni 의 기하적 복잡도 이론(GCT)은 퍼머넌트가 행렬식보다 본질적으로 어렵다는 추측을 궤도 폐포와 표현론의 문제로 옮긴다. 대칭성을 써서 알려진 장벽을 피하려는 계획이지만, 가장 단순한 형태는 불가능함이 증명되었고 매우 긴 호흡의 계획으로 평가된다.

전문
관리자
2026-10-05 23:05
조회 0
AI 도움

검토 완료 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.

화면·그림·수식 전수 점검(2026-10-07)으로 내용을 확인했습니다. 증명이 옳다는 뜻은 아닙니다.

Mulmuley 와 Sohoni 의 기하적 복잡도 이론(GCT)은 퍼머넌트가 행렬식보다 본질적으로 어렵다는 추측을 궤도 폐포와 표현론의 문제로 옮긴다. 이 글은 그 계획의 세 걸음, 장벽을 피한다고 보는 이유, 그리고 지금 상태를 정리한다.

핵심 정리

행렬식과 퍼머넌트는 순열의 부호를 곱하느냐만 다르지만, 행렬식은 다항 시간에 계산되고 퍼머넌트 계산은 #P-완전이다(Valiant, 1979).
Valiant 의 추측(표수가 2 가 아닌 체 위에서 퍼머넌트에는 다항 크기의 산술 회로가 없다)은 P vs NP 의 「산술판 예행연습」으로 여겨진다. 아직 추측이다.
GCT 는 이를 「덧댄 퍼머넌트가 행렬식의 궤도 폐포에 들지 않는다」로 옮기고, 표현론의 장애물로 증명하려 한다.
퍼머넌트와 행렬식이 대칭성으로 특징지어진다는 사실 때문에 알려진 장벽을 피할 것으로 기대된다. 다만 장벽이 없다는 것이 성공을 보장하지는 않는다.
가장 단순한 길(출현 장애물)은 막혔고, 매우 긴 호흡의 계획으로 평가된다.

퍼머넌트 대 행렬식

n×n 행렬의 행렬식(determinant)과 퍼머넌트(permanent)는 정의가 거의 같다. 둘 다 각 행에서 서로 다른 열의 성분을 하나씩 골라 곱한 값을, 고르는 방법(순열) 전부에 대해 더한 것이다. 다만 행렬식은 순열의 부호를 곱하고 퍼머넌트는 곱하지 않는다.

2×2 행렬 a b / c d 에서 순열은 두 가지다. 그대로 고르면 a·d, 두 열을 바꿔 고르면 b·c 다. 행렬식은 바꾼 순열에 부호 마이너스를 곱해 a·d − b·c, 퍼머넌트는 부호 없이 a·d + b·c 다. 아래에는 행렬식은 다항 시간에 계산되고, 퍼머넌트 계산은 #P-완전이라고 적혀 있다. — 2×2 행렬로 본 두 정의 — 차이는 부호 하나지만, 계산의 어려움은 전혀 다르다.

그런데 계산의 어려움은 전혀 다르다. 행렬식은 다항 시간에 계산되지만, 퍼머넌트 계산은 #P-완전이다(Valiant, 1979). 퍼머넌트를 빨리 계산할 수 있다면 NP 문제의 해의 개수까지 셀 수 있다.

추측 — 증명되지 않음 Valiant 의 추측은, 표수가 2 가 아닌 체 위에서는 퍼머넌트에 다항 크기의 산술 회로(덧셈과 곱셈 게이트로 다항식을 계산하는 회로)가 없다는 것이다.

회로가 나오지 않는 꼴로도 말할 수 있다. n×n 퍼머넌트를, 각 성분이 변수들의 일차식인 m×m 행렬의 행렬식으로 쓸 수 있는 가장 작은 m 을 D(n) 이라 하자. D(n) 이 n^{O(log n)} 보다 빠르게 자라면 Valiant 의 추측이 따라 나온다. 지금 알려진 것은 n²/2 ≤ D(n) ≤ 2ⁿ − 1 뿐이다(하한은 Mignon·Ressayre, 상한은 Grenet).

이 추측은 P vs NP 의 「산술판 예행연습」으로 여겨진다. Bürgisser 는 Valiant 의 추측이 틀리면, 표수 0 에서는 일반화 리만 가설 아래, NP ⊆ P/poly 가 따라 나옴을 보였다.

기하와 표현론으로 옮기기

Mulmuley 와 Sohoni 의 기하적 복잡도 이론(geometric complexity theory, GCT)은 이 문제를 세 걸음으로 옮긴다.

궤도 폐포. m² 개 변수의 m 차 동차 다항식들의 공간에 일반선형군이 변수의 일차 치환으로 작용한다. 행렬식 detₘ 의 궤도 폐포(orbit closure)는 detₘ 에 일차 치환을 하고 극한을 취해 얻는 다항식 전체다. 퍼머넌트는 차수를 맞추려고 변수 하나의 거듭제곱을 곱한 「덧댄 퍼머넌트」로 바꾼다.
추측. m 이 2^{n^o(1)} 이하이면, 충분히 큰 n 에서 덧댄 퍼머넌트는 detₘ 의 궤도 폐포에 들지 않는다. 이것이 증명되면 Valiant 의 추측이 나온다.
장애물. 두 궤도 폐포의 좌표환은 일반선형군의 표현이어서 기약 표현들로 분해된다. 어떤 기약 표현이 퍼머넌트 쪽에 행렬식 쪽보다 더 많이 나타나면, 곧 중복도(multiplicity)가 더 크면, 그 표현은 포함 관계가 불가능하다는 증거인 장애물(obstruction)이 된다. 행렬식 쪽 중복도가 0 인 경우를 출현 장애물(occurrence obstruction)이라 한다.

큰 영역이 행렬식 det m 의 궤도 폐포이고, 그 안에 det m 과 일차 치환으로 얻은 다항식들이 있다. 영역 밖에 덧댄 퍼머넌트가 있고, 추측은 m 이 충분히 작으면 덧댄 퍼머넌트가 이 영역에 들지 않는다는 것이다. 아래에는 장애물, 곧 퍼머넌트 쪽에 더 많이 나타나는 기약 표현이 포함이 불가능하다는 증거가 된다고 적혀 있다. — GCT 의 그림 — 덧댄 퍼머넌트가 행렬식의 궤도 폐포 밖에 있음을 표현론의 장애물로 보이려 한다. 그림은 추측이 옳다고 할 때의 모습이다.

이 틀에서 변수의 일차 치환은 「환원」의 구실을 하고, 한 다항식의 궤도 폐포는 그 다항식으로 환원되는 문제들의 클래스에 해당한다. 「덧댄 퍼머넌트가 행렬식의 궤도 폐포에 없다」는 말은 「퍼머넌트는 작은 행렬식으로 환원되지 않는다」를 기하의 말로 옮긴 것이다. 극한까지 허용하므로 원래 추측보다 조금 강한 명제가 된다.

P vs NP 자체를 다루려면 유한체 위에서 같은 틀을 세워야 하는데, Aaronson 은 거기에 필요한 수학이 더욱 덜 알려져 있다고 전한다.

장벽을 피한다고 보는 이유

핵심은 퍼머넌트와 행렬식이 대칭성으로 특징지어진다는 사실이다. 같은 차수의 동차 다항식 가운데 퍼머넌트의 대칭을 모두 가진 것은 퍼머넌트의 상수배뿐이고, 행렬식도 그렇다. 무작위로 고른 다항식에는 이런 성질이 없다. 그래서 이 성질에 기대는 증명은 무작위 함수에는 통하지 않고, 자연 증명의 「큼」 조건에서 벗어난다. 오라클을 붙인 문제는 같은 대칭을 갖지 않으므로 상대화와 대수화도 피할 것으로 기대된다.

GCT 는 하한 문제를 알고리즘 문제로 뒤집기도 한다. 장애물을 찾으려면 표현의 중복도를 계산하거나 0 인지 판정하는 효율적인 알고리즘이 필요하다. Mulmuley 는 이것을 「뒤집기(the flip)」라 부른다.

지금 상태

가장 단순한 길은 막혔다. Bürgisser·Ikenmeyer·Panova 는 출현 장애물로는 퍼머넌트와 행렬식의 궤도 폐포를 분리할 수 없음을 증명했다(2016년 발표, 2019년 게재). 초록은 이 접근이 「불가능하다」고 쓰면서도, 일반적인 중복도 장애물까지 배제한 것은 아니라고 덧붙인다.
중복도 장애물은 남아 있다. Dörfler·Ikenmeyer·Panova(2020)는 출현으로는 분리할 수 없지만 중복도로는 분리되는 설정을 처음 제시했다. Ikenmeyer·Kandasamy(2020)는 두 다항식의 대칭군을 모두 써서 중복도 장애물을 얻는, 원래 계획의 첫 「구현」을 작은 모형 문제에서 보였다.
얻은 하한은 아직 작다. GCT 식 장애물로 얻은 결과로는 n×n 행렬 곱 텐서의 경계 계수(border rank)가 (3/2)n² − 2 이상이라는 것이 있다(Bürgisser·Ikenmeyer, 2013). 다른 방법으로 얻은 2n² − n 보다 약하다.
평가. Fortnow 는 2009년에, Mulmuley 자신도 이 계획이 성공한다 해도 「약 100년」은 걸릴 것으로 본다고 전했다. Aaronson 은 2017년에 전문가들의 전망이 갈린다고 적고 GCT 를 「전산학의 끈 이론」에 비유했다. 대각선 논법과 균일성을 활용하지 못한다는 점도 한계로 꼽았다.

출처

K. D. Mulmuley, M. Sohoni, "Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems", SIAM J. Comput. 31(2), 496–526 (2001). 서지는 DOI 등록 정보로, 내용은 Aaronson 2017 §6.6.1–6.6.4 로 확인.
L. G. Valiant, "The Complexity of Computing the Permanent", Theoret. Comput. Sci. 8(2), 189–201 (1979). 서지는 DOI 등록 정보로, 내용은 Aaronson 2017 §6.5.1 로 확인.
P. Bürgisser, "Cook's versus Valiant's Hypothesis", Theoret. Comput. Sci. 235(1), 71–88 (2000). 서지는 DOI 등록 정보로, 내용은 Aaronson 2017 §6.5.1 로 확인.
T. Mignon, N. Ressayre, "A Quadratic Bound for the Determinant and Permanent Problem", Int. Math. Res. Not. 2004(79), 4241–4253. 서지는 DOI 등록 정보로, 내용은 Aaronson 2017 정리 74 로 확인.
B. Grenet, "An Upper Bound for the Permanent versus Determinant Problem", 원고(2011). 원고는 열지 못했고 Aaronson 2017 정리 73 으로만 확인했다.
P. Bürgisser, C. Ikenmeyer, G. Panova, "No Occurrence Obstructions in Geometric Complexity Theory", J. Amer. Math. Soc. 32(1), 163–193 (2019); FOCS 2016. 공개본(arXiv:1604.06431)의 초록과 서론을 확인.
J. Dörfler, C. Ikenmeyer, G. Panova, "On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions", SIAM J. Appl. Algebra Geom. 4(2), 354–376 (2020). arXiv:1901.04576 의 초록을 확인.
C. Ikenmeyer, U. Kandasamy, "Implementing Geometric Complexity Theory: On the Separation of Orbit Closures via Symmetries", STOC 2020, 713–726. arXiv:1911.03990 의 초록을 확인.
P. Bürgisser, C. Ikenmeyer, "Explicit Lower Bounds via Geometric Complexity Theory", STOC 2013, 141–150. 서지는 DOI 등록 정보로, 내용은 Aaronson 2017 정리 96–97 로 확인.
S. Aaronson, "P =? NP", 저자 공개본(2017). §6.5.1, §6.6 전체를 확인.
L. Fortnow, "The Status of the P versus NP Problem", Commun. ACM 52(9), 78–86 (2009). §9 를 확인.

출처·이용 조건: 직접 작성

참고문헌 11

접근서지만 확인
Geometric Complexity Theory I: An Approach to the P vs. NP and Related ProblemsKetan D. Mulmuley, Milind Sohoni · 2001SIAM Journal on Computing 31(2), 496–526쪽 (2001)
기하적 복잡도 이론(GCT)을 시작한 논문이다. 대수기하와 표현론의 배경이 필요한 전문 연구자용 논문이다. 접근의 얼개만 알고 싶다면 aaronson-2017 의 6.6절을 먼저 읽는 편이 좋다. SIAM 페이지로 연결되며 본문 열람에는 구독이 필요할 수 있다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.6.1–6.6.4 로 확인.
원문 주소 (doi.org)DOI 10.1137/s009753970038715x
부분 결과서지만 확인
The Complexity of Computing the PermanentL. G. Valiant · 1979Theoretical Computer Science 8(2), 189–201쪽 (1979)
퍼머넌트 계산이 #P-완전임을 보인 논문이다. 행렬식은 다항 시간에 계산되지만 퍼머넌트는 그렇지 않으리라는 대비의 출발점으로, 2-3 의 GCT 글이 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.5.1 로 확인.
원문 주소 (doi.org)DOI 10.1016/0304-3975(79)90044-6
부분 결과서지만 확인
Cook's versus Valiant's HypothesisPeter Bürgisser · 2000Theoretical Computer Science 235(1), 71–88쪽 (2000)
Valiant 의 추측이 틀리면 NP ⊆ P/poly 가 따라 나옴을 보인 논문이다(표수 0 인 체에서는 일반화 리만 가설을 가정한다). 퍼머넌트 대 행렬식 문제가 P 대 NP 의 「산술판 예행연습」으로 여겨지는 근거다. 1-1 의 「여러 얼굴」 글과 2-3 의 GCT 글이 인용한다.
확인:논문 본문은 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.5.1 로 확인.
원문 주소 (doi.org)DOI 10.1016/s0304-3975(99)00183-8
부분 결과서지만 확인
A Quadratic Bound for the Determinant and Permanent ProblemT. Mignon, N. Ressayre · 2004International Mathematics Research Notices 2004(79), 4241–4253쪽
n×n 퍼머넌트를 행렬식으로 쓰려면 크기가 n²/2 이상인 행렬이 필요함을 보인 논문이다. 퍼머넌트 대 행렬식 문제에서 알려진 하한의 출처로, 2-3 의 GCT 글이 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Aaronson 2017 정리 74 로 확인.
원문 주소 (doi.org)DOI 10.1155/s1073792804142566
부분 결과미확인
An Upper Bound for the Permanent versus Determinant ProblemB. Grenet · 2011원고 (2011)
n×n 퍼머넌트를 크기 2ⁿ − 1 인 행렬의 행렬식으로 쓸 수 있음을 보인 원고다. 퍼머넌트 대 행렬식 문제에서 알려진 상한의 출처로, 2-3 의 GCT 글이 Aaronson 의 2017년 개관(정리 73)을 따라 인용한다. 원고의 주소를 확인하지 못해 링크가 없다.
확인:원고를 열지 못했고 주소도 확인하지 못함. 서지와 내용은 Aaronson 2017 의 참고문헌 목록과 정리 73 으로만 적음.
접근원문 확인
No Occurrence Obstructions in Geometric Complexity TheoryP. Bürgisser, C. Ikenmeyer, G. Panova · 2019Journal of the American Mathematical Society 32(1), 163–193쪽 (2019) · 학회 발표 FOCS 2016, 386–395쪽
기하적 복잡도 이론에서 출현 장애물만으로는 퍼머넌트와 행렬식을 분리할 수 없음을 증명한 논문이다. GCT 계획의 가장 단순한 형태가 불가능함을 보였지만, 일반적인 중복도 장애물까지 배제한 것은 아니라고 초록이 밝힌다. 2-3 의 접근 지도와 GCT 글이 인용한다. arXiv 공개본으로 연결한다.
확인:arXiv 공개본(1604.06431)의 초록과 서론을 읽음.
원문 주소 (arxiv.org)arXiv 1604.06431
접근서지만 확인
On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence ObstructionsJ. Dörfler, C. Ikenmeyer, G. Panova · 2020SIAM Journal on Applied Algebra and Geometry 4(2), 354–376쪽 (2020)
출현 장애물로는 분리할 수 없지만 중복도 장애물로는 분리되는 설정을 처음 제시한 논문이다. 기하적 복잡도 이론에서 중복도 장애물의 길이 남아 있음을 보여 주는 결과로, 2-3 의 GCT 글이 인용한다. arXiv 공개본으로 연결한다.
확인:arXiv 공개본(1901.04576)의 초록까지 확인. 본문을 읽었다는 기록은 없음.
원문 주소 (arxiv.org)arXiv 1901.04576
접근서지만 확인
Implementing Geometric Complexity Theory: On the Separation of Orbit Closures via SymmetriesC. Ikenmeyer, U. Kandasamy · 2020STOC 2020 (Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing), 713–726쪽
두 다항식의 대칭군을 모두 써서 중복도 장애물을 얻는, 기하적 복잡도 이론 계획의 첫 「구현」을 작은 모형 문제에서 보인 논문이다. 2-3 의 GCT 글이 계획의 현황으로 인용한다. arXiv 공개본으로 연결한다.
확인:arXiv 공개본(1911.03990)의 초록까지 확인. 본문을 읽었다는 기록은 없음.
원문 주소 (arxiv.org)arXiv 1911.03990
접근서지만 확인
Explicit Lower Bounds via Geometric Complexity TheoryP. Bürgisser, C. Ikenmeyer · 2013STOC 2013 (Proceedings of the 45th Annual ACM Symposium on Theory of Computing), 141–150쪽
기하적 복잡도 이론의 장애물로 행렬 곱 텐서의 경계 계수에 대한 구체적인 하한을 얻은 논문이다. n×n 행렬 곱 텐서의 경계 계수가 (3/2)n² − 2 이상임을 보인다. 2-3 의 GCT 글이 「얻은 하한은 아직 작다」의 예로 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Aaronson 2017 정리 96–97 로 확인.
원문 주소 (doi.org)DOI 10.1145/2488608.2488627
개관원문 확인
P =? NPScott Aaronson · 2017ECCC TR17-004 (2017년 1월 8일 공개) · 책 Open Problems in Mathematics (John Forbes Nash Jr., Michael Th. Rassias 엮음, Springer, 2016), 1–122쪽에 실린 글
P 대 NP 문제의 의미와 알려진 결과, 장벽, 접근 전반을 120여 쪽에 정리한 개관이다. 수학·과학·공학 배경의 넓은 독자를 겨냥해, 왜 P ≠ NP 라고 믿는지, 왜 증명이 어려운지, 지난 반세기에 무엇이 진전되었는지를 저자의 관점과 함께 설명한다. 상대화·자연 증명·대수화 장벽과 GCT 까지 다루므로, 이 서비스의 2부를 한 편으로 깊이 읽고 싶은 독자에게 가장 먼저 권한다.
확인:저자 공개본(2017년 판)을 열어 인용한 절들을 읽음.
원문 주소 (www.scottaaronson.com)
개관원문 확인
The status of the P versus NP problemLance Fortnow · 2009Communications of the ACM 52(9), 78–86쪽 (2009)
P 대 NP 문제의 의미와 2009년 시점의 연구 상황을 전산학 일반 독자에게 풀어 쓴 개관이다. 문제를 풀려던 시도들과 그 한계, NP-완전 문제를 현실에서 다루는 법, 양자 컴퓨터의 가능성까지 짧게 훑는다. 수식이 거의 없어 입문 독자가 처음 읽을 영어 글로 알맞다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본을 열어 인용한 절들을 읽음.
원문 주소 (lance.fortnow.com)

하위 정보 0

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

아직 없습니다.