J 2015

An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Separation

PEREZ-JIMENEZ, MJ a Petr SOSÍK

Zá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ě

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.

Přiložené soubory