Hi Hal,
Here is Scott's responce.
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 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"" <[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 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
