The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules
Tissue P systems with evolutional communication (symport/antiport) rules are computational models inspired by biochemical systems consisting of multiple individuals living and cooperating in a certain environment, where objects can be modified when moving from one region to another region. In this w...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2018-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2018/3745210 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849690735976120320 |
|---|---|
| author | Linqiang Pan Bosheng Song Luis Valencia-Cabrera Mario J. Pérez-Jiménez |
| author_facet | Linqiang Pan Bosheng Song Luis Valencia-Cabrera Mario J. Pérez-Jiménez |
| author_sort | Linqiang Pan |
| collection | DOAJ |
| description | Tissue P systems with evolutional communication (symport/antiport) rules are computational models inspired by biochemical systems consisting of multiple individuals living and cooperating in a certain environment, where objects can be modified when moving from one region to another region. In this work, cell separation, inspired from membrane fission process, is introduced in the framework of tissue P systems with evolutional communication rules. The computational complexity of this kind of P systems is investigated. It is proved that only problems in class P can be efficiently solved by tissue P systems with cell separation with evolutional communication rules of length at most (n,1), for each natural number n≥1. In the case where that length is upper bounded by (3,2), a polynomial time solution to the SAT problem is provided, hence, assuming that P≠NP a new boundary between tractability and NP-hardness on the basis of the length of evolutional communication rules is provided. Finally, a new simulator for tissue P systems with evolutional communication rules is designed and is used to check the correctness of the solution to the SAT problem. |
| format | Article |
| id | doaj-art-eea08512a654445fb83f7c59921ea71d |
| institution | DOAJ |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2018-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-eea08512a654445fb83f7c59921ea71d2025-08-20T03:21:13ZengWileyComplexity1076-27871099-05262018-01-01201810.1155/2018/37452103745210The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport RulesLinqiang Pan0Bosheng Song1Luis Valencia-Cabrera2Mario J. Pérez-Jiménez3Key Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China, School of Automation, Huazhong University of Science and Technology, Wuhan, Hubei 430074, ChinaKey Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China, School of Automation, Huazhong University of Science and Technology, Wuhan, Hubei 430074, ChinaResearch Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, SpainResearch Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, SpainTissue P systems with evolutional communication (symport/antiport) rules are computational models inspired by biochemical systems consisting of multiple individuals living and cooperating in a certain environment, where objects can be modified when moving from one region to another region. In this work, cell separation, inspired from membrane fission process, is introduced in the framework of tissue P systems with evolutional communication rules. The computational complexity of this kind of P systems is investigated. It is proved that only problems in class P can be efficiently solved by tissue P systems with cell separation with evolutional communication rules of length at most (n,1), for each natural number n≥1. In the case where that length is upper bounded by (3,2), a polynomial time solution to the SAT problem is provided, hence, assuming that P≠NP a new boundary between tractability and NP-hardness on the basis of the length of evolutional communication rules is provided. Finally, a new simulator for tissue P systems with evolutional communication rules is designed and is used to check the correctness of the solution to the SAT problem.http://dx.doi.org/10.1155/2018/3745210 |
| spellingShingle | Linqiang Pan Bosheng Song Luis Valencia-Cabrera Mario J. Pérez-Jiménez The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules Complexity |
| title | The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules |
| title_full | The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules |
| title_fullStr | The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules |
| title_full_unstemmed | The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules |
| title_short | The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules |
| title_sort | computational complexity of tissue p systems with evolutional symport antiport rules |
| url | http://dx.doi.org/10.1155/2018/3745210 |
| work_keys_str_mv | AT linqiangpan thecomputationalcomplexityoftissuepsystemswithevolutionalsymportantiportrules AT boshengsong thecomputationalcomplexityoftissuepsystemswithevolutionalsymportantiportrules AT luisvalenciacabrera thecomputationalcomplexityoftissuepsystemswithevolutionalsymportantiportrules AT mariojperezjimenez thecomputationalcomplexityoftissuepsystemswithevolutionalsymportantiportrules AT linqiangpan computationalcomplexityoftissuepsystemswithevolutionalsymportantiportrules AT boshengsong computationalcomplexityoftissuepsystemswithevolutionalsymportantiportrules AT luisvalenciacabrera computationalcomplexityoftissuepsystemswithevolutionalsymportantiportrules AT mariojperezjimenez computationalcomplexityoftissuepsystemswithevolutionalsymportantiportrules |