Sparse Sets, Lowness and Highness

DOI10.1137/0215053zbMATH Open0621.68033OpenAlexW2033908054MaRDI QIDQ3758244FDOQ3758244

Ronald V. Book, José L. Balćzar, 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

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

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)

Cited In (28)

• Robust machines accept easy sets
• The structure of logarithmic advice complexity classes
• Lowness Properties of Sets in the Exponential-Time Hierarchy
• Hard promise problems and nonuniform complexity
• Fault-tolerance and complexity (Extended abstract)
• A note on sparse sets and the polynomial-time hierarchy
• Upper bounds for the complexity of sparse and tally descriptions
• Low sets without subsets of higher many-one degree
• Some connections between bounded query classes and non-uniform complexity.
• Sparse selfreducible sets and nonuniform lower bounds
• Structural properties of oracle classes
• Highly sparse sets as additive complements for a prescribed density
• Highly spare sets as additive complements for a prescribed density: an open problem
• Title not available (Why is that?)
• The extended low hierarchy is an infinite hierarchy
• The join can lower complexity
• Closure and nonclosure properties of the classes of compressible and rankable sets
• 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
• Nonuniform lowness and strong nonuniform lowness
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• A relationship between difference hierarchies and relativized polynomial hierarchies
• 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)