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

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

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

CC BY-SA 3.0
2017-07-14T09:19:37.703Z
This follows from the Union-Theorem of McCreight and Meyer, too.
Markus Bläser
CC BY-SA 3.0
2017-07-13T14:33:28.687Z
2017-07-13T14:33:28.687Z
Emil Jeřábek
<p>Most people believe that $\mathsf{P} \not= \mathsf{PSPACE}$ and $\mathsf{PSPACE} \not=\mathsf{EXP}$. </p>

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

CC BY-SA 3.0
2016-10-02T22:25:01.453Z
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
CC BY-SA 3.0
2016-10-02T22:34:03.457Z
@usul no, I want a bigger upper bound than $\mathsf{P}$
Alexey Milovanov
CC BY-SA 3.0
2016-10-02T22:37:19.787Z
My comment might have been unclear, I meant do you want to take out $2^n$ and replace it with something bigger, or are you implying that most people believe $\mathsf{PSPACE} \subseteq \mathsf{DTIME}(2^n)$? (If so, is it true?)
usul
CC BY-SA 3.0
2016-10-02T22:40:51.997Z
@usul do you think that $ \bigcup_k \mathsf{DTIME}(n^{k \log n}) \subseteq \mathsf{PSPACE}$?
Alexey Milovanov
CC BY-SA 3.0
2016-10-03T01:55:15.090Z
I wouldn't believe that $TIME(n^{\omega(1)})$ is contained in $PSPACE$...
Ryan Williams
CC BY-SA 3.0
2016-10-03T04:43:06.377Z
I am not sure this question is appropriate here, as it is opinion based, unless we could somehow conduct a poll..
Sasho Nikolov
CC BY-SA 3.0
2016-10-03T06:00:41.033Z
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
CC BY-SA 3.0
2016-10-03T08:27:03.363Z
@SashoNikolov I would like to see for example a language in $\mathsf{DTIME}(n^{\log n})$ such that we do not about it belonging to $\mathsf{PSPACE}$.
Alexey Milovanov
CC BY-SA 3.0
2016-10-23T05:19:33.643Z
@EmilJeřábek $DTIME(n^{g^{-1}(n)})\supseteq TIME(n^{\omega(1)})$?
Turbo
CC BY-SA 3.0
2016-10-23T12:40:18.403Z
@AJ. What do you mean by $\mathrm{TIME}(n^{\omega(1)})$? Taken by its face value, it denotes the set of all computable predicates, as arbitrarily fast growing functions are $\omega(1)$.
Emil Jeřábek
CC BY-SA 3.0
2016-10-23T18:33:10.587Z
@EmilJeřábek sorry bad query there.
Turbo
<cc.complexity-theory><complexity-classes>
DTIME and PSPACE
Alexey Milovanov
# DTIME and PSPACE

(Asked by: username_0 on 2016-10-02)

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

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: 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})$.  
> **username_0**: @usul no, I want a bigger upper bound than $\mathsf{P}$  
> **username_1**: My comment might have been unclear, I meant do you want to take out $2^n$ and replace it with something bigger, or are you implying that most people believe $\mathsf{PSPACE} \subseteq \mathsf{DTIME}(2^n)$? (If so, is it true?)  
> **username_0**: @usul do you think that $ \bigcup_k \mathsf{DTIME}(n^{k \log n}) \subseteq \mathsf{PSPACE}$?  
> **username_2**: I wouldn't believe that $TIME(n^{\omega(1)})$ is contained in $PSPACE$...  
> **username_3**: I am not sure this question is appropriate here, as it is opinion based, unless we could somehow conduct a poll..  
> **username_4**: 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.  
> **username_0**: @SashoNikolov I would like to see for example a language in $\mathsf{DTIME}(n^{\log n})$ such that we do not about it belonging to $\mathsf{PSPACE}$.  
> **username_5**: @EmilJeřábek $DTIME(n^{g^{-1}(n)})\supseteq TIME(n^{\omega(1)})$?  
> **username_4**: @AJ. What do you mean by $\mathrm{TIME}(n^{\omega(1)})$? Taken by its face value, it denotes the set of all computable predicates, as arbitrarily fast growing functions are $\omega(1)$.  
> **username_5**: @EmilJeřábek sorry bad query there.  

---

## 1 answers

### Answer by username_4 on 2017-07-13. Score: 4

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

> **Comments:**
> **username_6**: This follows from the Union-Theorem of McCreight and Meyer, too.  

---

