# Natural Decision Problem not in PTIME

Are there any natural decision problems which are guaranteed not to be in $\mathsf{PTIME}$? Preferably natural graph problems like $\mathsf{CLIQUE}, \mathsf{VERTEXCOVER}$ etc. (However, they would be in $\mathsf{PTIME}$ if $\mathsf{PTIME}=\mathsf{NPTIME}$).

The Time hierarchy theorem suggests a $\mathsf{EXPTIME}$ complete problem. Any graph problems which are $\mathsf{EXPTIME}$-complete?

"Cops and robbers" is a natural $\mathsf{EXPTIME}$-complete graph problem. Thus, there can be no polynomial time algorithm to decide the general "Cops and Robbers"-Problem.