A computational proof of complexity of some restricted counting problems
type: Item
instance of: scholarly article
title: A computational proof of complexity of some restricted counting problems
zbMATH Open document ID: 1216.68122
author: Jin-Yi Cai
author: Pinyan Lu
author: Mingji Xia
published in: Theoretical Computer Science
publication date: 2011-05-18T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 68-04
zbMATH DE Number: 5895903
zbMATH Keywords: Holant problem
zbMATH Keywords: holographic reduction
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.10.039
OpenAlex ID: W2099255094
cites work: Q4391229
cites work: Towards a dichotomy theorem for the counting constraint satisfaction problem
cites work: The complexity of partition functions
cites work: Graph Homomorphisms with Complex Values: A Dichotomy Theorem
cites work: Q3549638
cites work: A Computational Proof of Complexity of Some Restricted Counting Problems
cites work: Holant problems and counting CSP
cites work: Q4079605
cites work: Complexity of generalized satisfiability counting problems
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: On counting homomorphisms to directed acyclic graphs
cites work: Q4521549
cites work: Q5390002
cites work: On the complexity of H-coloring
cites work: Q5807665
cites work: Q4002474
cites work: The complexity of counting in sparse, regular, and planar graphs
cites work: Quantum Circuits That Can Be Simulated Classically in Polynomial Time
DOI: 10.1016/J.TCS.2010.10.039
description: scientific article; zbMATH DE number 5895903