A polynomial alternative to unbounded environment for tissue P systems with cell division

TitleA polynomial alternative to unbounded environment for tissue P systems with cell division
Publication TypeJournal Papers
Year of Publication2013
AuthorsPérez-Jiménez, M. J., Riscos-Núñez A., Rius-Font M., & Romero-Campero F. J.
Journal TitleInternational Journal of Computer Mathematics
PublisherTaylor and Francis
Place PublishedLondon, UK
Volume90
Pages760-775
Abstract

The standard definition of tissue P systems includes a special alphabet whose elements are assumed to appear in the initial configuration of the system in an arbitrarily large number of copies. These objects reside in a distinguished place of the system, called the environment. Such potentially infinite supply of objects seems an unfair tool when designing efficient solutions to computationally hard problems in the framework of membrane computing, by performing a space–time trade-off.

This paper deals with computational aspects of tissue P systems with cell division where there is no environment having the property mentioned above. Specifically, we prove that the polynomial complexity classes associated with tissue P systems with cell division and with or without environment are actually identical. As a consequence, we conclude that it is not necessary to have infinitely many copies of some objects in the initial configuration in order to solve NP–complete problems in an efficient way.

Keywordscell division, Computational Complexity, Environment of a tissue, Membrane computing, Tissue P Systems
URLhttp://www.tandfonline.com/doi/abs/10.1080/00207160.2012.748898
Issue4
Impact Factor

0.542

Ranking

173/247 - Q3

ISSN Number0020-7160
DOI10.1080/00207160.2012.748898