At 01:04 AM 2/5/99 -0600, John Kelsey wrote:
>>At 10:45 AM 2/1/99 -0700, [EMAIL PROTECTED] wrote:
>>>Suppose someone discovers a way to solve NP-complete
>>>problems with a quantum computer; should he publish?
>>>Granted, the quantum computers aren't big enough yet, but
>>>the prospects look bright for larger ones in the near
>>>future. It would break all classical cryptography.
>
>>If he's a Good Guy, yes. It not only would revolutionize
>>cryptography (sigh - back to the couriers with briefcases
>>handcuffed to their arms) but would also revolutionize whole
>>areas of mathematical practice - there are a _lot_ of
>>NP-hard problems with real-world applications.
>
>Yeah, I was thinking this, too. Does anyone know how large
>the impact of this would be? Like, would the costs of Fed
>Ex, UPS, etc., go down substantially, because the way they
>flew their delivery routes became so much more efficient?
Not really. In most real-world situations, you don't need to
actually solve the NP-complete problem. Reasonable analysis
techniques quickly get you within a few percent of optimal,
and that's good enough for FedEx, etc. Phone company
routing may improve, but probably not by that much either.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
