Completeness, approximability and exponential time results for counting problems with easy decision version
From MaRDI portal
Publication:2143122
DOI10.1016/j.tcs.2022.02.030OpenAlexW4214573398WikidataQ115566723 ScholiaQ115566723MaRDI QIDQ2143122
Stathis Zachos, Eleni Bakali, Aris Pagourtzis, Aggeliki Chalki, Antonis Antonopoulos, Petros Pantavos
Publication date: 31 May 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2022.02.030
computational complexitycounting complexity\#P\textsf{TotP}backtracking-tree estimationtree-monotonicity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Stochastic enumeration method for counting trees
- The complexity of computing the permanent
- NP is as easy as detecting unique solutions
- Approximate counting, uniform generation and rapidly mixing Markov chains
- A very hard log-space counting class
- The relative complexity of approximate counting problems
- Characterizations and approximability of hard counting classes below \#\textsf{P}
- A structured view on weighted counting with relations to counting, quantum computation and applications
- On the connection between interval size functions and path counting
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
- PP is as Hard as the Polynomial-Time Hierarchy
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- On Approximation Algorithms for # P
- The Complexity of Enumeration and Reliability Problems
- Heuristic Sampling: A Method for Predicting the Performance of Tree Searching Programs
- Estimating the Efficiency of Backtrack Programs
- Tree Size by Partial Backtracking
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
- Completeness Results for Counting Problems with Easy Decision
- Computational Complexity
- FPTAS for Counting Monotone CNF
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
- The Complexity of Computing the Size of an Interval
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- The Complexity of Counting Functions with Easy Decision Version
- On the solution‐space geometry of random constraint satisfaction problems
- Computational Complexity
- On the complexity of \(k\)-SAT
This page was built for publication: Completeness, approximability and exponential time results for counting problems with easy decision version
