A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
type: Item
instance of: scholarly article
title: A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
zbMATH Open document ID: 1253.68184
author: Tomoyuki Yamakami
published in: Theoretical Computer Science
publication date: 2012-08-13T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6065024
zbMATH Keywords: constraint satisfaction problem
zbMATH Keywords: \(\#\)CSP
zbMATH Keywords: bounded degree
zbMATH Keywords: approximate counting
zbMATH Keywords: dichotomy theorem
zbMATH Keywords: T-constructibility
zbMATH Keywords: signature
zbMATH Keywords: holant problem
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.03.036
OpenAlex ID: W1550829276
cites work: Signature Theory in Holographic Algorithms
cites work: Holographic algorithms: from art to science
cites work: Holant problems and counting CSP
cites work: Q5365150
cites work: Complexity of generalized satisfiability counting problems
cites work: Mathematical Foundations of Computer Science 2003
cites work: On Counting Independent Sets in Sparse Graphs
cites work: The Complexity of Approximating Bounded-Degree Boolean #CSP
cites work: The Complexity of Weighted Boolean #CSP
cites work: An approximation trichotomy for Boolean \#CSP
cites work: Fanout limitations on constraint systems
cites work: Q4002474
cites work: On the Structure of Polynomial Time Reducibility
cites work: The complexity of satisfiability problems
cites work: Holographic Algorithms
cites work: \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
DOI: 10.1016/J.TCS.2012.03.036
description: scientific article; zbMATH DE number 6065024