10 votes
Accepted

Are space and time hierarchies even comparable?

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{...
Mikhail Rudoy's user avatar
9 votes
Accepted

$DTIME_1(o(n^2))\setminus$ REGULAR

For example, I think you can decide if $\lfloor\log_2|w|\rfloor$ is even in time $O(n\log n)$: you first overwrite the input string with all 1s, and then do $\log n$ passes over the string where you ...
Emil Jeřábek's user avatar
7 votes

Justification of log f in DTIME hierarchy theorem

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 ...
Dmytro Taranovsky's user avatar
6 votes
Accepted

Time Hierarchies in DSPACE(O(s(n)))

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/\...
Dmytro Taranovsky's user avatar
4 votes
Accepted

Can we replace deterministic part of alternative turing machine with some other equivalent machines?

I think you need to work on what $(0.2)^2$ is before you go any further.
Jeffrey Shallit's user avatar
3 votes

$DTIME_1(o(n^2))\setminus$ REGULAR

The language $L=\{0^n1^n : n\geq 0\}$ is non-regular, but decidable in time $O(n\log n)$ on a one-tape Turing machine (one can either use a counter or iteratively remove every next 0 and 1 plus check ...
QMath's user avatar
  • 303
1 vote

Are space and time hierarchies even comparable?

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 ...
CurryKatsuCutlet's user avatar
1 vote
Accepted

How fine-grained can the time hierarchy theorem be in a reasonable model?

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 ...
Dmytro Taranovsky's user avatar

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