Journal
AXIOMS
Volume 10, Issue 4, Pages -Publisher
MDPI
DOI: 10.3390/axioms10040327
Keywords
membrane computing; computational complexity theory; P vs; NP problem; evolutional communication; symport; antiport
Categories
Funding
- FEDER/Ministerio de Ciencia e Innovacion-Agencia Estatal de Investigacion/_Proyecto [TIN2017-89842-P]
- European Social Fund
- Junta de Andalucia
Ask authors/readers for more resources
A widely studied field in membrane computing is computational complexity theory, where adding syntactic or semantic ingredients to membrane systems can improve their problem-solving efficiency. This study successfully solved the SAT problem using evolutional symport/antiport rules and passive environmental participation in recognizer P systems.
A widely studied field in the framework of membrane computing is computational complexity theory. While some types of P systems are only capable of efficiently solving problems from the class P, adding one or more syntactic or semantic ingredients to these membrane systems can give them the ability to efficiently solve presumably intractable problems. These ingredients are called to form a frontier of efficiency, in the sense that passing from the first type of P systems to the second type leads to passing from non-efficiency to the presumed efficiency. In this work, a solution to the SAT problem, a well-known NP-complete problem, is obtained by means of a family of recognizer P systems with evolutional symport/antiport rules of length at most (2,1) and division rules where the environment plays a passive role; that is, P systems from (CDEC) over cap (2,1). This result is comparable to the one obtained in the tissue-like counterpart, and gives a glance of a parallelism and the non-evolutionary membrane systems with symport/antiport rules.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available