An example of a computable problem that is not in P

Question

I am trying to find a simple example of a problem that is computable but not in P, I know very well that it would be enough to get one in NEXTIME-complete however the problems that I find in this set are very artificial

Answer 1

As Yuval Filmus already mentioned in the comments, because of the time hierarchy theorem, we know $\mathsf{P} \neq \mathsf{EXP}$. Hence, any $\mathsf{EXP}$-complete problem is an example. These include, for instance, generalized chess and checkers.

Answer 2

This isn't really a natural example, but a natural technique (which I'm leaving as an answer instead of a comment since I think it's still valuable, and it's clearly too long): we can use a diagonal argument. Specifically, while we can't tell whether a Turing machine runs in polynomial time, we can whip up a list of polynomial-time Turing machines such that every polytime machine is equivalent to one on the list.

Namely, let $(M_e)_{e\in\mathbb{N}}$ be your favorite enumeration of Turing machines, let $(p_e)_{e\in\mathbb{N}}$ be your favorite enumeration of polynomials, and let $\langle\cdot,\cdot\rangle$ be your favorite pairing function on $\mathbb{N}$. Then we let $N_{\langle i,j\rangle}$ be the machine "$M_i$ cut off by $p_j$" - on input $k$, $N_{\langle i,j\rangle}$ simulates $M_i$ for $p_j(k)$-many steps, and (say) halts and ouptuts $0$ of $M_i(k)$ doesn't halt in that time. The key point is that if $M_i$ really does run in polynomial time, there is some $j$ such that $N_{\langle i,j\rangle}$ is "equivalent to" $M_i$ in the obvious sense.

Now let $X=\{n: N_n(n)=0\}$ - intuitively, $X$ is the set of $n$ which aren't in the $n$th polynomial-time-computable set. More generally, this technique lets us diagonalize out of any complexity class which is effectively describable - the reason we can't diagonalize out of REC (= the set of all computable sets) is that we have no way to "cheat" in the above manner and whip up an enumeration of those Turing machines which correspond to computable sets (= those which always halt - put another way, the set $Tot$ of always-halting Turing machines is not c.e. in a very strong way).