NL-printable sets and Nondeterministic Kolmogorov Complexity
From MaRDI portal
Publication:4924524
DOI10.1016/S1571-0661(04)80838-7zbMath1264.68089OpenAlexW2067416548MaRDI QIDQ4924524
Publication date: 6 June 2013
Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s1571-0661(04)80838-7
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On sparse sets in NP-P
- A very hard log-space counting class
- Hardness vs randomness
- Upward separation for FewP and related classes
- Computation times of NP sets of different densities
- Sparse sets and collapse of complexity classes
- A note on logspace optimization
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Resource-Bounded Kolmogorov Complexity Revisited
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- Randomness conservation inequalities; information and independence in mathematical theories
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Structure and importance of logspace-MOD class
- L-Printable Sets
- P-Printable Sets
- Tally languages and complexity classes
- Making Nondeterminism Unambiguous
- An unambiguous class possessing a complete set
- Power from Random Strings
- On the power of parity polynomial time
- Counting classes: Thresholds, parity, mods, and fewness
This page was built for publication: NL-printable sets and Nondeterministic Kolmogorov Complexity
