# Tagged Questions

The tag has no usage guidance.

157 views

$\newcommand{\cc}[1]{\mathsf{#1}}$Does a theorem along the following lines hold: If $g(n)$ is a little bigger than $f(n)$, then $\cc{NTIME}(g) \cap \cc{coNTIME}(g) \neq \cc{NTIME}(f) \cap \cc{coNTIME}(... 1answer 138 views ### Is there an additive time hierarchy theorem? I would like something like this to be true: Conjecture: There is a function$g(n)$such that for all functions$f(n)$(perhaps satisfying some reasonable properties, like time-constructability), ... 1answer 476 views ### Is$\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$? Define$\mathsf{DTIME}(f(n))$as the class of languages that can be accepted by a (multitape) Turing machine in time$f(n) + 1$. (The "$+ 1$" is just to simplify notation and avoid confusion.) Notice ... 0answers 163 views ### Open questions about linear-time What are some interesting open or solved-but-hard questions around problems having linear-time solutions? Ala riffle shuffles. I'm especially curious about problems which people believe to be linear-... 0answers 92 views ### Real-time countable vs fully time-constructible Real-time countable functions were used in time hierarchy theorem in the papers of Hartmanis and Stearns (Theorem 9, 9.1 ...) and also of Hennie and Stearns (Theorems 3, 5, 7 ...). Now it is a "... 2answers 937 views ### Hierarchy for BPP vs derandomization In one sentence: would the existence of a hierarchy for$\mathsf{BPTIME}$imply any derandomization results? A related but vaguer question is: does the existence of a hierarchy for$\mathsf{BPTIME}$... 2answers 485 views ### What happens if we improve the time hierarchy theorems? In a nutshell, the time hierarchy theorems say that a Turing machine can solve more problems if it has more time for computation. In detail for deterministic TM and time-constructable functions$f,g$... 2answers 757 views ### Justification of log f in DTIME hierarchy theorem If we look at DTIME hierarchy theorem, we've got a log due to the overhead in simulation of a deterministic Turing Machine by a universal machine :$DTIME(\frac{f}{\log f}) \subsetneq DTIME(f)$We ... 2answers 588 views ### Is there a Time Hierarchy theorem for PH? Is it true that there are problems in the polynomial hierarchy solvable in time$O(n^k)$(by an alternating Turing machine in some level of the polynomial hierarchy) that are not solvable in$O(n^{k-1}...
Consider the language $A=\{0^{k}1^{k}|k\geq0\}$ . On Sipser's book "Introduction to the Theory of Computation" an algorithm with running time $O(n\log n)$ is given, on single-tape TM. We also know ...