Solving SUBSET SUM by Spiking Neural P Systems with Pre-computed Resources
Solving SUBSET SUM by Spiking Neural P Systems with Pre-computed Resources
复制标题
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Leporati;M. A. Gutiérrez-Naranjo
中科院分区：
文献类型：
--
作者：
A. Leporati;M. A. Gutiérrez-Naranjo
最近的可能性，使用脉冲神经P系统解决计算困难的问题已被考虑。这种解决方案假设预先给出了一些（可能是指数级大的）预先计算的资源，前提是它们的结构是“规则的”，并且它们既不包含简化特定实例的解决方案的“隐藏信息”，也不包含所有可能解决方案的编码（即，允许在解决问题的实例时作弊的指数级信息量）。在本文中，我们继续这一研究路线，我们探讨解决数值NP完全问题，如子集和的可能性。特别是，我们首先提出了一个半统一的家庭的尖峰神经P系统，其中每个系统解决了一个特定的例子子集总和。然后，我们利用一种技术来计算迭代加法与布尔电路，以获得一个统一的家庭的尖峰神经P系统，其中每个系统都能够解决任何实例的子集和一个固定的大小。这里考虑的所有系统都是确定性的，并且它们的大小通常相对于实例大小呈指数增长。
Recently the possibility of using spiking neural P systems for solving computationally hard problems has been considered. Such solutions assume that some (possibly exponentially large) pre-computed resources are given in advance, provided that their structure is "regular" and they do not contain neither "hidden information" that simplify the solution of specific instances, nor an encoding of all possible solutions (that is, an exponential amount of information that allows to cheat while solving the instances of the problem). In this paper we continue this research line, and we investigate the possibility of solving numerical NP-complete problems such as SUBSET SUM. In particular, we first propose a semi-uniform family of spiking neural P systems in which every system solves a specific instance of SUBSET SUM. Then, we exploit a technique used to calculate ITERATED ADDITION with Boolean circuits to obtain a uniform family of spiking neural P systems in which every system is able to solve any instance of SUBSET SUM of a fixed size. All the systems here considered are deterministic, and their size generally grows exponentially with respect to the instance size.