NL-printable sets and nondeterministic Kolmogorov complexity

DOI10.1016/J.TCS.2006.01.005MaRDI QIDQ2369009zbMATH OpenOpenAlexFDO

Authors Eric Allender

Publication date 28 April 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.01.005

zbMATH Keywords

Kolmogorov complexityNL-printabilityUnambiguous logspace

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• NL-printable sets and nondeterministic Kolmogorov complexity
• L-Printable Sets
• scientific article; zbMATH DE number 107775
• P-Printable Sets
• Sets with small generalized Kolmogorov complexity

Cites work

• 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?)
• 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
• 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

(5)

• On the power of unambiguity in log-space
• Windable heads and recognizing \textsf{NL} with constant randomness
• \textsc{ReachFewL} = \textsc{ReachUL}
• NL-printable sets and nondeterministic Kolmogorov complexity
• The Complexity of Complexity

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)