Hacker News new | ask | show | jobs
by algorias 3858 days 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.
1 comments

The 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.
Correct, but I didn't claim what you are refuting. I just said that there is no upper bound to "how polynomiallly hard" a problem can get, i.e. Knuths intuition is wrong.
Look at the quote. Knuth is explicitly only talking about NP problems.