NL-printable sets and nondeterministic Kolmogorov complexity
From MaRDI portal
Publication:2369009
Recommendations
Cites work
- A note on logspace optimization
- A very hard log-space counting class
- An unambiguous class possessing a complete set
- Computation times of NP sets of different densities
- Counting classes: Thresholds, parity, mods, and fewness
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Hardness vs randomness
- scientific article; zbMATH DE number 45125 (Why is no real title available?)
- scientific article; zbMATH DE number 1283991 (Why is no real title available?)
- scientific article; zbMATH DE number 1304314 (Why is no real title available?)
- scientific article; zbMATH DE number 1335883 (Why is no real title available?)
- scientific article; zbMATH DE number 1346519 (Why is no real title available?)
- scientific article; zbMATH DE number 1010621 (Why is no real title available?)
- scientific article; zbMATH DE number 2081089 (Why is no real title available?)
- scientific article; zbMATH DE number 2196513 (Why is no real title available?)
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Isomorphisms and 1-L reductions
- L-Printable Sets
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- Making Nondeterminism Unambiguous
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Nondeterministic Space is Closed under Complementation
- On sparse sets in NP-P
- On the power of parity polynomial time
- P-Printable Sets
- Polynomial-time isomorphism of 1-L-complete sets
- Randomness conservation inequalities; information and independence in mathematical theories
- Resource-bounded Kolmogorov complexity revisited
- Sparse sets and collapse of complexity classes
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- Structure and importance of logspace-MOD class
- Tally languages and complexity classes
- The method of forced enumeration for nondeterministic automata
- Upward separation for FewP and related classes
Cited in
(6)- On the power of unambiguity in log-space
- The Complexity of Complexity
- scientific article; zbMATH DE number 1101598 (Why is no real title available?)
- NL-printable sets and nondeterministic Kolmogorov complexity
- \textsc{ReachFewL} = \textsc{ReachUL}
- Windable heads and recognizing \textsf{NL} with constant randomness
This page was built for publication: NL-printable sets and nondeterministic Kolmogorov complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2369009)
