5
$\begingroup$

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

$\endgroup$
  • $\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
4
$\begingroup$

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

$\endgroup$
  • 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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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