Computational efficiency and universality of timed P systems with membrane creation

Abstract

P systems are a class of distributed parallel computing models inspired by the structure and the functioning of a living cell, where the execution of each rule is completed in exactly one time unit (a global clock is assumed). How-ever, in living cells, the execution time of different biological processes is difficult to know precisely and very sensi-tive to environmental factors that might be hard to control. Inspired from this biological motivation, in this work, timed polarization P systems with membrane creation are intro-duced and their computational efficiency and universality are investigated. Specifically, we give a time-free semi-uniform solution to the SAT problem by a family of P systems with membrane creation in the sense that the correctness of the solution is irrelevant to the times associated with the involved rules. We also prove that timefree P systems with membrane creation are computationally universal.