# Tag Info

Superpolynomial time complexity cannot be in P. While this appears easy to believe, it is actually a false belief. Formally, we may think that if $f(n)$ is a superpolynomial function, then ${\mathsf {DTIME}}(f(n)) \not\subseteq {\mathsf P}$. Surprisingly, this is wrong. In fact there exists a superpolynomial function $f(n)$ with {\mathsf P} = {\mathsf {...