کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430011 | 687773 | 2015 | 12 صفحه PDF | دانلود رایگان |
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-NPNP∪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.
Journal: Journal of Computer and System Sciences - Volume 81, Issue 2, March 2015, Pages 473–484