Optical binary-matrix synthesis for solving bounded NP-complete combinatorial problems Academic Article uri icon

abstract

  • An optical method for synthesizing a binary matrix represent- ing 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 represent- ing 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

publication date

  • January 1, 2007