A uniform family of tissue P systems with cell division solving 3-COL in a linear time

• DOI: 10.1016/j.tcs.2008.04.005
• Publication Date: 2008-04-08T16:18:06Z
• Authors: Daniel Díaz-Pernil; Miguel A. Gutiérr...; Mario J. Pérez-Ji...; Agustín Riscos-Núñez
• Keywords: Tissue P systems; Cell division; Membrane computing; 3-coloring problem; 0102 computer and information sciences; 01 natural sciences; Theoretical Computer Science; Computer Science(all)

AbstractSeveral examples of the efficiency of cell-like P systems regarding the solution of NP-complete problems in polynomial time can be found in the literature(obviously, trading space for time). Recently, different new models of tissue-like P systems have received much attention from the scientific community. In this paper we present a linear-time solution to an NP-complete problem from graph theory, the 3-coloring problem, and we discuss the suitability of tissue-like P systems as a framework to address the efficient solution to intractable problems.