Efficient simulation of tissue-like P systems by transition cell-like P systems |
| |
Authors: | Daniel Díaz-Pernil Mario J Pérez-Jiménez Álvaro Romero-Jiménez |
| |
Affiliation: | (1) Department of Computer Science and Artificial Intelligence, Research Group on Natural Computing, University of Sevilla, Sevilla, Spain |
| |
Abstract: | In the framework of P systems, it is known that the construction of exponential number of objects in polynomial time is not
enough to efficiently solve NP-complete problems. Nonetheless, it could be sufficient to create an exponential number of membranes in polynomial time. Working
with P systems whose membrane structure does not increase in size, it is known that it is not possible to solve computationally
hard problems (unless P = NP), basically due to the impossibility of constructing exponential number of membranes, in polynomial time, using only evolution,
communication and dissolution rules. In this paper we show how a family of recognizer tissue P systems with symport/antiport
rules which solves a decision problem can be efficiently simulated by a family of basic recognizer P systems solving the same
problem. This simulation allows us to transfer the result about the limitations in computational power, from the model of
basic cell-like P systems to this kind of tissue-like P systems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|