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


SHARE
RELATED CONTENT

Correlation-based optical numeric processors
Proceedings of SPIE (November 30 1991)
Noise as a way of representing clutter experimental and...
Proceedings of SPIE (December 26 1996)
Single-stage optical numeric symbolic substitution
Proceedings of SPIE (July 11 1993)

Back to Top