3 ms·
But is that a convincing argument? His argument seems to be that he can come up with a integer M that is so unimaginably large that we can surely solve any n bi
by devilsavocado 11y ago
But is that a convincing argument? His argument seems to be that he can come up with a integer M that is so unimaginably large that we can surely solve any n bit problem in NP space in n^M steps. Knuth himself prefaces his argument by saying that it is naive!
His main point, which is more about the practical effects of P=NP is much more convincing, and actually very common I believe.
- algorias 11y agoThe 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.