Computational complexity of tissue-like P systems

TitleComputational complexity of tissue-like P systems
Publication TypeJournal Papers
Year of Publication2010
AuthorsPan, L., & Pérez-Jiménez M. J.
Journal TitleJournal of Complexity
Date Published06/2010

Membrane systems, also called P systems, are biologically inspired theoretical models of distributed and parallel computing. This paper presents a new class of tissue-like P systems with cell separation, a feature which allows the generation of new workspace. We study the efficiency of the class of P systems and draw a conclusion that only tractable problems can be efficiently solved by using cell separation and communication rules with the length of at most 1. We further present an efficient (uniform) solution to SAT by using cell separation and communication rules with length at most 6. We conclude that a borderline between efficiency and non-efficiency exists in terms of the length of communication rules . We discuss future research topics and open problems.

KeywordsCell separation, Membrane computing, SAT, Tissue P Systems
Impact Factor



65/97 - Q3

ISSN Number0885-064X