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

DOI10.1016/j.jsc.2015.06.008zbMath1346.68295arXiv1311.4066OpenAlexW2171050449MaRDI QIDQ898252

N. E. Zubov

Publication date: 8 December 2015

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

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

zbMATH Keywords

Gröbner basescomputer algebrapolynomial idealsdichotomy theorems\(\#\)CSP

Mathematics Subject Classification ID

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

Related Items (2)

A finite-tame-wild trichotomy theorem for tensor diagrams ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints

Uses Software

• SINGULAR

Cites Work

• Unnamed Item
• The complexity of complex weighted Boolean \#CSP
• Generalized counting constraint satisfaction problems with determinantal circuits
• Nowhere-zero flow polynomials
• The complexity of weighted Boolean \#CSP with mixed signs
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Colorings and orientations of graphs
• Stable sets and polynomials
• Holographic algorithms without matchgates
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• The complexity of planar Boolean \#CSP with complex weights
• Valiant's holant theorem and matchgate tensors
• The complexity of partition functions
• Gadgets and anti-gadgets leading to a complexity dichotomy
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• On the complexity of #CSP
• Computational Complexity of Holant Problems
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Holographic Algorithms
• Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
• The Complexity of Weighted Boolean #CSP
• Combinatorial Nullstellensatz
• Holant problems and counting CSP
• The complexity of the counting constraint satisfaction problem
• Complexity of counting CSP with complex weights
• A Simple Algorithm for Mal'tsev Constraints
• A complete dichotomy rises from the capture of vanishing signatures
• Dichotomy for Holant Problems with a Function on Domain Size 3

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