From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
type: Item
instance of: scholarly article
title: From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
zbMATH Open document ID: 1255.68079
author: Jin-Yi Cai
author: Sangxia Huang
author: Pinyan Lu
published in: Algorithmica
publication date: 2013-01-28T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6131860
zbMATH Keywords: Holant problem
zbMATH Keywords: \#CSP
zbMATH Keywords: holographic reduction
zbMATH Keywords: dichotomy
MaRDI profile type: Publication
full work available at URL: s00453-012-9626-6
OpenAlex ID: W1660495057
cites work: A dichotomy theorem for constraint satisfaction problems on a 3-element set
cites work: Towards a dichotomy theorem for the counting constraint satisfaction problem
cites work: Automata, Languages and Programming
cites work: The complexity of partition functions
cites work: Holographic algorithms: from art to science
cites work: Holant problems and counting CSP
cites work: A computational proof of complexity of some restricted counting problems
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Tensor Geometry
cites work: The Complexity of Weighted Boolean #CSP
cites work: On Counting Homomorphisms to Directed Acyclic Graphs
cites work: On counting homomorphisms to directed acyclic graphs
cites work: Q4952624
cites work: Corrigendum: The complexity of counting graph homomorphisms
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Reflection positivity, rank connectivity, and homomorphism of graphs
cites work: A Complexity Dichotomy for Partition Functions with Mixed Signs
cites work: On the complexity of H-coloring
cites work: Classification of a Class of Counting Problems Using Holographic Reductions
cites work: Holant Problems for Regular Graphs with Complex Edge Functions
cites work: Holographic Algorithms
cites work: Computational complexity of counting problems on 3-regular planar graphs
DOI: 10.1007/S00453-012-9626-6
Recommended article: From Holant to #CSP and Back: Dichotomy for Holant c Problems
Recommended article: On the CSP Dichotomy Conjecture
Recommended article: Holant problems and counting CSP
Recommended article: On the complexity of \#CSP
Recommended article: On the Complexity of Holant Problems
Recommended article: A Proof of the CSP Dichotomy Conjecture
Recommended article: Dichotomy for Holant\(^\ast\) problems on the Boolean domain
Recommended article: Some New Tractable Classes of CSPs and Their Relations with Backtracking Algorithms
Recommended article: Q3696516
Recommended article: The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
description: scientific article; zbMATH DE number 6131860