Top

Natural Computing

06-04-2024

Solving subset sum and SAT problems by reaction systems

Authors: Bogdan Aman, Gabriel Ciobanu

Published in: Natural Computing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We study the efficiency of the reaction systems in solving NP-complete problems. Due to the fact that standard reaction systems are qualitative, in order to accomplish our aim, in this paper we consider communicating reaction systems with direct communication extended with duration for resources and a mutual exclusion relation between reactions forbidding two reactions to be used in the same step, in parallel. We show that these systems, working in a non-deterministic way, are powerful enough to provide polynomial-time solutions to the subset sum and SAT problems. We consider a semi-uniform approach by constructing a system for each instance of the subset sum and SAT problems and embedding the parameters into the constructed systems.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Alhazov A, Aman B, Freund R, Ivanov S (2016) Simulating R systems by P systems. In: Leporati A, Rozenberg G, Salomaa A, Zandron C (eds) 17th international conference on membrane computing, CMC 2016, Revised Selected Papers, Lecture Notes in Computer Science, vol 10105. Springer, pp 51–66, https://doi.org/10.1007/978-3-319-54072-6_4

Aman B (2023) Solving subset sum by spiking neural P systems with astrocytes producing calcium. Nat Comput 22(1):3–12. https://doi.org/10.1007/s11047-022-09900-7MathSciNetCrossRef

Aman B, Ciobanu G (2008) Describing the immune system using enhanced mobile membranes. Electron Notes Theor Comput Sci 194(3):5–18. https://doi.org/10.1016/j.entcs.2007.12.003CrossRef

Aman B, Ciobanu G (2009) Turing completeness using three mobile membranes. In: Calude CS, Costa JF, Dershowitz N, Freire E, Rozenberg G (eds) Unconventional computation, 8th international conference, UC 2009, Ponta Delgada, Azores, Portugal, September 7-11, 2009. Proceedings, Lecture Notes in Computer Science, vol 5715. Springer, pp 42–55, https://doi.org/10.1007/978-3-642-03745-0_12

Aman B, Ciobanu G (2011a) Mobility in process calculi and natural computing. Natural computing series, Springer, https://doi.org/10.1007/978-3-642-24867-2

Aman B, Ciobanu G (2011) Solving a weak NP-complete problem in polynomial time by using mutual mobile membrane systems. Acta Inf 48(7–8):409–415. https://doi.org/10.1007/s00236-011-0144-9MathSciNetCrossRef

Aman B, Ciobanu G (2017a) Controlled reversibility in reaction systems. In: Gheorghe M, Rozenberg G, Salomaa A, Zandron C (eds) 18th International conference on membrane computing, CMC 2017, Revised Selected Papers, Lecture Notes in Computer Science, vol 10725. Springer, pp 40–53, https://doi.org/10.1007/978-3-319-73359-3_3

Aman B, Ciobanu G (2017) Efficiently solving the bin packing problem through bio-inspired mobility. Acta Inf 54(4):435–445. https://doi.org/10.1007/s00236-016-0264-3MathSciNetCrossRef

Aman B, Ciobanu G (2020) Mutual exclusion and reversibility in reaction systems. J Membrane Comput 2(3):171–178. https://doi.org/10.1007/s41965-020-00043-1MathSciNetCrossRef

Azimi S, Iancu B, Petre I (2014) Reaction system models for the heat shock response. Fund Inf 131(3–4):299–312. https://doi.org/10.3233/FI-2014-1016MathSciNetCrossRef

Bagossy A, Gy Vaszil (2020) Simulating reversible computation with reaction systems. J Membrane Comput 2(3):179–193. https://doi.org/10.1007/s41965-020-00049-9MathSciNetCrossRef

Barbuti R, Gori R, Levi F, Milazzo P (2018) Generalized contexts for reaction systems: definition and study of dynamic causalities. Acta Inf 55(3):227–267. https://doi.org/10.1007/s00236-017-0296-3MathSciNetCrossRef

Bottoni P, Labella A, Rozenberg G (2019) Reaction systems with influence on environment. J Membrane Comput 1(1):3–19. https://doi.org/10.1007/s41965-018-00005-8MathSciNetCrossRef

Bottoni P, Labella A, Rozenberg G (2020) Networks of reaction systems. Int J Found Comput Sci 31(1):53–71. https://doi.org/10.1142/S0129054120400043MathSciNetCrossRef

Brijder R, Ehrenfeucht A, Main MG, Rozenberg G (2011) A tour of reaction systems. Int J Found Comput Sci 22(7):1499–1517. https://doi.org/10.1142/S0129054111008842MathSciNetCrossRef

Brijder R, Ehrenfeucht A, Rozenberg G (2011b) Reaction systems with duration. In: Kelemen J, Kelemenová A (eds) Computation, cooperation, and life–essays dedicated to gheorghe Păun on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, vol 6610. Springer, pp 191–202, https://doi.org/10.1007/978-3-642-20000-7_16

Brodo L, Bruni R, Falaschi M, Gori R, Levi F, Milazzo P (2023) Quantitative extensions of reaction systems based on SOS semantics. Neural Comput Appl 35(9):6335–6359. https://doi.org/10.1007/S00521-022-07935-6CrossRef

Ciobanu G (2010) Semantics of P systems. In: Păun G, Rozenberg G, Salomaa A (eds) The Oxford Handbook of Membrane Computing. Oxford University Press Inc, USA, pp 413–436

Ciobanu G, Todoran EN (2017) Denotational semantics of membrane systems by using complete metric spaces. Theor Comput Sci 701:85–108. https://doi.org/10.1016/j.tcs.2017.08.022MathSciNetCrossRef

Ciobanu G, Pérez-Jiménez MJ, Păun G (2006) Applications of membrane computing. Natural Computing Series, Springer, https://doi.org/10.1007/3-540-29937-8

Corolli L, Maj C, Marini F, Besozzi D, Mauri G (2012) An excursion in reaction systems: from computer science to biology. Theor Comput Sci 454:95–108. https://doi.org/10.1016/j.tcs.2012.04.003MathSciNetCrossRef

Csuhaj-Varjú E, Sethy PK (2020) Communicating reaction systems with direct communication. In: Freund R, Ishdorj T, Rozenberg G, Salomaa A, Zandron C (eds) 21st international conference on membrane computing, CMC 2020, Virtual Event, Revised Selected Papers, Lecture Notes in Computer Science, vol 12687. Springer, pp 17–30, https://doi.org/10.1007/978-3-030-77102-7_2

Csuhaj-Varjú E, Sethy PK (2021) Properties of communicating reaction systems. In: Brejová B, Ciencialová L, Holena M, Mráz F, Pardubská D, Plátek M, Vinar T (eds) 21st conference information technologies - applications and theory (ITAT 2021), CEUR workshop proceedings, vol 2962. CEUR-WS.org, pp 217–221

Ehrenfeucht A, Rozenberg G (2007) Reaction systems. Fund Inf 75(1–4):263–280

Ehrenfeucht A, Rozenberg G (2009) Introducing time in reaction systems. Theor Comput Sci 410(4–5):310–322. https://doi.org/10.1016/j.tcs.2008.09.043MathSciNetCrossRef

Ehrenfeucht A, Rozenberg G (2014) Zoom structures and reaction systems yield exploration systems. Int J Found Comput Sci 25(3):275–306. https://doi.org/10.1142/S0129054114500142MathSciNetCrossRef

Ehrenfeucht A, Main MG, Rozenberg G (2011) Functions defined by reaction systems. Int J Found Comput Sci 22(1):167–178. https://doi.org/10.1142/S0129054111007927MathSciNetCrossRef

Frisco P, Gheorghe M, Pérez-Jiménez MJ (2014) Applications of membrane computing in systems and synthetic biology. Emerg Complex Comput Springer. https://doi.org/10.1007/978-3-319-03191-0CrossRef

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. A series of books in the mathematical sciences, W. H. Freeman and Company, New York

Kleijn J, Koutny M, Rozenberg G (2020) Plug-in context providers for reaction systems. Theor Comput Sci 834:26–42. https://doi.org/10.1016/j.tcs.2020.01.033MathSciNetCrossRef

Leporati A, Mauri G, Zandron C, Păun Gh, Pérez-Jiménez MJ (2009) Uniform solutions to SAT and subset sum by spiking neural P systems. Natural Comput 8(4):681–702. https://doi.org/10.1007/s11047-008-9091-yMathSciNetCrossRef

Meski A, Koutny M, Penczek W (2016) Towards quantitative verification of reaction systems. In: Amos M, Condon A (eds) 15th International conference on unconventional computation and natural computation, UCNC 2016, Lecture Notes in Computer Science, vol 9726. Springer, pp 142–154, https://doi.org/10.1007/978-3-319-41312-9_12

Okubo F, Yokomori T (2016) The computational capability of chemical reaction automata. Natural Comput 15(2):215–224. https://doi.org/10.1007/s11047-015-9504-7MathSciNetCrossRef

Pan L, Ishdorj T (2004) P systems with active membranes and separation rules. J Univ Comput Sci 10(5):630–649. https://doi.org/10.3217/JUCS-010-05-0630MathSciNetCrossRef

Pan L, Păun Gh, Zhang G, Neri F (2017) Spiking neural P systems with communication on request. Int J Neural Syst 27(8):1750042–1750042. https://doi.org/10.1142/S0129065717500423CrossRef

Păun Gh (2000) Computing with membranes. J Comput Syst Sci 61(1):108–143. https://doi.org/10.1006/jcss.1999.1693MathSciNetCrossRef

Păun Gh (2001) P systems with active membranes: attacking NP-complete problems. J Autom Lang Comb 6(1):75–90. https://doi.org/10.25596/jalc-2001-075MathSciNetCrossRef

Păun Gh (2002) Membrane computing: an introduction. Natural computing series, Springer, https://doi.org/10.1007/978-3-642-56196-2

Păun Gh, Pérez-Jiménez MJ (2012) Towards bridging two cell-inspired models: P systems and R systems. Theor Comput Sci 429:258–264. https://doi.org/10.1016/j.tcs.2011.12.046MathSciNetCrossRef

Păun Gh, Rozenberg G, Salomaa A (2010) The Oxford Handbook of Membrane Computing. Oxford University Press Inc, USACrossRef

Pérez-Jiménez MJ, Riscos-Núñez A, Romero-Jiménez Á, Woods D (2010) Complexity: membrane division, membrane creation. The Oxford handbook of membrane computing, pp 302–336

Shang Z, Verlan S, Petre I, Zhang G (2019) Reaction systems and synchronous digital circuits. Molecules. https://doi.org/10.3390/molecules24101961CrossRef

Wu T, Bîlbîe F, Păun A, Pan L, Neri F (2018) Simplified and yet Turing universal spiking neural P systems with communication on request. Int J Neural Syst 28(8):1850013–1850013. https://doi.org/10.1142/S0129065718500132CrossRef

Zhang G, Rong H, Neri F, Pérez-Jiménez MJ (2014) An optimization spiking neural P system for approximately solving combinatorial optimization problems. Int J Neural Syst. https://doi.org/10.1142/S0129065714400061CrossRef

Zhang G, Pérez-Jiménez MJ, Gheorghe M (2017) Real-life applications with membrane computing. emergence, complexity and computation, Springer, https://doi.org/10.1007/978-3-319-55989-6

Zhang G, Rong H, Paul P, He Y, Neri F, Pérez-Jiménez MJ (2021) A complete arithmetic calculator constructed from spiking neural P systems and its application to information fusion. Int J Neural Syst. https://doi.org/10.1142/S0129065720500550CrossRef

Zhu M, Yang Q, Dong J, Zhang G, Gou X, Hong H, Paul P, Neri F (2021) An adaptive optimization spiking neural P system for binary problems. Int J Neural Syst. https://doi.org/10.1142/S0129065720500549CrossRef

Title: Solving subset sum and SAT problems by reaction systems
Authors: Bogdan Aman
Gabriel Ciobanu
Publication date: 06-04-2024
Publisher: Springer Netherlands
Published in: Natural Computing
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-024-09972-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner