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

extended highnessextended lownessgeneralized highnessgeneralized lownesspolynomial-time hierarchysparse set

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

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

(29)

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

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)