Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the third annual ACM symposium on Theory of computing, Shaker Heights, Ohio, United States, pp. 151–158. ACM, New York (1971)
Rintanen, J., Heljanko, K., Niemel, I.: Planning as satisfiability: parallel plans and algorithms for plan search. Artificial Intelligence 170(12-13), 1031–1080 (2006)
Amla, N., Du, X., Kuehlmann, A., Kurshan, R.P., McMillan, K.L.: An analysis of SAT-Based model checking techniques in an industrial environment. In: Borrione, D., Paul, W. (eds.) CHARME 2005. LNCS, vol. 3725, pp. 254–268. Springer, Heidelberg (2005)
Oltean, M., Muntean, O.: Exact cover with light. 0708.1962 (August 2007). In: New Generation Computing, vol. 26(4), pp. 327–344. Springer, Heidelberg (2008)
Oltean, M.: Solving the hamiltonian path problem with a light-based computer. Natural Computing: an international journal 7(1), 57–70 (2008)
Oltean, M., Muntean, O.: Solving the subset-sum problem with a light-based device. Natural Computing: an international journal 8(2), 321–331 (2009)
Haist, T., Osten, W.: An optical solution for the traveling salesman problem. Optics Express 15(16), 10473–10482 (2007) PMID: 19547400.
Dolev, S., Fitoussi, H.: The traveling beams optical solutions for bounded NP-Complete problems. In: Crescenzi, P., Prencipe, G., Pucci, G. (eds.) FUN 2007. LNCS, vol. 4475, pp. 120–134. Springer, Heidelberg (2007)
Shaked, N.T., Tabib, T., Simon, G., Messika, S., Dolev, S., Rosen, J.: Optical binary-matrix synthesis for solving bounded NP-complete combinatorial problems. Optical Engineering 46(10), 108–201 (2007)
Shaked, N.T., Messika, S., Dolev, S., Rosen, J.: Optical solution for bounded NP-complete problems. Applied Optics 46(5), 711–724 (2007) PMID: 17279159.
Woods, D., Gibson, J.: Lower bounds on the computational power of an optical model of computation. Natural Computing 7(1), 95–108 (2008)
Woods, D., Naughton, T.J.: An optical model of computation. Theor. Comput. Sci. 334(1-3), 227–258 (2005)
Woods, D., Naughton, T.: Parallel and sequential optical computing. In: Dolev, S., Haist, T., Oltean, M. (eds.) OSC 2008. LNCS, vol. 5172, pp. 70–86. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goliaei, S., Jalili, S. (2009). An Optical Wavelength-Based Solution to the 3-SAT Problem. In: Dolev, S., Oltean, M. (eds) Optical SuperComputing. OSC 2009. Lecture Notes in Computer Science, vol 5882. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10442-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-10442-8_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10441-1
Online ISBN: 978-3-642-10442-8
eBook Packages: Computer ScienceComputer Science (R0)