OSA's Digital Library

Applied Optics

Applied Optics

APPLICATIONS-CENTERED RESEARCH IN OPTICS

  • Editor: James C. Wyant
  • Vol. 46, Iss. 5 — Feb. 10, 2007
  • pp: 711–724

Optical solution for bounded NP-complete problems

Natan T. Shaked, Stephane Messika, Shlomi Dolev, and Joseph Rosen  »View Author Affiliations


Applied Optics, Vol. 46, Issue 5, pp. 711-724 (2007)
http://dx.doi.org/10.1364/AO.46.000711


View Full Text Article

Enhanced HTML    Acrobat PDF (3017 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

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

You do not have subscription access to this journal. Citation lists with outbound citation links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Log in to access OSA Member Subscription

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Log in to access OSA Member Subscription

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Log in to access OSA Member Subscription

You do not have subscription access to this journal. Article level metrics are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Log in to access OSA Member Subscription

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited