A limitation of cell division in tissue P systems by PSPACE

摘要

P systems are abstract distributed computing models inspired by the information flows in living cells and their networks, with applications, e.g., in systems biology and optimization. A tissue P system is a variant based on the interchange of objects between cells due to an underlying communication graph. The model is further enriched with the operation of cell division. This operation allows to produce an exponential number of cells in polynomial time. The paper studies the computational power of polynomially uniform families of these systems. Previous studies demonstrated that they can cover problems ranging between P and NP∪co-NP due to the length of communication rules, thus characterizing a borderline between tractability and intractability. We show that, in spite of the exponential space the model can use, the problems solvable by these families in polynomial time lie within the class PSPACE.