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