Self-reducible sets of small density
From MaRDI portal
Recommendations
Cites work
- A low and a high hierarchy within NP
- A Note on Sparse Complete Sets
- scientific article; zbMATH DE number 18529 (Why is no real title available?)
- scientific article; zbMATH DE number 192916 (Why is no real title available?)
- Lower bounds for the low hierarchy
- On Circuit-Size Complexity and the Low Hierarchy in NP
- On self-reducibility and weak P-selectivity
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The polynomial-time hierarchy and sparse oracles
Cited in
(21)- On sparse hard sets for counting classes
- Space-efficient recognition of sparse self-reducible languages
- Geometric sets of low information content
- Sparse selfreducible sets and nonuniform lower bounds
- p-selective self-reducible sets: a new characterization of P
- Small sets in dense pairs
- Self-reducibility
- scientific article; zbMATH DE number 4179363 (Why is no real title available?)
- scientific article; zbMATH DE number 4022646 (Why is no real title available?)
- Natural Self-Reducible Sets
- scientific article; zbMATH DE number 4092778 (Why is no real title available?)
- scientific article; zbMATH DE number 1333601 (Why is no real title available?)
- scientific article; zbMATH DE number 522855 (Why is no real title available?)
- New collapse consequences of NP having small circuits
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
- A refinement of the low and high hierarchies
- Easily Checked Generalized Self-Reducibility
- Upper bounds for the complexity of sparse and tally descriptions
- Characterizations of some complexity classes between \(\Theta_2^{\mathrm{P}}\) and \(\Delta_2^{\mathrm{P}}\)
- Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds
- Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
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)
