On counting and approximation
From MaRDI portal
Publication:1114675
zbMath0663.03025MaRDI QIDQ1114675
Johannes Köbler, Jacobo Toran, Uwe Schoening
Publication date: 1989
Published in: Acta Informatica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
A note on SpanP functions, Completeness Results for Counting Problems with Easy Decision, Simple characterizations of \(P(\# P)\) and complete problems, A complexity theory for feasible closure properties, The operators min and max on the polynomial hierarchy, Complexity of counting the optimal solutions, Locating \(P\)/poly optimally in the extended low hierarchy, Tractable counting of the answers to conjunctive queries, Complexity of Counting the Optimal Solutions, The consequences of eliminating NP solutions, Computing functions with parallel queries to NP, Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P, A very hard log-space counting class, On the autoreducibility of functions, Descriptional and computational complexity of finite automata -- a survey, Dimension, entropy rates, and compression, Nondeterministic \(NC^1\) computation, Subtractive reductions and complete problems for counting complexity classes, Tally NP sets and easy census functions., Gap-definable counting classes, A note on unambiguous function classes
