NL-printable sets and nondeterministic Kolmogorov complexity (Q2369009): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2006.01.005
+Normal rank
@@ Property / OpenAlex ID @@
+W1971290294
@@ Property / OpenAlex ID: W1971290294 / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial-time isomorphism of 1-L-complete sets
@@ Property / cites work: Polynomial-time isomorphism of 1-L-complete sets / rank @@
+Normal rank
@@ Property / cites work @@
+Isomorphisms and 1-L reductions
@@ Property / cites work: Isomorphisms and 1-L reductions / rank @@
+Normal rank
@@ Property / cites work @@
+Q4474202
@@ Property / cites work: Q4474202 / rank @@
+Normal rank
@@ Property / cites work @@
+Non-commutative arithmetic circuits: depth reduction and size lower bounds
+Normal rank
@@ Property / cites work @@
+Q4258574
@@ Property / cites work: Q4258574 / rank @@
+Normal rank
@@ Property / cites work @@
+Isolation, matching, and counting uniform and nonuniform upper bounds
+Normal rank
@@ Property / cites work @@
+P-Printable Sets
@@ Property / cites work: P-Printable Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Q4240333
@@ Property / cites work: Q4240333 / rank @@
+Normal rank
@@ Property / cites work @@
+A very hard log-space counting class
@@ Property / cites work: A very hard log-space counting class / rank @@
+Normal rank
@@ Property / cites work @@
+A note on logspace optimization
@@ Property / cites work: A note on logspace optimization / rank @@
+Normal rank
@@ Property / cites work @@
+Counting classes: Thresholds, parity, mods, and fewness
+Normal rank
@@ Property / cites work @@
+Tally languages and complexity classes
@@ Property / cites work: Tally languages and complexity classes / rank @@
+Normal rank
@@ Property / cites work @@
+Q4251044
@@ Property / cites work: Q4251044 / rank @@
+Normal rank
@@ Property / cites work @@
+Resource-Bounded Kolmogorov Complexity Revisited
@@ Property / cites work: Resource-Bounded Kolmogorov Complexity Revisited / rank @@
+Normal rank
@@ Property / cites work @@
+Structure and importance of logspace-MOD class
@@ Property / cites work: Structure and importance of logspace-MOD class / rank @@
+Normal rank
@@ Property / cites work @@
+Q4266543
@@ Property / cites work: Q4266543 / rank @@
+Normal rank
@@ Property / cites work @@
+On the power of parity polynomial time
@@ Property / cites work: On the power of parity polynomial time / rank @@
+Normal rank
@@ Property / cites work @@
+Q5465360
@@ Property / cites work: Q5465360 / rank @@
+Normal rank
@@ Property / cites work @@
+L-Printable Sets
@@ Property / cites work: L-Printable Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse sets and collapse of complexity classes
@@ Property / cites work: Sparse sets and collapse of complexity classes / rank @@
+Normal rank
@@ Property / cites work @@
+On sparse sets in NP-P
@@ Property / cites work: On sparse sets in NP-P / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse sets in NP-P: EXPTIME versus NEXPTIME
@@ Property / cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME / rank @@
+Normal rank
@@ Property / cites work @@
+Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
+Normal rank
@@ Property / cites work @@
+Computation times of NP sets of different densities
+Normal rank
@@ Property / cites work @@
+Nondeterministic Space is Closed under Complementation
+Normal rank
@@ Property / cites work @@
+Q3995641
@@ Property / cites work: Q3995641 / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+An unambiguous class possessing a complete set
@@ Property / cites work: An unambiguous class possessing a complete set / rank @@
+Normal rank
@@ Property / cites work @@
+Randomness conservation inequalities; information and independence in mathematical theories
+Normal rank
@@ Property / cites work @@
+Q4337021
@@ Property / cites work: Q4337021 / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Upward separation for FewP and related classes
@@ Property / cites work: Upward separation for FewP and related classes / rank @@
+Normal rank
@@ Property / cites work @@
+Making Nondeterminism Unambiguous
@@ Property / cites work: Making Nondeterminism Unambiguous / rank @@
+Normal rank
@@ Property / cites work @@
+The method of forced enumeration for nondeterministic automata
+Normal rank