Solving Minimum Hitting Set Problem and Generalized Exact Cover Problem with Light Based Devices
Masud Hasan, Shabab Hossain, Md. Mahmudur Rahman and M. Sohel Rahman
We suggest a new way for solving the exact cover and the minimum hitting set problems using massive parallelism of light. The idea is to build an optical device that will generate all possible solution sets and then to select the correct one among those sets. The device has a graph like structure. There are several nodes connected by arcs (optical fibers). The light ray passing through an arc is delayed by some predefined time represented by the number assigned to the arc. The arcs are connected in such a way that the existence of a solution is represented by the arrival of a light signal at the destination at a predefined time.
Keywords: light based device, optical computing, NP-Complete problems