Slashdot Mirror

← Back to Stories (view on slashdot.org)

Optical Solution For an NP-Complete Problem?

Posted by kdawson on from the too-bad-about-the-noise dept.

6 writes to let us know that two optical researchers have proposed, as a thought experiment, a novel idea for solving the traveling salesman problem. From the abstract: 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."

5 of 232 comments (clear)

  1. Parallel computing by iamacat · · Score: 4, Insightful

    So effectively each photon is a CPU core and the running time is reduced by massive parallel computing rather than inherent reduction in complexity, which is (N^N)*(N^2).

    1. Re:Parallel computing by bateleur · · Score: 4, Insightful

      The ironic thing being that this is precisely why we care about whether NP=P or not. Because without a polynomial time algorithm, large problems remain intractable even after you massively parallelize them!

  2. Still an exponential algorithm by n01 · · Score: 4, Insightful

    The paper says that the path the photons have to travel for a TSP with N cities is
    N*d + a*(2^N+1)
    Since the speed of light is finite, the algorithm still takes O(2^N) i.e. exponential time to complete.

  3. exponential photons == not practical by frankie · · Score: 4, Insightful

    To solve a 50-point traveling salesman using their algorithm would require on the order of 50^50 photons (about 10^85). For comparison, the Sun emits roughly 10^45 photons per second. Somehow I don't think their system is going to scale very well.

  4. Re:Not the first time this has been proposed by mdmkolbe · · Score: 4, Insightful

    From the last line of the abstract, "The proposed method is meant purely as a gedankenexperiment."

    Translation, "We know this wont ever work; we just think it's cool."

    Even better is in section five where they cite Wikipedia for the definition of a quantum computer.