Article
Uniform solutions to SAT and Subset Sum by spiking neural P systems
Author/s | Leporati, Alberto
Mauri, Giancarlo Zandron, Claudio Paun, Gheorghe Pérez Jiménez, Mario de Jesús ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
Department | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Publication Date | 2009 |
Deposit Date | 2017-12-28 |
Published in |
|
Abstract | We continue the investigations concerning the possibility of using spiking neural
P systems as a framework for solving computationally hard problems, addressing two
problems which were already recently considered in this ... We continue the investigations concerning the possibility of using spiking neural P systems as a framework for solving computationally hard problems, addressing two problems which were already recently considered in this respect: Subset Sum and SAT: For both of them we provide uniform constructions of standard spiking neural P systems (i.e., not using extended rules or parallel use of rules) which solve these problems in a constant number of steps, working in a non-deterministic way. This improves known results of this type where the construction was non-uniform, and/or was using various ingredients added to the initial definition of spiking neural P systems (the SN P systems as defined initially are called here ‘‘standard’’). However, in the Subset Sum case, a price to pay for this improvement is that the solution is obtained either in a time which depends on the value of the numbers involved in the problem, or by using a system whose size depends on the same values, or again by using complicated regular expressions. A uniform solution to 3-SAT is also provided, that works in constant time. |
Project ID. | TIN2006-13425
![]() TIC-581 ![]() HI 2005-0194 ![]() |
Citation | Leporati, A., Mauri, G., Zandron, C., Paun, G. y Pérez Jiménez, M.d.J. (2009). Uniform solutions to SAT and Subset Sum by spiking neural P systems. Natural Computing, 8 (4), 681-702. |
Files | Size | Format | View | Description |
---|---|---|---|---|
s11047-008-9091-y.pdf | 1.689Mb | ![]() | View/ | |