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?