In complexity, Is the relationship between P and R known?

Question

The relationship between P and NP is unknown; However, we can ask an "easier" question, what is the relationship between P and R (=decidable languages)? In other words, is there a (decidable) problem shown to be not solvable in polynomial time? This wikipedia diagram states that EXPSPACE is strictly contained in R, meaning that P is strictly contained in R, however, I couldn't find any further details on this. Thanks!

Answer 1

Given any total recursive function $\rho:\mathbb N\to \mathbb N$, you can define a decidable subset of $\mathbb N$ which is not decidable by any Turing machine in less than $\rho$ time.

Essentially, this is done by a diagonal argument, by finding a recursive language $L:\mathbb N\to\{0,1\}$ which does not agree with any function that takes $\rho(n)$ time for all $n$.

If $\phi_e$ is an effective enumeration of computable Turing functions, we say $\phi_{e,s}(n)\downarrow$ if the Turing machine finished computation in time $s$ given input $n$. For any $N$, we enumerate $1\leq e \leq N$ such that for all $1\leq n \leq N$, $\phi_{e,\rho(n)}(n)\downarrow$ and all resulting values are in $\{0,1\}$, and we pick the smallest such $e$ which we have not previously excluded. Then we define $L(N)=1-\phi_e(N)$. (If there is no such $e$, then we defint $L(N)=0$.) Now we added this $e$, if it existed, to the "previously excluded" set for later steps. Note that this all takes a finite amount of time for each $N$.

This induction has the effect that if $\phi_e(n)$ runs in time $\rho(n)$ for all $n$ and always returns $0,1$, then it gets excluded at some step. (This requires proof, but basically you can show that $\phi_e$ will get excluded by step $N=2e$.)

The resulting $L$ will be a total function which takes only the values $0,1$ and which is not equal to any computable function which takes $\rho(n)$ time to compute for all $n$.

Now, if $\rho(n)=2^n$, then this means that the resulting $L$ cannot, in particular, be computed in polynomial time.

Answer 2

By the Time Hierarchy Theorem, we know that class P is strictly contained in class EXPTIME. A natural example of problems that lie in EXPTIME but not P (aka the EXPTIME-complete problems) is the decision problem of whether a deterministic Turing machine would halt on a certain input within $k$ steps.

Now EXPTIME, by definition, is a class of decision problems and is therefore contained in R (and, by Time Hierarchy Theorem, is strictly contained in R). So it follows that $P \subsetneq R$.