Go Back   Molecular Biology Forum Life Science Forums > General Science Forums > Physics Forum
Register FAQ Members List Calendar Science Groups New! Arcade Search Today's Posts Mark Forums Read

Physics Forum Physics Forum. Discuss and ask physics questions, kinematics and other physics problems.


Algorithm for Solving NP hard problems

Algorithm for Solving NP hard problems - Physics Forum

Algorithm for Solving NP hard problems - Physics Forum. Discuss and ask physics questions, kinematics and other physics problems.


Reply
 
LinkBack Thread Tools Display Modes
  #1 (permalink)  
Old 10-03-2006, 01:36 AM
wschlanger@gmail.com
Guest
 
Posts: n/a
wschlanger@gmail.com RSS Feed
Default Algorithm for Solving NP hard problems



Here is an algorithm that can solve NP hard problems in polynomial time
provided it is possible to (1) split this universe into two universes
depending on the value of an observed random quantum number and (2) to
send information from the future back to the past, before the split was
made.

The theory is that (2) can be accomplished if and only if entanglement
itself can convey information. Most people believe this is impossible
but New Scientist has run an article about John Cramer who is working
on a double-split experiment that will attempt to send information
nonclassically using entangled laser-light. See New Scienstist for more
information.

The algorithm.
What kind of problem we attempt to solve? Breaking codes. Such as,
given 2^256 possible keys we wish to find a key that breakes the code.
We assume an "oracle" exists that can tell us whether or not a given
subset of key bits has a solution. More precisely it reports NO
SOLUTION for some choices of key bits.
For key bit 0, try =0, with bits 1..255 all DONT CARE. The oracle
reports NO SOLUTION or 1 OR MORE SOLUTIONS FOUND. Depending on the
result, choose that value for bit 0 of the key bit.
Then move on to bit 1 and try = 0 (for the first trial bit 1 was DONT
CARE along with all higher bits).

So you see how given an ORACLE that reports whether or not any
solutions exist for a given subset of key bits - e.g. given a list of
key bits, where each key bit is either 0, 1, or DONT CARE. The oracle
tries all possible values for DONT CARE key bits and reports the OR of
the result, where 0 is NON-SOLUTION and 1 is SOLUTION FOUND.

How to build the oracle. This requires time travel! The basic idea is
that this universe can be split into two baby universes by detecting a
quantum random number. Each parallel universe then has a value for the
key bit to process. How then to communicate back in time?

This is done as follows: there are two entangled pairs, one copy of
each pair is left in the past and the other is in the future.

According to New Scientist information can be sent from one entangled
particle to the other of the pair by passing it through a double-slit
experiment and selectively detecting the other as a particle or wave.
This forces the counterpart to be detected the same way, According to
New Scientist.

To delay to the future, slow the light down to a slow speed or, use 10
km of fiber optics as New Scientist says.

Now that you know how to split the universe in two and how to
communicate back in time, you next need to know how to OR the result of
two baby universes in the future and get the result in the past.

How to do it? I could draw you a nice diagram but it's hard with ASCII.

We have 3 laserbeams. One is a random number that we detect. This is 0
or 1. The other two beams are labeled beam 0 and beam 1 respectively.
If we detect "0", use beam 0. That means we are in the universe where
the random quantum number was 0. If 1, use beam 1. Both beams
communicate back in time.

The PAST receives both beams ORs the result. It thus gets the OR of two
future universes. It then has to complete the cycle by repeating the
experiment but ONLY FOR ONE of the two universes - for 0 or 1 depending
on the result, not both.

Critically, this allows 2^256 baby universes to be built with just 256
steps. This is known as a Quantum Oracle.

How an oracle can be used with a classical computer to break codes.

When used, the oracle generates a 256-bit number which a classical
computer tries to see if it breaks the code and then reports back to
the ORACLE. The oracle, in touch with 2^256 parallel unvierses which
can now communicate with eachother via time travel (see New
Scienstist), ORs all these parallel universe's outputs and thus the
classical computer is given a NO SOLUTION or SOLUTION for a subset of
the 2^256 keyspace.

Only 256 oracle interrogations are needed - 1 for each key bit - where
the remainder bits are as determined or DONT CARE.

Other uses of an Oracle. It can be used to as Deadman's switch across
time or parallel universes. These universes can send 1 bit to eachother
and can differ by as much as they can given 1 bit that creates them and
the short amount of time before they decohere.

Avoiding decoherence. This is a problem that limits the effectiveness
of an oracle. In our case we use many 'stages' each of which receives a
two signals from the future, ORs them, and sends it back into the past.

Anyone have any comments or care to speculate about whether this is a
valid interpretation of quantum mechanics? Is New Scienstist wrong? Am
I a wrong? The premise of my theory is that basically parallel worlds
can be leveraged now that time travel allows them to communicate with
eachother by sending a message to the past before the split was made
and saving the result for the future. Thus a SWITCH can be made between
two parallel universes.

Reply With Quote


Reply

Tags
algorithm , hard , problems , solving




Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
PLeasee help me with chemistry problems I am having a really hard time with a few... jackie Chemistry Forum 0 11-04-2008 04:19 AM
Chemistry is so hard.. please help with these problems!? Joon Chemistry Forum 0 10-28-2008 07:17 PM
problems with growing healthy Arabidopsis plants Monika Kuzma Arabidopsis and Plant Biology 1 02-19-2007 03:55 PM
Problems with growing healthy Arabidopsis plants - light intesity? Karl Lundy Arabidopsis and Plant Biology 0 02-07-2007 05:11 PM
[ANN] xmds-1.3-4 released! xmds solves complex problems simply and quickly Paul Cochrane Forum Chemie 0 06-21-2004 02:29 AM


All times are GMT. The time now is 03:09 PM.


Powered by vBulletin® Version 3.8.4
Copyright ©2000 - 2009, Jelsoft Enterprises Ltd.
Copyright 2005-2009 Molecular Station | All Rights Reserved