A Tissue P Systems Based Uniform Solution to Tripartite Matching Problem
A Tissue P Systems Based Uniform Solution to Tripartite Matching Problem
复制标题
DOI：
10.3233/fi-2011-503
复制
发表时间：
2011-04
期刊：
影响因子：
--
通讯作者：
Yunyun Niu;L. Pan;M. Pérez-Jiménez;M. Rius-Font
中科院分区：
文献类型：
--
作者：
Yunyun Niu;L. Pan;M. Pérez-Jiménez;M. Rius-Font
具有细胞分裂功能的组织P系统是一种具有两个基本特征的计算模型：细胞间通信和细胞分裂能力。细胞分裂的能力使我们能够在线性时间内获得指数数量的细胞，并在多项式时间内为计算困难的问题设计细胞解决方案。在这项工作中，我们提出了一个有效的解决三方匹配问题的一族这样的设备。这一解决方案引出了一个有趣的开放问题：细胞分裂和通讯规则为2的组织P系统是否能解决NP-完全问题。这个悬而未决的问题的答案将在沟通规则的长度方面提供效率和非效率之间的分界线。
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.