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
