Re: Time Machines, FTL, and P=NP

Harry Erwin <herwin@[EMAIL PROTECTED]
> wrote:
> Aaronson's article in the March 2008 points out that a universe with
> time machines (and/or FTL) has PSPACE = P. Note that PSPACE is a
> superset of NP.

It'll depend on what sort of time travel you get, but generally you'll be 
able to perform infinite computation in finite time. The only reason this 
doesn't solve the Halting Problem is because you don't have infinite 
storage. It does let you solve the version of the Halting Problem extended

to real, space-limited hardware. This is technically in PSPACE but in a 
practical sense is unsolveable for any non-trivial hardware. The ability 
to build oracles, even limited oracles that assume finite storage, would 
change a lot.

-- 
Michael Ash
Rogue Amoeba Software