On Approximation Algorithms for # P
From MaRDI portal
Publication:3718150
DOI10.1137/0214060zbMath0589.68031OpenAlexW2014603110WikidataQ56061359 ScholiaQ56061359MaRDI QIDQ3718150
Publication date: 1985
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0214060
Related Items
Amplification with one \textsf{NP} oracle query ⋮ One-Way Functions and (Im)perfect Obfuscation ⋮ On triangle estimation using tripartite independent set queries ⋮ On randomized versus deterministic computation ⋮ Locating \(P\)/poly optimally in the extended low hierarchy ⋮ The relative exponential time complexity of approximate counting satisfying assignments ⋮ Completeness, approximability and exponential time results for counting problems with easy decision version ⋮ \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) ⋮ On randomized versus deterministic computation ⋮ Relativized alternation and space-bounded computation ⋮ On the complexity of finding shortest variable disjunction branch-and-bound proofs ⋮ Graph isomorphism is in the low hierarchy ⋮ A \(q\)-analog of approximation inclusion-exclusion ⋮ The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments ⋮ On the hardness of approximate reasoning ⋮ Approximate counting in SMT and value estimation for probabilistic programs ⋮ Counting vertices of integral polytopes defined by facets ⋮ Unnamed Item ⋮ Optimal proof systems imply complete sets for promise classes ⋮ Almost optimal query algorithm for hitting set using a subset query ⋮ Semantics and complexity of abduction from default theories ⋮ Approximating the chromatic polynomial of a graph ⋮ Parameterized random complexity ⋮ On the complexity of ranking ⋮ ANALYSIS OF QUANTUM FUNCTIONS ⋮ Randomness buys depth for approximate counting ⋮ On Pseudodeterministic Approximation Algorithms. ⋮ Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P ⋮ Model counting with error-correcting codes ⋮ Lower bounds for non-black-box zero knowledge ⋮ The parameterized complexity of probability amplification ⋮ Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy ⋮ Dimension, entropy rates, and compression ⋮ Unnamed Item ⋮ On the parameterized complexity of approximate counting ⋮ On the computational power of DNA ⋮ Probabilistic complexity classes and lowness ⋮ Unnamed Item ⋮ Enumerative counting is hard ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the de-randomization of space-bounded approximate counting problems ⋮ On the complexity of counting in the polynomial hierarchy ⋮ A note on enumerative counting ⋮ Relativized separation of EQP from \(\text{P}^{\text{NP}}\) ⋮ The complexity of estimating min-entropy
