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

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.