A Shift-free Characterization of NP within Interval-valued Computing

• Autorzy: Nagy B. , Vályi S.

Identyfikatory

DOI

10.3233/FI-2017-1581

• Języki publikacji: EN

Abstrakty

EN

Interval-valued computing is a new computing paradigm that is based on manipulations of interval-values. Interval-values are finite unions of intervals on the unit interval [0; 1) so this kind of computing can be considered as a continuous space machine like optical computing [25]. Based on the massive parallelism of this paradigm, various intractable problems can be solved efficiently, i.e., by polynomial number of steps. In this paper, the well-known complexity classes, NP and coNP are addressed. A specific subclass of polynomial size interval-valued computations is proven to characterize NP, that is, exactly languages with non-deterministically polynomial time complexity can be decided by interval-valued computations of this subclass. This specific subclass of interval-valued computations does not use any of the shift operators, moreover the product operator is used only in the starting section of the computation. Due to the fact that interval-valued computing is a deterministic model of computing, an analogue result can be established for the class coNP.

Słowa kluczowe

EN

complexity; coNP; deterministic computing; interval-valued computing; massive parallelism; new computing paradigms; NP; unconventional computing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 155, nr 1/2
• Strony: 187--207
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Nagy B.

• Department of Mathematics, Faculty of Arts and Sciences Eastern Mediterranean University Famagusta, North Cyprus, Mersin-10, Turkey

autor

Vályi S.

• Institute of Mathematics and Informatics, University of Nyíregyháza, Hungary

Bibliografia

• [1] Calude CS, Pǎun Gh. Computing with Cells and Atoms: An Introduction to Quantum, DNA and Membrane Computing, Taylor&Francis/Hemisphere, London, Bristol, PA, USA, 2001. ISBN:9780748408993.
• [2] Dolev S, Fitoussi H. Masking traveling beams: Optical solutions for NP-complete problems, trading space for time, Theoretical Computer Science, 2010;411(6):837–853. URL https://doi.org/10.1016/j.tcs.2009.06.030.
• [3] Gramß T, Bornholdt S, Groß M, Mitchell M, Pellizzari T. Non-Standard Computation: Molecular Computation – Cellular Automata – Evolutionary Algorithms – Quantum Computers,Wiley-VCH Verlag GmbH, 1998. ISBN-10:3527294279, 13:9783527294275.
• [4] Gutiérrez-Naranjo MA, Pérez-Jiménez MJ, Romero-Campero FJ. A uniform solution to SAT using membrane creation, Theoretical Computer Science 2007;371(1-2):54–61. URL https://doi.org/10.1016/j.tcs.2006.10.013.
• [5] Herendi T, Nagy B. Parallel Approach of Algorithms, Typotex, Budapest, 2014. ISBN-9789632793382.
• [6] Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Massachusetts, 1979. ISBN-81-7808-347-7.
• [7] Leporati A, Felloni S. Three “quantum” algorithms to solve 3-SAT, Theoretical Computer Science 2007;372(2-3):218–241. doi:10.1016/j.tcs.2006.11.026.
• [8] Manea F, Martín-Vide C, Mitrana V. Accepting networks of splicing processors: Complexity results, Theoretical Computer Science 2007;371(1-2):72–82. URL https://doi.org/10.1016/j.tcs.2006.10.015.
• [9] McKenzie P, Wagner KW. The complexity of membership problems for circuits over sets of natural numbers, Computational complexity 2007;16(3):211–244. doi:10.1007/s00037-007-0229-6.
• [10] Nagy B. A general fuzzy logic using intervals, HUCI 2005: 6th International Symposium of Hungarian Researchers on Computational Intelligence, Budapest, Hungary, 2005, pp. 613–624.
• [11] Nagy B. An interval-valued computing device. In: CiE 2005, Computability in Europe: New Computational Paradigms, Amsterdam, Netherlands, 2005, pp. 166–177.
• [12] Nagy B. Új Számítási Paradigmák: Bevezetés az Intervallum-értékű, a DNS-, a Membrán-és a Kvantumszámítógépek elméletébe (New Computing Paradigms: Introduction to Interval-Valued, DNA, Membrane and Quantum Computing, in Hungarian), Typotex, Budapest, 2014.
• [13] Nagy B, Major SR. Connection between interval-valued computing and cellular automata, CINTI 2013: 14th IEEE International Symposium on Computational Intelligence and Informatics, Budapest, Hungary, 2013, pp. 225–230. doi:10.1109/CINTI.2013.6705196.
• [14] Nagy B, Vályi S. Solving a PSPACE-complete problem by a linear interval-valued computation. In: CiE 2006, Computability in Europe: Logical Approaches to Computational Barriers, University of Wales, Swansea, UK, 2006, pp. 216–225.
• [15] Nagy B, Vályi S. Interval-valued computations and their connection with PSPACE. Theoretical Computer Science 2008;394(3):208–222. URL https://doi.org/10.1016/j.tcs.2007.12.013.
• [16] Nagy B, Vályi S. Prime factorization by interval-valued computing. Publicationes Mathematicae Debrecen 2011;79:539–551.
• [17] Nagy B, Vályi S. Computing discrete logarithm by interval-valued paradigm. Electronic Proceedings on Theoretical Computer Science, 2014;143:76–86. doi:10.4204/EPTCS.143.7.
• [18] Nagy B, Vályi S. A Characterization of NP within Interval-Valued Computing, MCU 2015: 7th Conference on Machines, Computations and Universality, LNCS 9288, 2015, p. 164–179. doi:10.1007/978-3-319-23111-2_11.
• [19] Papadimitriou C. Computational Complexity, Addison Wesley, 1994. ISBN-13:978-0201530827, 10:0201530821.
• [20] Pǎun, Gh., Rozenberg, G., Salomaa, A.: DNA Computing: New computing paradigms, Springer-Verlag, Berlin, 1998. doi:10.1007/978-3-662-03563-4.
• [21] Pǎun, Gh., Rozenberg, G., Salomaa, A. (Eds.): Handbook of Membrane Computing, Oxford University Press, 2010. ISBN:0199556679 9780199556670.
• [22] Rozenberg G, Bäck T, Kok JN (Eds.). Handbook of Natural Computing, 4 volumes, Springer, 2012. ISBN:978-3-540-92911-6, 978-3-540-92909-3.
• [23] Savage JE. Models of Computation: Exploring the Power of Computing, Addison-Wesley, 1998. ISBN-10:0201895390, 13:978-0201895391.
• [24] Sipser M. Introduction to the Theory of Computation, Cengage Learning, 2012. ISBN-10:113318779X, 13:978-1133187790.
• [25] Woods D, Naughton TJ. On the Computational Power of a Continuous-Space Optical Model of Computation, In: MCU 2001, Third International Conference on Machines, Computations, and Universality, Chisinau, Moldavia, 2001, pp. 288–299. doi:10.1007/3-540-45132-3_20.
• [26] Woods D, Naughton TJ. Optical computing, Applied Mathematics and Computation 2009;215(4):1417–1430. ISSN:0096-3003. URL https://doi.org/10.1016/j.amc.2009.04.061.