Polynomial-time solvable \#CSP problems via algebraic models and Pfaffian circuits

DOI10.1016/J.JSC.2015.06.008zbMATH Open1346.68295arXiv1311.4066OpenAlexW2171050449MaRDI QIDQ898252FDOQ898252

Authors: N. E. Zubov 

Publication date: 8 December 2015

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: A Pfaffian circuit is a tensor contraction network where the edges are labeled with changes of bases in such a way that a very specific set of combinatorial properties are satisfied. By modeling the permissible changes of bases as systems of polynomial equations, and then solving via computation, we are able to identify classes of 0/1 planar #CSP problems solvable in polynomial-time via the Pfaffian circuit evaluation theorem (a variant of L. Valiant's Holant Theorem). We present two different models of 0/1 variables, one that is possible under a homogeneous change of basis, and one that is possible under a heterogeneous change of basis only. We enumerate a series of 1,2,3, and 4-arity gates/cogates that represent constraints, and define a class of constraints that is possible under the assumption of a ``bridge" between two particular changes of bases. We discuss the issue of planarity of Pfaffian circuits, and demonstrate possible directions in algebraic computation for designing a Pfaffian tensor contraction network fragment that can simulate a swap gate/cogate. We conclude by developing the notion of a decomposable gate/cogate, and discuss the computational benefits of this definition.

Full work available at URL: https://arxiv.org/abs/1311.4066

Recommendations

• Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits
• Generalized counting constraint satisfaction problems with determinantal circuits
• Holographic algorithms without matchgates
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• Publication:4938661

zbMATH Keywords

computer algebradichotomy theorems\(\#\)CSPpolynomial idealsGröbner bases

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Cites Work

• Stable sets and polynomials
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• The complexity of partition functions
• On the complexity of \#CSP
• Holographic Algorithms
• The Complexity of Weighted Boolean #CSP
• Holant problems and counting CSP
• The complexity of the counting constraint satisfaction problem
• A complete dichotomy rises from the capture of vanishing signatures (extended abstract)
• The complexity of weighted Boolean \#CSP with mixed signs
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• An effective dichotomy for the counting constraint satisfaction problem
• Complexity of counting CSP with complex weights
• A Simple Algorithm for Mal'tsev Constraints
• Combinatorial Nullstellensatz
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Colorings and orientations of graphs
• The complexity of planar Boolean \(\#\)CSP with complex weights
• Valiant's holant theorem and matchgate tensors
• Gadgets and anti-gadgets leading to a complexity dichotomy
• Computational complexity of Holant problems
• The complexity of complex weighted Boolean \#CSP
• Dichotomy for Holant* problems with a function on domain size 3
• Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
• Holographic algorithms without matchgates
• Generalized counting constraint satisfaction problems with determinantal circuits
• Title not available (Why is that?)
• Nowhere-zero flow polynomials

Cited In (5)

• Generalized counting constraint satisfaction problems with determinantal circuits
• CSPs with global modular constraints: algorithms and hardness via polynomial representations
• FKT is not universal -- a planar holant dichotomy for symmetric constraints
• A finite-tame-wild trichotomy theorem for tensor diagrams
• Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits

Uses Software

• SINGULAR

This page was built for publication: Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898252)