The Computational Complexity of Tissue P Systems with Evolutional SymportAntiport Rules
Joint Authors
Valencia-Cabrera, Luis
Pérez-Jiménez, Mario J.
Song, Bosheng
Pan, L.
Source
Issue
Vol. 2018, Issue 2018 (31 Dec. 2018), pp.1-21, 21 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2018-04-23
Country of Publication
Egypt
No. of Pages
21
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Pan, L.& Song, Bosheng& Valencia-Cabrera, Luis& Pérez-Jiménez, Mario J.. 2018. The Computational Complexity of Tissue P Systems with Evolutional SymportAntiport Rules. Complexity،Vol. 2018, no. 2018, pp.1-21.
https://search.emarefa.net/detail/BIM-1133762
Modern Language Association (MLA)
Pan, L.…[et al.]. The Computational Complexity of Tissue P Systems with Evolutional SymportAntiport Rules. Complexity No. 2018 (2018), pp.1-21.
https://search.emarefa.net/detail/BIM-1133762
American Medical Association (AMA)
Pan, L.& Song, Bosheng& Valencia-Cabrera, Luis& Pérez-Jiménez, Mario J.. The Computational Complexity of Tissue P Systems with Evolutional SymportAntiport Rules. Complexity. 2018. Vol. 2018, no. 2018, pp.1-21.
https://search.emarefa.net/detail/BIM-1133762
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1133762