Tag Info

Hot answers tagged time-hierarchy

11

From the comment: In "Deterministic Turing Machines in the Range between Real-Time and Linear-Time" I found: ... if $r \in T^{−1}(DTM)$ and $r' \in o(r)$ then $DTIME(n+r') \subset DTIME(n+r)$ ...

10

You can get the situation you describe by choosing weird functions $f(n)$ and $g(n)$. For example, let $g(n) = n^3$ and $$f(n) = \begin{cases} n & \text{if n is odd}, \\\ 2^{n^5} & \text{if n is even}. \end{cases}$$ Then choose $L_1$ and $L_2$ as follows: $L_1$ is a language containing only strings of even length which can be decided in ...

8

For n-tape TMs a tight time hierarchy result similar to the space hierarchy theorem is proven by Furer in 1982. The $\lg$ factor is not needed. The $\lg$ factor for the time hierarchy theorem stated in your post is only for single-tape TMs. Unless you are very committed to the single-tape model for some reason there is not a difference between space and ...

5

This is an open problem: It is open whether $\mathrm{DTISP}(O(n \log n),O(n)) = \mathrm{DSPACE}(O(n))$ (or even $\mathrm{NSPACE}(O(n))$). We only know that $\mathrm{DTIME}(O(n))⊆\mathrm{DSPACE}(O(n/\log n))$. However, under plausible computational complexity conjectures, there is a proper hierarchy. For example, if for every $ε>0$, CIRCUIT-SAT ∉ i.o.-$O(... 5 For a fixed number of tapes greater than one,$\mathrm{Time}(o(f)) ⊊ \mathrm{Time}(O(f)$) for time-constructible$f$. The logarithmic overhead comes from the tape reduction theorem, where any number of tapes can be converted into two tapes (or even just a single tape and a stack and with just oblivious movement). If the number of tapes is not fixed, we do ... 4 I think you need to work on what$(0.2)^2$is before you go any further. 3 I don't see the need for your clarification, since through linear speed-up those sets are exactly the same. It is clear why you need to avoid using asymptotics, since$f(n)-g(n)$and$f(n)$are asymptotically the same, but not using asymptotics doesn't somehow make the linear speed-up theorem not true. Some further insight can be gained.$g(n)$is actually$...

1

In some sense yes, specifically as of right now we have that: $\textbf{DTIME}(S(n)) \subseteq \textbf{SPACE}(S(n)) \subseteq \textbf{NSPACE}(S(n)) \subseteq \textbf{DTIME}(2^{O(S(n))})$ And also we know that $\textbf{PSPACE} \subsetneq \textbf{EXPSPACE}$ So that also implies $\textbf{P} \subsetneq \textbf{EXPSPACE}$. Though we don't know what the specific ...

1

The three ingredients of a diagonalization based proof of the time hierarchy theorem are universal simulation, timing, and reversal. By choosing (or defining) a computational model where these operations are efficient, we get a sharp hierarchy theorem. In particular, by using a model with a timed virtualization primitive satisfying certain conditions, we ...

Only top voted, non community-wiki answers of a minimum length are eligible