An Optical Wavelength-Based Solution to the 3-SAT Problem

摘要

The NP-complete is a class of complexity including many real-world problems. Although many efforts made to find efficient solutions to NP-complete problems, no such a solution having polynomial complexity of used resources is found yet. Optical computing, as a branch of unconventional computing, provides new capabilities to solve NP-complete problems, using physical properties of light such as high parallelism nature of it. Some optical approaches to solve NP-complete problems in efficient manner are already provided, such as delaying the light motion, using optical masks, and using continuous space machines. In this paper, a new optical approach, using wide range of wavelengths exist in a light ray, is provided to solve the 3-SAT problem, a well-known NP-complete problem, in polynomial time. Each instance of the 3-SAT problem is a CNF-formula consisting m clauses be composed of n Boolean variables. The question is if there is a value-assignment to the Boolean variables which satisfies the formula or not. In the method provided in this paper, wavelengths presented in a light ray are considered as possible value-assignments to n variables. Basic optical devices such as prisms and mirrors are used to discriminate proper wavelengths which satisfy the CNF-formal. The method uses exponential size blocks to drop improper wavelengths, which may be constructed in a preprocessing phase and be used in many 3-SAT problem instances. After the preprocessing phase, the method takes O(m) time and exponential number of different wavelengths in light rays to find the answer of each 3-SAT problem instance.