Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
The Efficiency of Tissue P Systems with Cell Separation Relies on the Environment
verfasst von : Luis F. Macías-Ramos, Mario J. Pérez-Jiménez, Agustín Riscos-Núñez, Miquel Rius-Font, Luis Valencia-Cabrera
Erschienen in: Membrane Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The classical definition of tissue P systems includes a distinguished alphabet with the special assumption that its elements are available in an arbitrarily large amount of copies. These objects are shared in a distinguished place of the system, called the
environment
. This ability of having infinitely many copies of some objects has been widely exploited in the design of efficient solutions to computationally hard problems by means of tissue P systems.
This paper deals with computational aspects of tissue P systems with cell separation where there is no such environment as described above. The main result is that only tractable problems can be efficiently solved by using this kind of P systems. Bearing in mind that
NP
–complete problems can be efficiently solved by using tissue P systems without environment and with cell division, we deduce that in the framework of tissue P systems without environment, the kind of rules (separation versus division) provides a new frontier of the tractability of decision problems.