Re: Time Machines, FTL, and P=NP

Crown-Horned Snorkack <chornedsnorkack@[EMAIL PROTECTED]
> wrote:
> On 19 veebr, 23:10, Michael Ash <m...@[EMAIL PROTECTED]
> wrote:
>> Harry Erwin <her...@[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.
>>
> How much storage does an oracle need to be programmatically useful at
> all?
> 
> Suppose that you have a laptop which contains four wormholes - two in
> one corner and two in diagonally opposite corner. The wormholes are
> two wormhole pairs such that each wormhole pair individually does not
> contain a closed lightlike curve, but the two pairs combined do
> contain that.
> 
> As the diagonal of your laptop is about 30 cm, the oracle can receive
> signals send about 2 ns from future.
> 
> If you are able to write a program which receives the message, checks
> it against a condition and sends it into past all in 1 ns, then you
> can deliver your message 1 ns towards past every cycle. So, you can
> receive a message sent tomorrow some 86 billions and 400 milliards of
> cycles later.
> 
> But how would you write programs where you have oracle function at
> your disposal?

First, a warning, I haven't thought this through too thoroughly.

I don't see why you would have two wormhole pairs. Either you can send 
information into the past or you can't. It sounds like you're trying to 
fool nature by not having a single pair violate causality, but I don't 
think nature cares.

Second, the length of time you can send information into the past is 
irrelevant, as long as it exceeds the delay needed to relay things through

the wormhole again. If you can send things 2ns into the past but you need 
more time, then you just read from the future, write to the past, and do 
this as many times as necessary.

My point being, the configuration of the wormholes and their delays are 
irrelevant to the question. All you need to know is that you can 
communicate with the past.

You could do useful things with an oracle that didn't have a great deal of

storage. For example, cracking someone's RSA private key can be done on a 
machine with what would be consided a miniscule amount of storage by 
today's standards. But if you have a laptop with a wormhole you have 
access to the full storage of that machine. If it's connected to a network

you conceivably have access to the full storage of every machine you can 
convince to do your bidding. Since you can crack their passwords 
instantaneously, that's probably a lot.

As for how you would write them, it would be a simple transformation of 
the standard brute force loop:

    set x to first possibility
    loop:
        test x
        if x is good, return x
        else set x to the next possibility

With this basic algorithm you can solve anything which can be solved in a 
finite, bounded amount of storage. The trouble being that it takes too 
long on normal computers. If you're cracking somebody's 64-bit key and you

can test one billion keys per second (an excessively high number for 
today's hardware), it'll take you nearly 600 years to try them all, and 
nearly 300 years per try, on average, to find the key. And that's a 
*small* problem.

Since you don't want to wait around for 300 years, you use your wormhole 
and write this instead:

    get x from future-wormhole
    if no future information exists yet because it's the first run:
        set x to first possibility
    test x
    if x is good, return x
    else put x into wormhole

This will give you the answer in the amount of time it takes to test a 
single possibility. So, what can you do with this?

You can exhaustively test a program to make sure it doesn't crash on 
malformed input. You can feed it every input your computer has enough 
storage to hold. This won't rule out the possibility that you'll crash as 
soon as someone tries a slightly larger machine, but this kind of test 
coverage is vastly beyond what can be done today.

You can crack nearly any cryptography in use. The one exception being 
one-time pads, which are mathematically impossible to crack. But they're 
also extremely difficult to use. The modern structure of e-commerce and 
electronic security comes crashing down.

If you can get yourself in the time-travel loop (and why not?) then you 
can do things like brute-force keyless entry locks. Have the machine 
generate a number, you try it, you tell the machine if it worked, and if 
it didn't it sends the result back in time to try again. To the user this 
will look like the machine just magically comes up with the right number.

Apply this to the stock market... have the machine generate a stock symbol

as the market opens. You buy, then sell at the end of the day and tell the

machine how much money you now have. It runs through them all and settles 
on the one which gives the greatest return. To the user, it looks like the

machine just magically generates an awesome stock pick every day.

Having some more fun, imagine picking up women in a bar. Give the machine 
a list of women, and a database of pick-up lines. It feeds you one, and 
you report back how well it worked. This will look like the machine 
automatically points you to a woman and gives you a pick-up line which 
will sweep her off her feet.

Anyway, this is why scientists tend to assume that causality isn't 
violated in the universe, because if it is, all kinds of wacky crap 
happens.

-- 
Michael Ash
Rogue Amoeba Software