Sparse sets and collapse of complexity classes
From MaRDI portal
Recommendations
Cites work
- Computation times of NP sets of different densities
- Downward translations of equality
- scientific article; zbMATH DE number 46423 (Why is no real title available?)
- scientific article; zbMATH DE number 719756 (Why is no real title available?)
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Limitations of the upward separation technique
- On random reductions from sparse sets to tally sets
- On sparse sets in NP-P
- On the Computational Complexity of Algorithms
- P-Printable Sets
- Separating Nondeterministic Time Complexity Classes
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Tally languages and complexity classes
Cited in
(14)- A note on sparse sets and the polynomial-time hierarchy
- Computation times of NP sets of different densities
- Sparse selfreducible sets and nonuniform lower bounds
- Complexity classes and sparse oracles
- Defying upward and downward separation
- NL-printable sets and nondeterministic Kolmogorov complexity
- scientific article; zbMATH DE number 3845567 (Why is no real title available?)
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- scientific article; zbMATH DE number 4068281 (Why is no real title available?)
- scientific article; zbMATH DE number 4080915 (Why is no real title available?)
- scientific article; zbMATH DE number 512827 (Why is no real title available?)
- scientific article; zbMATH DE number 1072529 (Why is no real title available?)
- On sparseness and Turing reducibility over the reals
- NL-printable sets and nondeterministic Kolmogorov complexity
This page was built for publication: Sparse sets and collapse of complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854459)
