Not just the ultimate compression algorithm
Posted Jun 19, 2008 11:54 UTC (Thu) by emk
In reply to: Compression
Parent article: The Kernel Hacker's Bookshelf: Ultimate Physical Limits of Computation
Such a time machine also allows you to send bits back in time. Let's say you want to know whether the Cubs win the World Series sometime between now and 2107. Simply create a file named "yes-they-won.txt". If the Chicago Cubs win, access that file. Presto! Your "compression" algorithm can now be used to tell whether or not the victory occurred / will occur.
If you want to place bets, create 100 files named "2008", "2009", "2010", etc. Then, at the beginning of each year the Cubs win the World Series, max out your credit cards and stake your entire fortune on the Cubs winning.
But this turns out to be an amazing waste of your "compression" algorithm. As it turns out, once you can send bits back in time, you can build a negative time delay element, a circuit component that shifts its inputs back in time. This, in turn, allows you solve NP-complete problems in polynomial time, as described in the Moravec article I just linked.
And if NP is equal to P, then you've built something much more powerful than a quantum computer. Specifically, you can answer virtually any question you can ask, provided the correctness of that answer can be checked in polynomial time. And this, in turn, has further surprising consequences:
But another reason we believe P≠NP is that otherwise mathematical creativity could be automated! You'd simply ask your computer: "Is there a proof of the Riemann hypothesis with at most a million symbols?" And if there is such a proof, the computer will find it in some way dramatically faster than searching through every possibility. If P=NP, you wouldn't merely have solved one of the seven million-dollar problems from the Clay Math Institute -- presumably you could also solve the other six.
(See also the section titled "Linearity" in another of Scott Aaronson's lectures
, which links to a paper analyzing a number of related problems in physics.)
to post comments)