NL-printable sets and nondeterministic Kolmogorov complexity

DOI10.1016/J.TCS.2006.01.005zbMATH Open1088.68072OpenAlexW1971290294MaRDI QIDQ2369009FDOQ2369009

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

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

zbMATH Keywords

Kolmogorov complexityNL-printabilityUnambiguous logspace

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Hardness vs randomness
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• A note on logspace optimization
• Nondeterministic Space is Closed under Complementation
• Randomness conservation inequalities; information and independence in mathematical theories
• The method of forced enumeration for nondeterministic automata
• Title not available (Why is that?)
• Structure and importance of logspace-MOD class
• Making Nondeterminism Unambiguous
• A very hard log-space counting class
• Title not available (Why is that?)
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Resource-bounded Kolmogorov complexity revisited
• Counting classes: Thresholds, parity, mods, and fewness
• Tally languages and complexity classes
• On sparse sets in NP-P
• Computation times of NP sets of different densities
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Title not available (Why is that?)
• P-Printable Sets
• Upward separation for FewP and related classes
• Title not available (Why is that?)
• On the power of parity polynomial time
• An unambiguous class possessing a complete set
• Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
• Isomorphisms and 1-L reductions
• Sparse sets and collapse of complexity classes
• Title not available (Why is that?)
• Polynomial-time isomorphism of 1-L-complete sets
• Title not available (Why is that?)
• L-Printable Sets
• Title not available (Why is that?)

Cited In (5)

• NL-printable sets and nondeterministic Kolmogorov complexity
• The Complexity of Complexity
• \textsc{ReachFewL} = \textsc{ReachUL}
• On the power of unambiguity in log-space
• 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)