Sparse sets and collapse of complexity classes

DOI10.1006/inco.2001.3056zbMath1007.68073OpenAlexW1986861930MaRDI QIDQ1854459

Vladimír Glasnák

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2001.3056

Mathematics Subject Classification ID

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

Related Items (2)

NL-printable sets and nondeterministic Kolmogorov complexity ⋮ NL-printable sets and Nondeterministic Kolmogorov Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• On random reductions from sparse sets to tally sets
• Downward translations of equality
• On sparse sets in NP-P
• Computation times of NP sets of different densities
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Limitations of the upward separation technique
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Separating Nondeterministic Time Complexity Classes
• P-Printable Sets
• Tally languages and complexity classes
• On the Computational Complexity of Algorithms

This page was built for publication: Sparse sets and collapse of complexity classes