Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6856852 | Information Sciences | 2018 | 7 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Daniel DÃaz-Pernil, Hepzibah A. Christinal, Miguel A. Gutiérrez-Naranjo,