Sparse Sets, Lowness and Highness
From MaRDI portal
Publication:3758244
DOI10.1137/0215053zbMath0621.68033OpenAlexW2033908054MaRDI QIDQ3758244
Ronald V. Book, José L. Balćzar, Uwe Schoening
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2117/103245
polynomial-time hierarchysparse setextended highnessextended lownessgeneralized highnessgeneralized lowness
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (20)
A relationship between difference hierarchies and relativized polynomial hierarchies ⋮ Locating \(P\)/poly optimally in the extended low hierarchy ⋮ Nonuniform lowness and strong nonuniform lowness ⋮ A refinement of the low and high hierarchies ⋮ The extended low hierarchy is an infinite hierarchy ⋮ The join can lower complexity ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ Robust machines accept easy sets ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ A note on P-selective sets and closeness ⋮ Structural properties of oracle classes ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ Hard promise problems and nonuniform complexity ⋮ A note on sparse sets and the polynomial-time hierarchy ⋮ Probabilistic complexity classes and lowness ⋮ Hybrid Elections Broaden Complexity-Theoretic Resistance to Control ⋮ The structure of logarithmic advice complexity classes ⋮ Boolean operations, joins, and the extended low hierarchy ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
This page was built for publication: Sparse Sets, Lowness and Highness
