Completeness Results for Counting Problems with Easy Decision
DOI10.1007/978-3-319-57586-5_6zbMath1486.68078OpenAlexW2606244929MaRDI QIDQ5283355
Petros Pantavos, Aggeliki Chalki, Eleni Bakali, Stathis Zachos, Aris Pagourtzis
Publication date: 21 July 2017
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-57586-5_6
Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational aspects of satisfiability (68R07)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- On counting and approximation
- Approximate counting, uniform generation and rapidly mixing Markov chains
- A very hard log-space counting class
- The relative complexity of approximate counting problems
- Descriptive complexity of \(\#\)P functions
- On the connection between interval size functions and path counting
- Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard
- The Complexity of Ferromagnetic Ising with Local Fields
- Approximate counting by dynamic programming
- Monte-Carlo approximation algorithms for enumeration problems
- The Complexity of Enumeration and Reliability Problems
- Estimating the Efficiency of Backtrack Programs
- Random Formulas Have Frozen Variables
- Computational Complexity
- The Complexity of Computing the Size of an Interval
- An FPTAS for #Knapsack and Related Counting Problems
- The Complexity of Counting Functions with Easy Decision Version
- On the solution‐space geometry of random constraint satisfaction problems
This page was built for publication: Completeness Results for Counting Problems with Easy Decision
