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

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.

Keywords:

• membrane computing
• tissue P systems
• cell division
• environment of a tissue
• computational complexity

2010 AMS Subject Classifications:

• 68Q05
• 68Q15

Acknowledgements

The work was supported by Project of Excellence with Investigador de Reconocida Valía, from Junta de Andalucía, grant P08 – TIC 04200, and by Project TIN2009-13192 of the Ministerio de Ciencia e Innovación of Spain, cofinanced by FEDER funds.