Hi Brent,

`Ok, I am rapidly loosing the connection that abstract models have with`

`the physical world, at least in the case of computations. If there is no`

`constraint on what we can conjecture, other than what is required by one's`

`choice of logic and set theory, what relation do mathematical models have`

`with reality?`

## Advertising

Is this not as obvious as it appears? BTW, Scott Aaronson has a nice paper on the P=NP problem that is found here: http://www.scottaaronson.com/papers/npcomplete.pdf I recommend this paper as well: http://www.scottaaronson.com/papers/are.ps Kindest regards, Stephen

`----- Original Message -----`

`From: "Brent Meeker" <[EMAIL PROTECTED]>`

To: <everything-list@eskimo.com> Sent: Friday, July 22, 2005 3:40 PM Subject: Re: is induction unformalizable?

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. 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 MeekerRegards -- Brent Meeker