On Thu, Oct 9, 2014 at 11:36 PM, meekerdb <[email protected]> wrote:
> NP problems constitute a *class *of problems of arbitrarial large inputs > and everyone of them can be solved in a finite time. > Yes. > When it is said that NP problems can't be solved in polynomial time that > refers to how the time required scales with the size of the problem. > Exactly. > If algorithm (1) solves problems in time t1=10000*N^200 that's a > polynomial time. > Yes n^200 is polynomial time. but 200^n is not. A computer may be able to solve a polynomial time problem but if it's a exponential time problem the complexity increases so enormously for even a small increase in n that finding a perfect solution is unobtainable. The ultimate in hard problems would be one that is not computable, like trying to find even a good approximation to one of those numbers that Turing proved to exist, you couldn't do that even if you had infinite time at your disposal. To me the fact that most real numbers, nearly all of them in fact, are not computable strongly hints that nature does not use real numbers to figure out what it should do next. > > So the dichotomy between NP and P is something that happens in Platonia > And it also happens on planet earth, we can solve P problems but as far as we know even nature can't solve NP complete problems in polynomial time, and given that the Universe is only 13.8 billion years old that means nature can't solve NP complete problems at all unless n is very very small. John K Clark -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
