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{...
- 2,758
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 ...
- 15.6k
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/\...
- 2,422
6
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 ...
- 2,422
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.
- 6,947
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 ...
- 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 ...
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 ...
- 2,422
Only top scored, non community-wiki answers of a minimum length are eligible