Artículo
A Tissue P Systems Based Uniform Solution to Tripartite Matching Problem
Autor/es | Niu, Yunyun
Pan, Linqiang Pérez Jiménez, Mario de Jesús Rius Font, Miquel |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2011 |
Fecha de depósito | 2021-04-27 |
Publicado en |
|
Resumen | A tissue P system with cell division is a computing model which has two basic features: intercellular communication and the ability of cell division. The ability of cell division allows us to obtain an exponential amount ... A tissue P system with cell division is a computing model which has two basic features: intercellular communication and the ability of cell division. The ability of cell division allows us to obtain an exponential amount of cells in linear time and to design cellular solutions to computationally hard problems in polynomial time. In this work we present an efficient solution to the tripartite matching problem by a family of such devices. This solution leads to an interesting open problem whether tissue P systems with cell division and communication rules of length 2 can solve NP-complete problems. An answer to this open problem will provide a borderline between efficiency and non-efficiency in terms of the lengths of communication rules |
Agencias financiadoras | Ministerio de Educación y Ciencia (MEC). España Junta de Andalucía |
Identificador del proyecto | TIN2009-13192
P08-TIC-04200 |
Cita | Niu, Y., Pan, L., Pérez Jiménez, M.d.J. y Rius Font, M. (2011). A Tissue P Systems Based Uniform Solution to Tripartite Matching Problem. Fundamenta Informaticae, 109 (2), 179-188. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
A tissue P systems based uniform ... | 225.5Kb | [PDF] | Ver/ | |