Holographic algorithms without matchgates
From MaRDI portal
Exact enumeration problems, generating functions (05A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Special matrices (15B99)
Abstract: The theory of holographic algorithms, which are polynomial time algorithms for certain combinatorial counting problems, yields insight into the hierarchy of complexity classes. In particular, the theory produces algebraic tests for a problem to be in the class P. In this article we streamline the implementation of holographic algorithms by eliminating one of the steps in the construction procedure, and generalize their applicability to new signatures. Instead of matchgates, which are weighted graph fragments that replace vertices of a natural bipartite graph G associated to a problem P, our approach uses only only a natural number-of-edges by number-of-edges matrix associated to G. An easy-to-compute multiple of its Pfaffian is the number of solutions to the counting problem. This simplification improves our understanding of the applicability of holographic algorithms, indicates a more geometric approach to complexity classes, and facilitates practical implementations. The generalized applicability arises because our approach allows for new algebraic tests that are different from the "Grassmann-Plucker identities" used up until now. Natural problems treatable by these new methods have been previously considered in a different context, and we present one such example.
Recommendations
Cites work
- scientific article; zbMATH DE number 973924 (Why is no real title available?)
- scientific article; zbMATH DE number 3326387 (Why is no real title available?)
- A combinatorial Laplacian with vertex weights
- Applications of minor-summation formula. II: Pfaffians and Schur polynomials
- Automata, Languages and Programming
- Basis collapse in holographic algorithms
- Dimer problem in statistical mechanics-an exact result
- Expressiveness of matchgates.
- Holographic Algorithms
- Holographic Algorithms: The Power of Dimensionality Resolved
- Holographic algorithms by Fibonacci gates
- Holographic algorithms: from art to science
- NP is as easy as detecting unique solutions
- Nonintersecting paths, pfaffians, and plane partitions
- On Symmetric Signatures in Holographic Algorithms
- On the computational complexity of the Jones and Tutte polynomials
- Pfaffian graphs, \(T\)-joins and crossing numbers
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Quantum computers that can be simulated classically in polynomial time
- Some Results on Matchgates and Holographic Algorithms
- Theory and Applications of Models of Computation
- Valiant's holant theorem and matchgate tensors
Cited in
(16)- On blockwise symmetric matchgate signatures and higher domain \#CSP
- Generalized counting constraint satisfaction problems with determinantal circuits
- Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
- Computing the Tutte polynomial of lattice path matroids using determinantal circuits
- Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits
- Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
- \(P\) versus \(NP\) and geometry
- A finite-tame-wild trichotomy theorem for tensor diagrams
- FKT is not universal -- a planar holant dichotomy for symmetric constraints
- Holographic Algorithms
- Counting degree-constrained subgraphs and orientations
- Holographic algorithms: from art to science
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- Holographic algorithms: from art to science
- Holographic algorithms by Fibonacci gates
- Some Results on Matchgates and Holographic Algorithms
This page was built for publication: Holographic algorithms without matchgates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1931767)
