Re: Time Machines, FTL, and P=NP

On 20 veebr, 18:19, Michael Ash <m...@[EMAIL PROTECTED]
> wrote:
> Crown-Horned Snorkack <chornedsnork...@[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
>
As pointed out, this is an infinite loop.

> 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 it this way: go burgling, and report your time machine the code
not as soon as the key opens, but after you have escaped and not been
caught at all.

Of course, this runs into the problems if the guards are smart enough
to seize your time machine when catching you, and tell the time
machine that you were not caught...

> 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.
>
This one is a harder task.

The answer not yes/no (like testing a key) nor a number which can be
compared with stored largest number. The answer is your subjective
impression.

> 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.
>