×

zbMATH — the first resource for mathematics

An optical solution for the set splitting problem. (English) Zbl 1425.68113
Summary: We describe here an optical device, based on time-delays, for solving the set splitting problem which is well-known NP-complete problem. The device has a graph-like structure and the light is traversing it from a start node to a destination node. All possible (potential) paths in the graph are generated and at the destination we will check which one satisfies completely the problem’s constrains.
MSC:
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R.S. Braich, N. Chelyapov, C. Johnson, P. Rothemund, L. Adleman, Solution of a 20-variable 3-SAT problem on a DNA computer , Science 296, 5567 (2002) 499-502. ⇒140, 141
[2] S. Dolev, H. Fitoussi, The traveling beams optical solutions for bounded NP- complete problems, Int. Conf. on Fun with Algorithms, FUN 2007, LNCS 4475, pp. 120-134, 2007. ⇒134 · Zbl 1201.68032
[3] M. R. Garey, D. S. Johnson, Computers and intractability: A guide to NP-Completeness, Freeman & Co, San Francisco, CA, 1979. ⇒134, 135 · Zbl 0411.68039
[4] S. Goliaei. S. Jalili, An optical wavelength-based solutionto the 3-SAT problem, Int. Workshop on Optical Supercomputing OSC 2009, LNCS 5882, pp. 77-85, Springer-Verlag Heidelberg, 2009. ⇒134
[5] S. Goliaei. S. Jalili, Optical graph 3-colorability, Int. Workshop on Optical Supercomputing, OSC 2010 LNCS 6748, pp. 16-22, Springer-Verlag Heidelberg, 2011. ⇒134
[6] S. Goliaei, M-H. Foroughman-Araabi, Lower bounds on the complexity of the wavelength-based machine, Int. Conference on Unconventional Computing and Natural Computation, UCNC 2012 LNCS 7445, pp. 94-105, Springer-Verlag Heidelberg, 2012. ⇒134 · Zbl 1374.68214
[7] S. Goliaei, S. Jalili, J. Salimi, Light-based solution for the dominating set prob- lem, Applied Optics 51,, 29 (2012) 6979-6983. ⇒134
[8] S. Goliaei, S. Jalili, An optical solution to the 3-SAT problem using wave-length based selectors, Int. Journal of Supercomputing 62, 2 (2012) 663-672. ⇒134
[9] S. Goliaei, S. Jalili, An optical polynomial time solution for the satisfiability problem, Int. Workshop on Optical Supercomputing, OSC 2012, LNCS 7715, pp. 15-24, Springer-Verlag Heidelberg, 2013. ⇒134
[10] S. Goliaei, M-H. Foroughman-Araabi, Light ray concentration reduces the complexity of the wavelength-based machine on PSPACE languages, Int. Conf. on Unconventional Computing and Natural Computation, UCNC 2013, LNCS 7956, pp. 90-101, Springer-Verlag Heidelberg, 2013. ⇒134 · Zbl 1381.68083
[11] S. Goliaei, M-H. Foroughman-Araabi, On the complexity of nonuniform wavelength-based machine, Natural Computing 13, 2 (2014) 269-283. ⇒134 · Zbl 1456.68052
[12] S. Goliaei, S. Jalili, Computation with optical sensitive sheets, Natural Comput- ing 14, 3 (2015) 437-450. ⇒134
[13] T. Haist, W. Osten, An optical solution for the traveling salesman problem, Opt. Express 15, 16 (2007) 10473-10482. ⇒134
[14] T. Haist, W Osten, An optical solution for the traveling salesman prob- lem:erratum, Opt. Express 15, 20 (2007) 12627-12627. ⇒134
[15] T. Haist, W. Osten, Ultrafast digital-optical arithmetic using wave-optical com- puting, Int. Workshop on Optical Supercomputing, OSC 2008, LNCS 5172, pp. 33-45, 2008. ⇒134
[16] T. Haist, W. Osten, Proposal for secure key distribution using classical optics, Int. Workshop on Optical Supercomputing, OSC 2009, LNCS 5882, pp. 99-101, 2009. ⇒134
[17] R. Hasan, S. Rahman, Computing a solution for the subset sum problem with a light based device, Int. Workshop on Optical Supercomputing, OSC 2009, LNCS 5882, pp. 70-76, 2009. ⇒134
[18] T. Head, Parallel computing by xeroxing on transparencies, Algorithmic Biopro- cesses, pp. 631-637, 2009. ⇒134
[19] T. Head, Computing transparently: the independent sets in a graph, Natural Computing, 10, 1 (2011) 129-138. ⇒134 · Zbl 1226.05194
[20] K. Nitta, N. Katsuta, O. Matoba, Improvement of a system for prime factoriza- tion based on optical interferometer, Int. Workshop on Optical Supercomputing, OSC 2009, LNCS 5882, pp. 124-129, 2009. ⇒134
[21] K. Nitta, N. Katsuta, O. Matoba, A method for modulo operation by use of spatial parallelism, Int. Workshop on Optical Supercomputing, OSC 2008, LNCS 5172, pp. 98-103, 2008. ⇒134
[22] O. Muntean, Optical Solutions for NP-complete problems (graduation thesis), Faculty of Mathematics and Computer Science, Babeş-Bolyai University, Cluj- Napoca, Romania (defended 3rd of July, 2007). )134
[23] O. Muntean, M. Oltean, Using light for solving the unbounded subset-sum prob-lem, Int. J. of Innovative Computing, Information and Control 5, 8 (2009) 2159{2167. )134} · Zbl 1188.68141
[24] O. Muntean, M. Oltean, Deciding whether a linear Diophantine equation has so-lutions by using a light-based device, J. Optoelectronics and Advanced Materials,11, 11 (2009) 1728{1734. )134}
[25] M. Oltean, A light-based device for solving the Hamiltonian path problem, Int.Conf. on Unconventional Computation, UC 2006, LNCS 4135, Springer-Verlag,pp. 217{227, 2006. )134, 135, 140} · Zbl 1126.68433
[26] M. Oltean M., O. Muntean, Solving the subset-sum problem with a light-baseddevice, Natural Computing, 8, 2 (2009) 321{331. )134, 135, 136, 137, 139, 141} · Zbl 1188.68141
[27] M. Oltean, O. Muntean, Exact cover with light, New Generation Computingn,26, 4 (2008) 327{344. )134} · Zbl 1191.68127
[28] M. Oltean, O. Muntean, An optical solution for the SAT problem, Int. Workshopon Optical Supercomputing, OSC 2010, LNCS 6748, pp. 53{62, 2010. )134}
[29] N. T. Shaked, S. Messika, S. Dolev, J. Rosen, Optical solution for bounded NP-complete problems, Applied Optics 46, 5 (2007) 711{724. )134}
[30] N. Shakeri, S. Jalili, V. Ahmadi, A. R. Zali, S. Goliaei, A 2-dimensional op-tical architecture for solving Hamiltonian path problem based on micro ringresonators, Optics & Laser Technology, 65, 1 (2015) 56{65. )134, 140}
[31] *** Set splitting problem on Wikipedia, https://en.wikipedia.org/wiki/Set_splitting_problem, last accessed on 2017.10.09 )135
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.