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
    Commented Oct 2, 2016 at 22:25
  • $\begingroup$ @usul no, I want a bigger upper bound than $\mathsf{P}$ $\endgroup$ Commented Oct 2, 2016 at 22:34
  • 9
    $\begingroup$ I wouldn't believe that $TIME(n^{\omega(1)})$ is contained in $PSPACE$... $\endgroup$ Commented Oct 3, 2016 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$ Commented Oct 3, 2016 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$ Commented Oct 3, 2016 at 6:00

1 Answer 1


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$ Commented Jul 14, 2017 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.