[RC5] More on Quantum Computing and Crypto
greg at hewgill.com
Fri May 21 00:30:22 EDT 1999
On Wed, May 19, 1999 at 09:22:42AM -0700, Adam Zilinskas wrote:
> If you could pull the web off the wall and label all end points and
> each strand, the longest distance between two points is found by holding
> each start/end point and carefully pulling them apart, if you
> break a strand but leave another path intact, you keep pulling. The moment
> you cannot pull any further without seperating the start and end point,
> that is the longest path.
I'm not sure this is a perfect analogy. Consider the following small fragment
of your conceptual spider web (please excuse the ascii art):
A B C D
That is, a taut connection between ABCD with a loop of web dangling from B and
C. While there is a wasy for this to break (at the short path between B and C)
to produce the longest connecting path, this will not be the case in general.
All other things being equal, there is a probability 1/3 that the short BC
connection will break first, rather than AB or CD. Of course, if AB or CD
breaks, then this web fragment becomes disconnected and is disqualified.
I think that at best, you could come up with a probability that the last
connected path is really the longest path.
If this were a quantum problem, then the web would not actually break until it
were observed. Unfortunately, I think tugging on the A and D ends of the web
above would count as observation because the elasticity of the remaining
connected web (if any) would exert a reactive force on the tugging, which could
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest
More information about the rc5