Approximable sets

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

zbMATH Keywords

NP-complete sets\(p\)-superterse

Mathematics Subject Classification ID

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