Journal
INFORMATION SCIENCES
Volume 430, Issue -, Pages 240-246Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2017.11.022
Keywords
Membrane computing; P systems; 3-COL problem
Categories
Ask authors/readers for more resources
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. (C) 2017 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available