Completeness Results for Counting Problems with Easy Decision
DOI10.1007/978-3-319-57586-5_6zbMATH Open1486.68078OpenAlexW2606244929MaRDI QIDQ5283355FDOQ5283355
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computational Complexity
- The complexity of computing the permanent
- The relative complexity of approximate counting problems
- The Complexity of Enumeration and Reliability Problems
- An FPTAS for #Knapsack and Related Counting Problems
- The Complexity of Ferromagnetic Ising with Local Fields
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Monte-Carlo approximation algorithms for enumeration problems
- Approximate counting by dynamic programming
- Estimating the Efficiency of Backtrack Programs
- On the solution‐space geometry of random constraint satisfaction problems
- On counting and approximation
- A very hard log-space counting class
- The Complexity of Computing the Size of an Interval
- Random Formulas Have Frozen Variables
- The Complexity of Counting Functions with Easy Decision Version
- Descriptive complexity of \(\#\)P functions
- On the connection between interval size functions and path counting
- Approximately counting \(H\)-colorings is \(\#\)BIS-hard
Cited In (3)
This page was built for publication: Completeness Results for Counting Problems with Easy Decision
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283355)
