1 October 2007 Optical binary-matrix synthesis for solving bounded NP-complete combinatorial problems
Author Affiliations +
Optical Engineering, 46(10), 108201 (2007). doi:10.1117/1.2799086
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.
Natan Tzvi Shaked, Tal Tabib, Simon Gil, Stephane Messika, Shlomi Dolev, Joseph Rosen, "Optical binary-matrix synthesis for solving bounded NP-complete combinatorial problems," Optical Engineering 46(10), 108201 (1 October 2007). http://dx.doi.org/10.1117/1.2799086
JOURNAL ARTICLE
11 PAGES


SHARE
KEYWORDS
Binary data

Optical engineering

Spatial light modulators

Chemical elements

Detection and tracking algorithms

Optical filters

CCD cameras

Back to Top