Self-reducible sets of small density

DOI10.1007/BF02090392zbMath0722.68058OpenAlexW2039379116MaRDI QIDQ3210176

Antoni Lozano, Jacobo Toran

Publication date: 1991

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02090392

zbMATH Keywords

sparse setslength decreasing self-reducibilityword decreasing self-reducibility

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

Space-efficient recognition of sparse self-reducible languages ⋮ Geometric sets of low information content ⋮ A refinement of the low and high hierarchies ⋮ Characterizations of some complexity classes between Θ2p and Δ2p ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ New collapse consequences of NP having small circuits ⋮ Sparse selfreducible sets and nonuniform lower bounds ⋮ On sparse hard sets for counting classes ⋮ Complexity classes between $\Theta _k^P$ and $\Delta _k^P$

Cites Work

• Unnamed Item
• Unnamed Item
• A low and a high hierarchy within NP
• On self-reducibility and weak P-selectivity
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The polynomial-time hierarchy and sparse oracles
• A Note on Sparse Complete Sets
• On Circuit-Size Complexity and the Low Hierarchy in NP
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Lower bounds for the low hierarchy

This page was built for publication: Self-reducible sets of small density