## Optical solution for bounded NP-complete problems

Applied Optics, Vol. 46, Issue 5, pp. 711-724 (2007)

http://dx.doi.org/10.1364/AO.46.000711

Enhanced HTML Acrobat PDF (3017 KB)

### Abstract

We present a new optical method for solving bounded (input-length-restricted) NP-complete combinatorial problems. We have chosen to demonstrate the method with an NP-complete problem called the traveling salesman problem (TSP). The power of optics in this method is realized by using a fast matrix–vector multiplication between a binary matrix, representing all feasible TSP tours, and a gray-scale vector, representing the weights among the TSP cities. The multiplication is performed optically by using an optical correlator. To synthesize the initial binary matrix representing all feasible tours, an efficient algorithm is provided. Simulations and experimental results prove the validity of the new method.

© 2007 Optical Society of America

**OCIS Codes**

(070.2580) Fourier optics and signal processing : Paraxial wave optics

(070.4550) Fourier optics and signal processing : Correlators

(070.4560) Fourier optics and signal processing : Data processing by optical means

(200.0200) Optics in computing : Optics in computing

**ToC Category:**

Fourier Optics and Optical Signal Processing

**History**

Original Manuscript: March 15, 2006

Revised Manuscript: September 10, 2006

Manuscript Accepted: October 11, 2006

Published: January 25, 2007

**Citation**

Natan T. Shaked, Stephane Messika, Shlomi Dolev, and Joseph Rosen, "Optical solution for bounded NP-complete problems," Appl. Opt. **46**, 711-724 (2007)

http://www.opticsinfobase.org/ao/abstract.cfm?URI=ao-46-5-711

Sort: Year | Journal | Reset

### References

- D. Harel, Algorithmics: The Spirit of Computing (Addison-Wesley, 1987).
- G. Reinelt, The Traveling Salesman: Computational Solutions for TSP Applications (Springer-Verlag, 1994).
- J. E. Mitchell, "Branch-and-cut algorithms for combinatorial optimization problems," in Handbook of Applied Optimization (Oxford U. Press, 2002), pp. 65-77.
- K. A. Smith, "Neural networks for combinatorial optimization: a review of more than a decade of research," INFORMS J. Comput. 11, 15-34 (1999). [CrossRef]
- N. Collings, R. Sumi, K. J. Weible, B. Acklin, and W. Xue, "The use of optical hardware to find good solutions of the travelling salesman problem (TSP)," in Proc. SPIE 1806, 637-641 (1993). [CrossRef]
- D. Gutfreund, R. Shaltiel, and A. Ta-Shma, "If NP languages are hard on the worst-case then it is easy to find their hard instances," in Proceedings of the 20th Annual Conference on Computational Complexity (CCC) (2005). A long version of this paper is available on the web at http://www.cs.tau.ac.il/∼amnon/Papers/GST.cc05.journal.ps.
- J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, 1996), pp. 232-246.
- C. S. Weaver and J. W. Goodman, "A technique for optically convolving two functions," Appl. Opt. 5, 1248-1249 (1966). [CrossRef] [PubMed]
- A. VanderLugt, "Signal detection by complex spatial filtering," IEEE Trans. Inf. Theory IT-10, 139-145 (1964). [CrossRef]
- A. Homaifar, S. Guan, and G. E. Liepins, "Schema analysis of the traveling salesman problem using genetic algorithms," Complex Syst. 6, 183-217 (1992).
- D. G. Feitelson, Optical Computing: A Survey for Computer Scientists (MIT Press, 1988), pp. 148-163.
- M. A. Karim and A. A. S. Awwal, Optical Computing: An Introduction (Wiley, 1992), pp. 328-356.
- J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, 1996), pp. 282-289.
- A. D. McAulay, Optical Computer Architectures: The Application of Optical Concepts to Next Generation Computers (Wiley, 1991), pp. 289-299. [PubMed]
- S. Dolev, E. Korach, and G. Uzan, "A method for encryption and decryption of messages," PCT patent application WO 2006/001006 (5 January 2006).

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

### Figures

Fig. 1 |
Fig. 2 |
Fig. 3 |

Fig. 4 |
Fig. 5 |
Fig. 6 |

Fig. 7 |
Fig. 8 |
Fig. 9 |

Fig. 10 |
Fig. 11 |
Fig. 12 |

Fig. 13 |
||

« Previous Article | Next Article »

OSA is a member of CrossRef.