Hi Hal, Here is Scott's responce.

## Advertising

Onward! Stephen

`----- Original Message -----`

`From: "Scott Aaronson" <[EMAIL PROTECTED]>`

To: "Stephen Paul King" <[EMAIL PROTECTED]> 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 definedas the shortest program that outputs x after some fixed polynomial numberof 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 thesmallest circuit that on input i, outputs the ith bit of x. In all threecases, it's obvious that finding the smallest efficient description (ormore precisely, deciding whether there exists a description of complexity<=K) is in NP (though interestingly, these problems are not known to beNP-complete). By contrast, finding the smallest *computable* descriptionof x (or equivalently, finding its Kolmogorov complexity) is known to beequivalent to the halting problem. This is probably what Hal had in mind.So if P=NP, then we could find smallest efficient descriptions inpolynomial time. Whether those descriptions would give us new insightsinto the things being described is of course another issue, and herereasonable people will have differing intuitions.Hope that helps! --Scott Stephen Paul King wrote:Hi Scott, Any comments? Stephen ----- Original Message ----- From: ""Hal Finney"" <[EMAIL PROTECTED]> To: <everything-list@eskimo.com> 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 foundhere:http://www.scottaaronson.com/papers/npcomplete.pdfThat describes different proposals for physical mechanisms forefficientlysolving 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 generateShakespeare's 38th play. For broadly speaking, that which we cancompresswe 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