But I'm not sure what it would mean for an instance of P=NP computation to exist in nature. What it would mean in computer science is that there was an algorithm for translating any NP algorithm into a P algorithm for the same problem. This refers to classes of algorithms for classes of problems. If you observe a certain instance of protein folding - that's not an algorithm. If you study many instances of protein folding you may develop an algorithm that will predict how a class of proteins will fold and that may scale as NP. Someone else might find another algorithm that scales as P. But that's not the same as finding a way of translating any NP algorithm into a P one. And neither one shows that nature is using an algorithm. Nature isn't predicting how a class of proteins is going to fold - it's just folding a few specific examples.

## Advertising

Brent Meeker On 22-Jul-05, you wrote: > Hi Brent, > > You make a very good point and I agree with you completely! > But I am arguing that it is the distinction between physical and > abstract systems that seems to require some closer examination, > and a slightly different point. If we are going to use arguments > that are only "in principle"based to make decisions about > situations in the physical world, does it not follow that we > might be making serious errors? > My claim stands! > > "... if there did occurs an instance of a P=NP computation > within our physical universe then it follows that Nature would > have found a way to implement it widely." > > If "P=NP Oracles" are allowed at all in our physical > universe, then it follows that some evidence could be found of > their occurance. If they can only exist in the very special case > of an abstract universe, what connection do they have with > physics or anything other than metaphysics? > > Stephen > > PS. Please cc your reply to the Everything List, I am sure that > others are interested in this thread. > > ----- Original Message ----- > From: "Brent Meeker" <[EMAIL PROTECTED]> > To: "Stephen Paul King" <[EMAIL PROTECTED]> > Sent: Friday, July 22, 2005 3:07 PM > Subject: Re: is induction unformalizable? > > >> On 22-Jul-05, you wrote: >> >>> Dear Brent, >> >> Could you name some examples? In the real world, >> computations obey the laws of thermodynamics, among other >> things, thus for problems with the same number of independent >> degrees of freedom, the P problems can be computed faster >> than >> the NP. Of course this is just an average, but baring some >> counter-examples I fail to understand your point. >> >> Stephen >> >> The laws of thermodynamics apply to physical processes, not >> abstractions like algorithms. Of course computations are >> physical processes - but P and NP are classes of algorithms, >> not >> computations. I'll see if I can find some specific examples, >> but >> the general point is that a polynomial algorithm may have a >> large >> fixed cost and then scale, say, linearly with the size of the >> problem; while another algorithm for the same class of problem >> may have a small fixed cost yet scale exponentially. Then up >> to >> some size (which may be very large) the latter will be faster >> than the former. It is only in the limit of infinite size that >> a >> P algorithm is necessarily faster than an NP one. Since all >> examples from Nature are finite, you can't infer that Nature >> must >> have found P algorithms for problems we think are NP. >> >> Brent Meeker >> > > Regards -- Brent Meeker