The Relevance of the Environment on the Efficiency of Tissue P Systems

摘要

The efficiency of computational devices is usually expressed in terms of their capability to solve computationally hard problems in polynomial time. This paper focuses on tissue P systems, whose efficiency has been shown for several scenarios where the number of cells in the system can grow exponentially, e.g. by using cell division rules or cell separation rules. Moreover, in the first case it suffices to consider very short communication rules with length bounded by two, and in the second one it is enough to consider communication rules with length at most three. This kind of systems have an environment with the property that objects initially located in it appear in an arbitrarily large number of copies, which is a somewhat unfair condition from a computational complexity point of view. In this context, we study the role played by the environment and its ability to handle infinitely many objects, in particular we consider tissue P systems whose environment is initially empty.