2015
An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Separation
PEREZ-JIMENEZ, MJ a Petr SOSÍKZákladní údaje
Originální název
An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Separation
Autoři
PEREZ-JIMENEZ, MJ a Petr SOSÍK
Vydání
FUNDAMENTA INFORMATICAE, AMSTERDAM, IOS PRESS, 2015, 0169-2968
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10200 1.2 Computer and information sciences
Stát vydavatele
Nizozemské království
Utajení
není předmětem státního či obchodního tajemství
Impakt faktor
Impact factor: 0.658
Označené pro přenos do RIV
Ne
Organizační jednotka
Filozoficko-přírodovědecká fakulta v Opavě
UT WoS
Klíčová slova anglicky
Membrane Computing; Tissue P Systems; Cell Separation; Computational Complexity; SAT Problem
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Návaznosti
ED1.1.00/02.0070, projekt VaV.
Změněno: 19. 3. 2020 14:52, doc. Ing. Petr Sosík, Dr.
Anotace
V originále
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.