Tuning Frontiers of Efficiency in Tissue P Systems with Evolutional Communication Rules
Over the last few years, a new methodology to address the P versus NP problem has been developed, based on searching for borderlines between the nonefficiency of computing models (only problems in class P can be solved in polynomial time) and the presumed efficiency (ability to solve NP-complete pro...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2021/7120840 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850210960583688192 |
|---|---|
| author | David Orellana-Martín Luis Valencia-Cabrera Bosheng Song Linqiang Pan Mario J. Pérez-Jiménez |
| author_facet | David Orellana-Martín Luis Valencia-Cabrera Bosheng Song Linqiang Pan Mario J. Pérez-Jiménez |
| author_sort | David Orellana-Martín |
| collection | DOAJ |
| description | Over the last few years, a new methodology to address the P versus NP problem has been developed, based on searching for borderlines between the nonefficiency of computing models (only problems in class P can be solved in polynomial time) and the presumed efficiency (ability to solve NP-complete problems in polynomial time). These borderlines can be seen as frontiers of efficiency, which are crucial in this methodology. “Translating,” in some sense, an efficient solution in a presumably efficient model to an efficient solution in a nonefficient model would give an affirmative answer to problem P versus NP. In the framework of Membrane Computing, the key of this approach is to detect the syntactic or semantic ingredients that are needed to pass from a nonefficient class of membrane systems to a presumably efficient one. This paper deals with tissue P systems with communication rules of type symport/antiport allowing the evolution of the objects triggering the rules. In previous works, frontiers of efficiency were found in these kinds of membrane systems both with division rules and with separation rules. However, since they were not optimal, it is interesting to refine these frontiers. In this work, optimal frontiers of the efficiency are obtained in terms of the total number of objects involved in the communication rules used for that kind of membrane systems. These optimizations could be easier to translate, if possible, to efficient solutions in a nonefficient model. |
| format | Article |
| id | doaj-art-8df1010f22274a0dad7c2dc22ed80d8d |
| institution | OA Journals |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2021-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-8df1010f22274a0dad7c2dc22ed80d8d2025-08-20T02:09:40ZengWileyComplexity1076-27871099-05262021-01-01202110.1155/2021/71208407120840Tuning Frontiers of Efficiency in Tissue P Systems with Evolutional Communication RulesDavid Orellana-Martín0Luis Valencia-Cabrera1Bosheng Song2Linqiang Pan3Mario J. Pérez-Jiménez4Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, SpainResearch Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, SpainCollege of Information Science and Engineering, Hunan University, Changsha 410082, ChinaKey Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China, Institute of Artificial Intelligence, School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, ChinaResearch Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, SpainOver the last few years, a new methodology to address the P versus NP problem has been developed, based on searching for borderlines between the nonefficiency of computing models (only problems in class P can be solved in polynomial time) and the presumed efficiency (ability to solve NP-complete problems in polynomial time). These borderlines can be seen as frontiers of efficiency, which are crucial in this methodology. “Translating,” in some sense, an efficient solution in a presumably efficient model to an efficient solution in a nonefficient model would give an affirmative answer to problem P versus NP. In the framework of Membrane Computing, the key of this approach is to detect the syntactic or semantic ingredients that are needed to pass from a nonefficient class of membrane systems to a presumably efficient one. This paper deals with tissue P systems with communication rules of type symport/antiport allowing the evolution of the objects triggering the rules. In previous works, frontiers of efficiency were found in these kinds of membrane systems both with division rules and with separation rules. However, since they were not optimal, it is interesting to refine these frontiers. In this work, optimal frontiers of the efficiency are obtained in terms of the total number of objects involved in the communication rules used for that kind of membrane systems. These optimizations could be easier to translate, if possible, to efficient solutions in a nonefficient model.http://dx.doi.org/10.1155/2021/7120840 |
| spellingShingle | David Orellana-Martín Luis Valencia-Cabrera Bosheng Song Linqiang Pan Mario J. Pérez-Jiménez Tuning Frontiers of Efficiency in Tissue P Systems with Evolutional Communication Rules Complexity |
| title | Tuning Frontiers of Efficiency in Tissue P Systems with Evolutional Communication Rules |
| title_full | Tuning Frontiers of Efficiency in Tissue P Systems with Evolutional Communication Rules |
| title_fullStr | Tuning Frontiers of Efficiency in Tissue P Systems with Evolutional Communication Rules |
| title_full_unstemmed | Tuning Frontiers of Efficiency in Tissue P Systems with Evolutional Communication Rules |
| title_short | Tuning Frontiers of Efficiency in Tissue P Systems with Evolutional Communication Rules |
| title_sort | tuning frontiers of efficiency in tissue p systems with evolutional communication rules |
| url | http://dx.doi.org/10.1155/2021/7120840 |
| work_keys_str_mv | AT davidorellanamartin tuningfrontiersofefficiencyintissuepsystemswithevolutionalcommunicationrules AT luisvalenciacabrera tuningfrontiersofefficiencyintissuepsystemswithevolutionalcommunicationrules AT boshengsong tuningfrontiersofefficiencyintissuepsystemswithevolutionalcommunicationrules AT linqiangpan tuningfrontiersofefficiencyintissuepsystemswithevolutionalcommunicationrules AT mariojperezjimenez tuningfrontiersofefficiencyintissuepsystemswithevolutionalcommunicationrules |