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?

   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 Meeker



Regards
--
Brent Meeker


Reply via email to