Published December 28, 2017
| Version v1
Publication
Uniform solutions to SAT and Subset Sum by spiking neural P systems
Description
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.
Abstract
Ministerio de Educación y Ciencia TIN2006-13425Abstract
Junta de Andalucía TIC-581Abstract
Ministerio de Educación y Ciencia HI 2005-0194Additional details
Identifiers
- URL
- https://idus.us.es/handle/11441/68031
- URN
- urn:oai:idus.us.es:11441/68031