7

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 {...


4

"When a problem is algorithmically undecidable, it means that it has a definite provable answer (yes or no) on all instances, but no unique algorithm is capable to reach this answer uniformly on all instances." It was a revelation for me to discover that any undecidable problem has particular instances that are independent of ZFC. Otherwise, ...


Only top voted, non community-wiki answers of a minimum length are eligible