Ponencia
Solving Numerical NP-complete Problems by Spiking Neural P Systems with Pre–computed Resources
Autor/es | Gutiérrez Naranjo, Miguel Ángel
Leporati, Alberto |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2008 |
Fecha de depósito | 2016-03-18 |
Publicado en |
|
ISBN/ISSN | 9788461244294 |
Resumen | Recently we have considered the possibility of using spiking neural P systems
for solving computationally hard problems, under the assumption that some (possibly exponentially
large) pre-computed resources are given in ... Recently we have considered the possibility of using spiking neural P systems for solving computationally hard problems, under the assumption that some (possibly exponentially large) pre-computed resources are given in advance. 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 specified 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 all the instances of Subset Sum of a fixed size. All the systems here considered are deterministic, but their size generally grows exponentially with respect to the instance size. |
Agencias financiadoras | Ministerio de Educación y Ciencia (MEC). España Junta de Andalucía |
Identificador del proyecto | TIN2006-13425
TIC-581 |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
subsetsum.pdf | 389.2Kb | [PDF] | Ver/ | |