# DTIME and PSPACE

Most people believe that $\mathsf{P} \not= \mathsf{PSPACE}$ and $\mathsf{PSPACE} \not=\mathsf{EXP}$.

Is there a function $f$ such that $f(n) < 2^n$ and $f(n) > p(n)$ for every polynomial $p$ (and rather large $n$) such that most people believe that $\mathsf{DTIME}(f(n)) \subseteq \mathsf{PSPACE}$ ?

• Do you want a bigger upper bound than $2^n$? I'm not sure about common belief that $\mathsf{PSPACE} \subseteq \mathsf{DTIME}(2^n)$. Note that $\mathsf{EXP}$ can be a bit ambiguous or unclear, but it means $\bigcup_k \mathsf{DTIME}(2^{n^k})$. – usul Oct 2 '16 at 22:25
• @usul no, I want a bigger upper bound than $\mathsf{P}$ – Alexey Milovanov Oct 2 '16 at 22:34
• I wouldn't believe that $TIME(n^{\omega(1)})$ is contained in $PSPACE$... – Ryan Williams Oct 3 '16 at 1:55
• I am not sure this question is appropriate here, as it is opinion based, unless we could somehow conduct a poll.. – Sasho Nikolov Oct 3 '16 at 4:43
• I am pretty sure that if $g$ is a function that eventually dominates all recursive functions, then $\mathrm{DTIME}(n^{g^{-1}(n)})$ is included in PSPACE (and in fact coincides with P). Presumably, some slower growing and computable function in place of $g$ will work, too. You should probably require $f(n)$ to be time-constructible or something, so that $\mathrm{DTIME}(f(n))$ is strictly larger than P. – Emil Jeřábek 3.0 Oct 3 '16 at 6:00

Let $g\colon\mathbb N\to\mathbb N$ be an increasing function that eventually majorizes every recursive function, and $h$ be its inverse; more precisely, $$h(n)=\min\{m:g(m)\ge n\}.$$ Then $h$ is an unbounded nondecreasing function with the property that every recursive function eventually majorized by $h$ is bounded. Put $$f(n)=n^{h(n)}.$$ Then $f$ is (barely) superpolynomial, and I claim $$\mathrm{DTIME}(f(n))\subseteq\mathrm{PSPACE}.$$ As a matter of fact, we have $$\mathrm{DTIME}(f(n))=\mathrm P.$$ In order to see this, let $L$ be a language recognized by a TM $M$ working in time $f(n)$. Put $$e_M(n)=\min\{k:\text{M terminates in time \le n^k for every input of length n}\}.$$ Then $e_M$ is a recursive function, and $e_M(n)\le h(n)$. Thus, $e_M$ is bounded, which means that $M$ actually runs in polynomial time, and $L\in\mathrm P$.