A Computational Proof of Complexity of Some Restricted Counting Problems

DOI10.1007/978-3-642-02017-9_17zbMath1241.68068OpenAlexW2174085268MaRDI QIDQ3630198

Pinyan Lu, Jin-Yi Cai, Mingji Xia

Publication date: 3 June 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02017-9_17

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Block interpolation: a framework for tight exponential-time counting complexity ⋮ A computational proof of complexity of some restricted counting problems ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ The Complexity of Symmetric Boolean Parity Holant Problems

This page was built for publication: A Computational Proof of Complexity of Some Restricted Counting Problems