PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

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

Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
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.
Wydawca
Rocznik
Strony
187--207
Opis fizyczny
Bibliogr. 26 poz., rys.
Twórcy
autor
  • Department of Mathematics, Faculty of Arts and Sciences Eastern Mediterranean University Famagusta, North Cyprus, Mersin-10, Turkey
autor
  • 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-492a2695-662a-4fb7-b3e1-d5dfa2a3de43
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.