$SO(3)$의 유한 부분군으로부터: $C_2$는 Holant 이분법으로 이어진다
From a finite subgroup of $SO(3)$:$C_2$ leads to a Holant dichotomy
한국어 초록
Holant 프레임워크 내의 계수 복잡도는 복잡도 이분법 정리를 통해 폭넓게 연구되어 왔다. 다양한 제한된 설정에서 상당한 진전이 이루어졌으나, 보조 단항 시그니처가 없는 일반적인 복소수 값 짝수 차수 경우는 대체로 미해결로 남아 있다. 본 논문은 이진 시그니처들이 \(M(B(\mathcal{F}))\cong C_2\)를 만족하는 군 구조를 유도하는 이 프로그램의 근본적인 경우를 연구한다. 이진 시그니처 행렬의 사영 동치류가 \(SO(3)\)의 유한 부분군에 자연스럽게 임베딩됨을 관찰하였으며, 이는 구조적 분류를 위한 대수적 관점을 제공한다. 본 논문은 더 나아가 \(C_2\) 경우에 대해 정규(normal) 경우와 등방(isotropic) 경우라는 근본적으로 다른 두 체제를 규명하고 각각의 복잡도 거동을 분석한다. 가젯 구성, 분해 기법, 보간 논증, 그리고 복소수 값 설정을 동등한 실수 구조 프레임워크로 변환하는 실수화(realnumberization) 접근법을 결합하여, 완전한 이분법 정리를 확립한다. 즉 \(M(\B(\mathcal{F}))\cong C_2\)를 만족하는 모든 짝수 차수 시그니처 집합 \(\mathcal{F}\)에 대해, 문제 \(\mathrm{Holant}(\mathcal{F})\)는 다항 시간에 계산 가능하거나 \#P-난해이다. 또한 실현 가능한 시그니처를 정리하고 표준 기저에서는 덜 분명한 구조적 관계를 드러내기 위한 대수적으로 자연스러운 언어로서 시그니처의 파울리 기저 표현을 추가로 도입한다.
원문 초록
Counting complexity within the Holant framework has been extensively studied through complexity dichotomy theorems. While substantial progress has been achieved for various restricted settings, the general complex-valued even-arity case without auxiliary unary signatures remains largely open. This paper studies a fundamental case in this program where the binary signatures induce a group structure satisfying \(M(B(\mathcal{F}))\cong C_2\). It is observed that projective equivalence classes of binary signature matrices naturally embed into finite subgroups of \(SO(3)\), providing an algebraic viewpoint for structural classification. This paper further identifies two fundamentally different regimes for the \(C_2\) case, namely the normal and isotropic cases, and analyzes their complexity behavior separately. Combining gadget constructions, decomposition techniques, interpolation arguments, and a realnumberization approach that transforms the complex-valued setting into an equivalent real-structured framework, this paper establishes a complete dichotomy theorem: for every even-arity signature set \(\mathcal{F}\) satisfying \(M(\B(\mathcal{F}))\cong C_2\), the problem \(\mathrm{Holant}(\mathcal{F})\) is either polynomial-time computable or \#P-hard. A Pauli-basis representation for signatures is further introduced as an algebraically natural language for organizing realizable signatures and revealing structural relations that are less transparent in the standard basis.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2611.24236v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.