On 10/9/2014 7:24 PM, John Clark wrote:
> NP problem *are* computable.
Yes, but not in polynomial time; our brains can't do it, our computers can't do it, and
there is not one scrap of evidence that nature can do it either.
There seems to be some confusion there. NP problems constitute a /class /of problems of
arbitrarial large inputs and everyone of them can be solved in a finite time. Those
finite times can be bounded by a polynomial function. 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. If algorithm (1) solves problems in time t1=10000*N^200 that's a
polynomial time. And if algorithm (2) solves the same problems in t2=exp(N/100) is an
exponential time. But for N<8000 you'd do well to use the exponential time algorithm. So
the dichotomy between NP and P is something that happens in Platonia where things are
"taken to the limit".
Brent
--
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.
