Solving the 3-COL problem by using tissue P systems without environment and proteins on cells

Abstract

The 3-COL problem consists on deciding if the regions of a map can be coloured with only three colors bearing in mind that two adjacent regions must be coloured with different colors. It is a NP problem and it has been previously used in complexity studies in membrane computing to check the ability of a model for solving problems of such complexity class. Recently, tissue P systems with proteins on cells have been presented and its ability to solve NP problems has been proved, but it remained as an open question to know if such model was still able to solve such problems if the environment was removed. In this paper, we provide an affirmative answer to this question by showing a uniform family of tissue P systems without environment and with proteins on cells which solves the 3-COL problem in linear time.