Self-reducible sets of small density
From MaRDI portal
Publication:3210176
DOI10.1007/BF02090392zbMATH Open0722.68058OpenAlexW2039379116MaRDI QIDQ3210176FDOQ3210176
Publication date: 1991
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02090392
Cites Work
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Title not available (Why is that?)
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- On self-reducibility and weak P-selectivity
- A low and a high hierarchy within NP
- The polynomial-time hierarchy and sparse oracles
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- A Note on Sparse Complete Sets
- On Circuit-Size Complexity and the Low Hierarchy in NP
- Lower bounds for the low hierarchy
- Title not available (Why is that?)
Cited In (14)
- \(p\)-selective self-reducible sets: a new characterization of P
- Upper bounds for the complexity of sparse and tally descriptions
- Small sets in dense pairs
- Sparse selfreducible sets and nonuniform lower bounds
- On sparse hard sets for counting classes
- New collapse consequences of NP having small circuits
- Title not available (Why is that?)
- Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
- Easily Checked Generalized Self-Reducibility
- A refinement of the low and high hierarchies
- Space-efficient recognition of sparse self-reducible languages
- Characterizations of some complexity classes between Θ2p and Δ2p
- Geometric sets of low information content
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
Recommendations
This page was built for publication: Self-reducible sets of small density
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3210176)
