Sparse Sets, Lowness and Highness

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

zbMATH Keywords

polynomial-time hierarchysparse setextended highnessextended lownessgeneralized highnessgeneralized lowness

Mathematics Subject Classification ID

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