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}$ ?

  • $\begingroup$ 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})$. $\endgroup$ – usul Oct 2 '16 at 22:25
  • $\begingroup$ @usul no, I want a bigger upper bound than $\mathsf{P}$ $\endgroup$ – Alexey Milovanov Oct 2 '16 at 22:34
  • 9
    $\begingroup$ I wouldn't believe that $TIME(n^{\omega(1)})$ is contained in $PSPACE$... $\endgroup$ – Ryan Williams Oct 3 '16 at 1:55
  • 1
    $\begingroup$ I am not sure this question is appropriate here, as it is opinion based, unless we could somehow conduct a poll.. $\endgroup$ – Sasho Nikolov Oct 3 '16 at 4:43
  • 4
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Oct 3 '16 at 6:00

Since no clarification seems to be forthcoming, let me just answer the question as is, for the record.

The answer is yes, one can prove there is such a function. (Which doesn’t necessarily mean most people will believe it, but anyway.)

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

  • 2
    $\begingroup$ This follows from the Union-Theorem of McCreight and Meyer, too. $\endgroup$ – Markus Bläser Jul 14 '17 at 9:19

Your Answer

