The power of time-free tissue P systems: Attacking NP-complete problems

Tissue P systems, which are inspired from the structures and functions of biological tissues, are a class of distributed and parallel computing models. In traditional tissue P systems, each rule (abstracted from biochemical reaction) has precise global execution time. The restriction on the execution time does not coincide with the biological fact, since the execution time of biochemical reaction can vary because of external uncontrollable conditions. In this work, we investigate a class of tissue P systems with no restriction on the execution time of each rule, named time-free tissue P systems. As a result, it is proved that the execution time of the rules has no influence on the computation results of the systems. Moreover, we consider the computational efficiency of time-free tissue P systems and prove that the Maximum Clique Problem and Hamilton Path Problem can be solved in this way in polynomial time with respect to the size of the problems.