Re:A Solution of the P versus NP Problem?
by OJFord on Monday August 14, 2017 @02:29PM
(#15011155)
It's generally not the case though: problems that arise 'naturally', i.e have not been constructed to counter my forthcoming point, in P seem to be of low order.
If NPC problems where P in n^{10^100}, wouldn't we expect a wealth of problems between there and the myriad at n^2 or so?
Re:A Solution of the P versus NP Problem?
by baddox on Monday August 14, 2017 @04:17PM
(#15012439)
Why would that be more surprising than the fact that some "natural" problems are polynomial and some are exponential, given that an exponential running time is asymptotically slower than any polynomial running time?
If NPC problems where P in n^{10^100}, wouldn't we expect a wealth of problems between there and the myriad at n^2 or so?