Approximable sets
From MaRDI portal
Publication:1898468
DOI10.1006/inco.1995.1115zbMath0835.68043OpenAlexW2913624541MaRDI QIDQ1898468
Frank Stephan, Richard Beigel, Martin Kummer
Publication date: 16 April 1996
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/6b1da0f8ffc9ca40b2b3f09eae00dd15e56d2a97
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (18)
Sparse sets, approximable sets, and parallel queries to NP ⋮ Geometric sets of low information content ⋮ Learning recursive functions from approximations ⋮ Time bounded frequency computations ⋮ Query complexity of membership comparable sets. ⋮ On membership comparable sets ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ Sparse selfreducible sets and nonuniform lower bounds ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ The value of help bits in randomized and average-case complexity ⋮ The communication complexity of enumeration, elimination, and selection ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ One query reducibilities between partial information classes ⋮ The enumerability of P collapses P to NC ⋮ Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete ⋮ Commutative queries ⋮ Optimal series-parallel trade-offs for reducing a function to its own graph ⋮ On the complexity of nonuniform wavelength-based machine
This page was built for publication: Approximable sets
