Solving 3-COL with Tissue P Systems

In the literature, several examples of the efficiency of cell-like P systems in order to solve NP-complete problems in polynomial time can be found. Recently, various new models of tissue-like P systems have received important attention from the scientific community. In this paper we present a linear-time solution to an NP-complete problem, the 3-COL problem, and discuss the possibilities of tissue-like P systems to solve hard problems.