%0 Generic
%D 2012
%T The Role of the Environment in Tissue P Systems with Cell Division
%A Mario J. Pérez-Jiménez
%A Agustín Riscos-Núñez
%A Miquel Rius-Font
%A Francisco J. Romero-Campero
%C Seville, Spain
%I Fénix Editora
%K cell division
%K Computational Complexity
%K Environment of a tissue
%K Membrane computing
%K Tissue P Systems
%P 89-104
%S Proceedings of the Tenth Brainstorming Week on Membrane Computing
%U http://www.gcn.us.es/10BWMC/10BWMCvolII/papers/mario-complejidad.pdf
%V II
%X Classical tissue P systems with cell division have a special alphabet whose elements appear at the initial conﬁguration of the system in an arbitrary large number of copies. These objects are shared in a distinguished place of the system, called the environment. Besides, the ability of these computing devices to have inﬁnite copies of some objects has been widely exploited in the design of eﬃcient solutions to computationally hard problems. This paper deals with computational aspects of tissue P systems with cell division where there is not an environment having the property mentioned above. Speciﬁcally, we establish the relationships between the polynomial complexity class associated with tissue P systems with cell division and with or without environment. As a consequence, we prove that it is not necessary to have inﬁnite copies of some objects at the initial conﬁguration in order to solve NP–complete problems in an eﬃcient way.
%8 02/2012