Time-free solution to SAT problem by P systems with active membranes and standard cell division rules

摘要

P systems are a class of distributed and parallel computing models inspired by the structure and the functioning of a single cell and complexes of cells. The computational efficiency of P systems with active membranes has been investigated widely with the assumption that the application of rules is completed in exactly one time unit. However, in biological facts, different biological processes may take different times to complete, and the execution time of certain biological process could vary because of external uncontrollable conditions. With this biological motivation, in this work, we solve SAT problem by a family of P systems with active membranes in a time-free manner in the sense that the correctness of the solution does not depend on the precise timing of the involved rules. In such a solution, standard cell division rules for elementary membranes are applied: the newly generated membranes have the same label with their parent membrane. This result answers an open problem formulated in Song et al. (Theor Comput Sci 529:61-68, 2014).