Hi Hal,
Here is Scott's responce.
Onward!
Stephen
----- Original Message -----
From: "Scott Aaronson" <aaronson.domain.name.hidden>
To: "Stephen Paul King" <stephenk1.domain.name.hidden>
Sent: Monday, July 25, 2005 9:02 PM
Subject: Re: Fw: what relation do mathematical models have with reality?
> Hi Stephen,
>
> It's precisely because of Hal's point that I was careful to say smallest
> *efficient* description, rather than smallest *computable* description.
> The smallest efficient description of an n-bit string x could be defined
> as the shortest program that outputs x after some fixed polynomial number
> of steps p(n). Or as the program that outputs x while minimizing L+T,
> where L is the length of the program and T is its running time. Or as the
> smallest circuit that on input i, outputs the ith bit of x. In all three
> cases, it's obvious that finding the smallest efficient description (or
> more precisely, deciding whether there exists a description of complexity
> <=K) is in NP (though interestingly, these problems are not known to be
> NP-complete). By contrast, finding the smallest *computable* description
> of x (or equivalently, finding its Kolmogorov complexity) is known to be
> equivalent to the halting problem. This is probably what Hal had in mind.
>
> So if P=NP, then we could find smallest efficient descriptions in
> polynomial time. Whether those descriptions would give us new insights
> into the things being described is of course another issue, and here
> reasonable people will have differing intuitions.
>
> Hope that helps!
> --Scott
>
>
>
> Stephen Paul King wrote:
>> Hi Scott,
>>
>> Any comments?
>>
>> Stephen
>>
>> ----- Original Message ----- From: ""Hal Finney"" <hal.domain.name.hidden>
>> To: <everything-list.domain.name.hidden>
>> Sent: Monday, July 25, 2005 2:46 PM
>> Subject: Re: what relation do mathematical models have with reality?
>>
>>
>>> Stephen Paul King wrote:
>>>
>>>> BTW, Scott Aaronson has a nice paper on the P=NP problem that is found
>>>> here:
>>>> http://www.scottaaronson.com/papers/npcomplete.pdf
>>>
>>>
>>> That describes different proposals for physical mechanisms for
>>> efficiently
>>> solving NP-complete problems: things like quantum computing variants,
>>> relativity, analog computing, and so on. He actually looked at a claim
>>> that soap bubble films effectively solve NP complete problems and tested
>>> it himself, to find that they don't work.
>>>
>>> He also discusses time travel and even what we call quantum suicide,
>>> where you kill yourself if the machine doesn't guess right.
>>>
>>> I am skeptical though about something he says in conclusion: "Even many
>>> computer scientists do not seem to appreciate how different the world
>>> would be if we could solve NP-complete problems efficiently.... If such
>>> a procedure existed, then we could quickly find the smallest Boolean
>>> circuits that output (say) a table of historical stock market data,
>>> or the human genome, or the complete works of Shakespeare. It seems
>>> entirely conceivable that, by analyzing these circuits, we could make
>>> an easy fortune on Wall Street, or retrace evolution, or even generate
>>> Shakespeare's 38th play. For broadly speaking, that which we can
>>> compress
>>> we can understand, and that which we can understand we can predict....
>>> if we could solve the general case - if knowing something was tantamount
>>> to knowing the shortest efficient description of it - then we would be
>>> almost like gods."
>>>
>>> This doesn't seem right to me, the notion that an NP solving oracle
>>> would be able to find the shortest efficient description of any data.
>>> That would require a more complex oracle, one that would be able to
>>> solve the halting problem.
>>>
>>> I think Aaronson is blurring the lines between finding the smallest
>>> Boolean circuit and finding the smallest efficient description. Maybe
>>> finding the smallest Boolean circuit is in NP; it's not obvious to me
>>> but it's been a while since I've studied this stuff. But even if we
>>> could find such a circuit I'm doubtful that all the rest of Aaronson's
>>> scenario follows.
>>>
>>> Hal Finney
Received on Mon Jul 25 2005 - 21:24:52 PDT