Sparse Sets, Lowness and Highness

DOI10.1137/0215053MaRDI QIDQ3758244zbMATH OpenOpenAlexFDO

Authors José L. Balćzar, Ronald V. Book, Uwe Schöning

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)

Recommendations

• scientific article; zbMATH DE number 3883613
• Lowness Properties of Sets in the Exponential-Time Hierarchy
• A note on sparse sets and the polynomial-time hierarchy
• A refinement of the low and high hierarchies
• Complexity and structure

Cited in

(28)

• A relationship between difference hierarchies and relativized polynomial hierarchies
• Robust machines accept easy sets
• The structure of logarithmic advice complexity classes
• Hard promise problems and nonuniform complexity
• Lowness Properties of Sets in the Exponential-Time Hierarchy
• A note on sparse sets and the polynomial-time hierarchy
• Upper bounds for the complexity of sparse and tally descriptions
• Some connections between bounded query classes and non-uniform complexity.
• Structural properties of oracle classes
• Low sets without subsets of higher many-one degree
• Sparse selfreducible sets and nonuniform lower bounds
• Highly sparse sets as additive complements for a prescribed density
• Highly spare sets as additive complements for a prescribed density: an open problem
• scientific article; zbMATH DE number 1555980 (Why is no real title available?)
• The extended low hierarchy is an infinite hierarchy
• Closure and nonclosure properties of the classes of compressible and rankable sets
• The join can lower complexity
• Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
• Locating P/poly optimally in the extended low hierarchy
• Boolean operations, joins, and the extended low hierarchy
• Fault-tolerance and complexity (extended abstract)
• Nonuniform lowness and strong nonuniform lowness
• scientific article; zbMATH DE number 3883613 (Why is no real title available?)
• A refinement of the low and high hierarchies
• Probabilistic complexity classes and lowness
• Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
• scientific article; zbMATH DE number 3984572 (Why is no real title available?)
• A note on P-selective sets and closeness

This page was built for publication: Sparse Sets, Lowness and Highness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3758244)