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" <meekerdb.domain.name.hidden>
To: <everything-list.domain.name.hidden>
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" <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 - 19:47:20 PDT