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" <meekerdb.domain.name.hidden>
> To: "Stephen Paul King" <stephenk1.domain.name.hidden>
> 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
Received on Fri Jul 22 2005 - 18:29:50 PDT