Masking traveling beams: Optical solutions for NP-complete problems, trading space for time

Two architectures for optical processors designed to solve instances of NP-Complete problems, trading space for time, are suggested. The first approach mimics the traveling salesman by an exponential number of traveling beams, that simultaneously examine the different possible paths. The other approach uses a pre-processing stage in which O(n2) masks consisting of an exponential number of locations, are constructed; each representing a different edge in the graph. The choice and combination of the appropriate (small) subset of these masks yields the solution. The solution is rejected in cases where the combination of these masks completely blocks the light and accepted otherwise. We present detailed designs for basic primitives of the optical processor. We propose designs for solving instances of Hamiltonian path, Traveling Salesman, Clique, Independent Set, Vertex Cover, Partition, 3-SAT, 3D-matching, and the Permanent.