Abstract

The initialization time for setting up the experiment grows exponential with the number of cities. Therefore the overall time required to solve the problem is not quadratic but exponential.

©2007 Optical Society of America

In [1] we claimed that the proposed gedankenexperiment will find the global solution of a traveling salesman problem (TSP) in quadratic time. That means the time required to solve the TSP increases quadratic with the number of cities N. Our analysis was based on the number of measurements needed to determine the minimum path.

However we did not consider in this estimation that the first measurement only can start after the light has passed through the network. Since the delays for our chosen labeling scheme (Eq. 1 in [1]) were chosen to be ∼ 2i for city i we have an exponential increase of the overall path length for the light to travel. Therefore the initialization time required before the measurements really can start also increases exponentially with N. That is we have an increase in the initialization time of O(2N). This is considerably lower than the original cost of O(N!) ∼ O(NN) and from a practical point of view this initialization cost is low (due to the high speed of photons) for small problems. Nevertheless the chosen delay settings won’t lead to an overall reduction to quadratic time. This important fact has to be considered.

Additionally two readers pointed us to related publications that we want to reference here [2, 3, 4]. Most important is the work of M. Oltean who solved another NP-complete problem, the Hamiltonian path problem, by light [2, 3]. The core idea to use optical path lengths for coding/labeling the different problems is the same. Whereas we proposed an interferometric approach his technique is based on short pulses of light and incoherent detection. We appreciate his very interesting conference publication.

References and links

1. T. Haist and W. Osten, “An optical solution for the traveling salesman problem,” Opt. Express 15, 10473–10482 (2007) [CrossRef]   [PubMed]  

2. M. Oltean, “A light-based device for solving the Hamiltonian path problem,” in Lecture Notes in Computer Science 4135, 217–227, Springer (2006). [CrossRef]  

3. M. Oltean, “Solving the Hamiltonian path problem with a light-based computer,” Natural Computing, to appear in Vol. 6, Issue 4, 2007.

4. S. Dolev and H. Fitoussi, “The traveling beams optical solutions for bounded NP-Complete problems,” in Lecture Notes in Computer Science 4475, 120–134 (2007). [CrossRef]  

References

  • View by:

  1. T. Haist and W. Osten, “An optical solution for the traveling salesman problem,” Opt. Express 15, 10473–10482 (2007)
    [Crossref] [PubMed]
  2. M. Oltean, “A light-based device for solving the Hamiltonian path problem,” in Lecture Notes in Computer Science 4135, 217–227, Springer (2006).
    [Crossref]
  3. M. Oltean, “Solving the Hamiltonian path problem with a light-based computer,” Natural Computing, to appear in Vol. 6, Issue 4, 2007.
  4. S. Dolev and H. Fitoussi, “The traveling beams optical solutions for bounded NP-Complete problems,” in Lecture Notes in Computer Science 4475, 120–134 (2007).
    [Crossref]

2007 (2)

T. Haist and W. Osten, “An optical solution for the traveling salesman problem,” Opt. Express 15, 10473–10482 (2007)
[Crossref] [PubMed]

S. Dolev and H. Fitoussi, “The traveling beams optical solutions for bounded NP-Complete problems,” in Lecture Notes in Computer Science 4475, 120–134 (2007).
[Crossref]

2006 (1)

M. Oltean, “A light-based device for solving the Hamiltonian path problem,” in Lecture Notes in Computer Science 4135, 217–227, Springer (2006).
[Crossref]

Dolev, S.

S. Dolev and H. Fitoussi, “The traveling beams optical solutions for bounded NP-Complete problems,” in Lecture Notes in Computer Science 4475, 120–134 (2007).
[Crossref]

Fitoussi, H.

S. Dolev and H. Fitoussi, “The traveling beams optical solutions for bounded NP-Complete problems,” in Lecture Notes in Computer Science 4475, 120–134 (2007).
[Crossref]

Haist, T.

Oltean, M.

M. Oltean, “A light-based device for solving the Hamiltonian path problem,” in Lecture Notes in Computer Science 4135, 217–227, Springer (2006).
[Crossref]

M. Oltean, “Solving the Hamiltonian path problem with a light-based computer,” Natural Computing, to appear in Vol. 6, Issue 4, 2007.

Osten, W.

in Lecture Notes in Computer Science (2)

M. Oltean, “A light-based device for solving the Hamiltonian path problem,” in Lecture Notes in Computer Science 4135, 217–227, Springer (2006).
[Crossref]

S. Dolev and H. Fitoussi, “The traveling beams optical solutions for bounded NP-Complete problems,” in Lecture Notes in Computer Science 4475, 120–134 (2007).
[Crossref]

Opt. Express (1)

Other (1)

M. Oltean, “Solving the Hamiltonian path problem with a light-based computer,” Natural Computing, to appear in Vol. 6, Issue 4, 2007.

Cited By

Optica participates in Crossref's Cited-By Linking service. Citing articles from Optica Publishing Group journals and other participating publishers are listed here.

Alert me when this article is cited.


Metrics