Slashdot stories can be listened to in audio form via an RSS feed, as read by our own robotic overlord.

 



Forgot your password?
typodupeerror

Slashdot videos: Now with more Slashdot!

  • View

  • Discuss

  • Share

We've improved Slashdot's video section; now you can view our video interviews, product close-ups and site visits with all the usual Slashdot options to comment, share, etc. No more walled garden! It's a work in progress -- we hope you'll check it out (Learn more about the recent updates).

×
Math

+ - An Optical Solution For an NP-Complete problem?->

Submitted by 6
6 (22657) writes "Tobias Haist and Wolfgang Osten have proposed a novel idea for solving the traveling salesman problem...

We introduce an optical method based on white light interferometry in order to solve the well-known NP-complete traveling salesman problem. To our knowledge it is the first time that a method for the reduction of non-polynomial time to quadratic time has been proposed. We will show that this achievement is limited by the number of available photons for solving the problem. It will turn out that this number of photons is proportional to NN for a traveling salesman problem with N cities and that for large numbers of cities the method in practice therefore is limited by the signal-to-noise ratio. The proposed method is meant purely as a gedankenexperiment."

Link to Original Source
This discussion was created for logged-in users only, but now has been archived. No new comments can be posted.

An Optical Solution For an NP-Complete problem?

Comments Filter:

Take your work seriously but never take yourself seriously; and do not take what happens either to yourself or your work seriously. -- Booth Tarkington

Working...