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 ...


9

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 turn every other 1 into a 0 (while skipping 0s that are already there). You keep track of the number of passes modulo 2.


6

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