Article
Solving the 3-COL problem by using tissue P systems without environment and proteins on cells
Author/s | Díaz Pernil, Daniel
Christinal, Hepzibah A. Gutiérrez Naranjo, Miguel Ángel |
Department | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Publication Date | 2018 |
Deposit Date | 2024-04-23 |
Published in |
|
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 ... 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. |
Citation | Díaz Pernil, D., Christinal, H.A. y Gutiérrez Naranjo, M.Á. (2018). Solving the 3-COL problem by using tissue P systems without environment and proteins on cells. INFORMATION SCIENCES, 430, 240-246. https://doi.org/10.1016/j.ins.2017.11.022. |
Files | Size | Format | View | Description |
---|---|---|---|---|
14_Solving_the_3COL_1-s2.0-S00 ... | 245.7Kb | [PDF] | View/ | |