2015
An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Separation
PEREZ-JIMENEZ, MJ and Petr SOSÍKBasic information
Original name
An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Separation
Authors
PEREZ-JIMENEZ, MJ and Petr SOSÍK
Edition
FUNDAMENTA INFORMATICAE, AMSTERDAM, IOS PRESS, 2015, 0169-2968
Other information
Language
English
Type of outcome
Article in a journal
Field of Study
10200 1.2 Computer and information sciences
Country of publisher
Netherlands
Confidentiality degree
is not subject to a state or trade secret
Impact factor
Impact factor: 0.658
Marked to be transferred to RIV
No
Organization unit
Faculty of Philosophy and Science in Opava
UT WoS
Keywords in English
Membrane Computing; Tissue P Systems; Cell Separation; Computational Complexity; SAT Problem
Tags
Tags
International impact, Reviewed
Links
ED1.1.00/02.0070, research and development project.
Changed: 19/3/2020 14:52, doc. Ing. Petr Sosík, Dr.
Abstract
In the original language
A membrane system (P system) is a distributed computing model inspired by information processes in living cells. P systems previously provided new characterizations of a variety of complexity classes and their borderlines. Specifically, in tissue-like membrane systems, cell separation rules have been considered joint with communication rules of the form symport/antiport. On the one hand, only tractable problems can be efficiently solved by using cell separation and communication rules with length at most 2. On the other hand, an efficient and uniform solution to the SAT problem by using cell separation and communication rules with length at most 8 has been recently given. In this paper we improve the previous result by showing that the SAT problem can be solved by a family of tissue P systems with cell separation in linear time, by using communication rules with length at most 3. Thus, in the framework of tissue P systems with cell separation, we provide an optimal tractability borderline: passing from length 2 to 3 amounts to passing from non-efficiency to efficiency, assuming that P not equal NP.