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
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). https://doi.org/10.1117/1.2799086

Back to Top