3 ms·
The argument is not only unconvincing, it is incorrect. The time hierarchy theorem implies the existence of problems of difficulty n^M for arbitrary M, and all
by algorias 11y ago
The argument is not only unconvincing, it is incorrect. The time hierarchy theorem implies the existence of problems of difficulty n^M for arbitrary M, and all those problems are clearly in NP.
- baddox 11y agoThe time hierarchy theorem does not state that there are NP-complete problems that cannot be solved in polynomial time. If it stated that and was well-accepted, then there would be no P ?= NP mystery.