Verifying whether one-tape Turing machines run in linear time (Q2009635): Difference between revisions

@@ Property / DOI @@
-.1016/j.jcss.2019.08.004
@@ Property / DOI: 10.1016/j.jcss.2019.08.004 / rank @@
-Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2967571932
@@ Property / OpenAlex ID: W2967571932 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.0496
@@ Property / arXiv ID: 1312.0496 / rank @@
+Normal rank
@@ Property / cites work @@
+Some combinatorial game problems require Ω(             <i>               n               <sup>k</sup>             </i>             ) time
+Normal rank
@@ Property / cites work @@
+Nontrivial lower bounds for the least common multiple of some finite sequences of integers
+Normal rank
@@ Property / cites work @@
+Verifying time complexity of Turing machines
@@ Property / cites work: Verifying time complexity of Turing machines / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity of One-Tape Turing Machine Computations
+Normal rank
@@ Property / cites work @@
+One-tape, off-line Turing machine computations
@@ Property / cites work: One-tape, off-line Turing machine computations / rank @@
+Normal rank
@@ Property / cites work @@
+Arithmetical hierarchy and complexity of computation
+Normal rank
@@ Property / cites work @@
+On the structure of one-tape nondeterministic Turing machine time hierarchy
+Normal rank
@@ Property / cites work @@
+An NP-complete language accepted in linear time by a one-tape Turing machine
+Normal rank
@@ Property / cites work @@
+Q5192993
@@ Property / cites work: Q5192993 / rank @@
+Normal rank
@@ Property / cites work @@
+Separating Nondeterministic Time Complexity Classes
+Normal rank
@@ Property / cites work @@
+Theory of one-tape linear-time Turing machines
@@ Property / cites work: Theory of one-tape linear-time Turing machines / rank @@
+Normal rank
@@ Property / cites work @@
+A Turing machine time hierarchy
@@ Property / cites work: A Turing machine time hierarchy / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q127356913
@@ Property / Wikidata QID: Q127356913 / rank @@
+Normal rank
@@ Property / DOI @@
+.1016/J.JCSS.2019.08.004
@@ Property / DOI: 10.1016/J.JCSS.2019.08.004 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:2009635