Share Email Print

Optical Engineering

Optical binary-matrix synthesis for solving bounded NP-complete combinatorial problems
Author(s): Natan Tzvi Shaked; Tal Tabib; Simon Gil; Stephane Messika; Shlomi Dolev; Joseph Rosen
Format Member Price Non-Member Price
PDF $20.00 $25.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

An optical method for synthesizing a binary matrix representing all feasible solutions of a bounded (input length restricted) NP-complete combinatorial problem is presented. After the preparation of this matrix, an optical matrix-vector multiplier can be used in order to multiply the synthesized binary matrix and a grayscale vector representing the weights of the problem. This yields the required solution vector. The synthesis of the binary matrix is based on an efficient algorithm that utilizes a small number of long-vector duplications. These duplications are performed optically by using an optical correlator. Simulations and experimental results are given.

Paper Details

Date Published: 1 October 2007
PDF: 11 pages
Opt. Eng. 46(10) 108201 doi: 10.1117/1.2799086
Published in: Optical Engineering Volume 46, Issue 10
Show Author Affiliations
Natan Tzvi Shaked, Ben-Gurion Univ. of the Negev (Israel)
Tal Tabib, Ben-Gurion Univ. of the Negev (Israel)
Simon Gil, Ben-Gurion Univ. of the Negev (Israel)
Stephane Messika
Shlomi Dolev, Ben-Gurion Univ. of the Negev (Israel)
Joseph Rosen, Ben-Gurion Univ. of the Negev (Israel)

© SPIE. Terms of Use
Back to Top