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 - 15:40:22 PDT