2024-04-25T11:23:55Z
https://meral.edu.mm/oai
oai:meral.edu.mm:recid/2037
2021-12-13T06:22:59Z
1582963390870:1582967549708
user-uy
SOLUTION TO THE SUBSETSUMPROBLEM USING THE FRAMEWORK OF SPIKING NEURAL P SYSTEMS WITH STRUCTURAL PLASTICITY
Cabarle, Francis George C.
Adorna, Henry N.
Spiking neural P systems (in short, SNP systems) are parallel, distributed models of computations based on the structure and function of neural cells or neurons. Neurons process only a single type of signal or object known as the spike. The neurons are placed on vertices of a directed graph, where each edge in the graph is called a synapse. Information cannot be discerned from the spikes, as spikes are indistinct signals. Instead, information is obtained
from the time intervals between spikes, or the presence (absence) of spikes at certain time steps. Time therefore is a means to encode information, rather than simply being a background of the computations. It is known that SNP systems and their variants are Turing universal, i.e. they can simulate any Turing machine, and thus can carry out any effective computation that we know of.
Since the introduction of SNP systems in 2006 (see [3]), many theoretical and practical problems have been solved using SNP systems. See e.g. [4] and the SNP systems chapter in [5]. In this extended abstract we use the variant known as SNP systems with structural plasticity (in short, SNPSP systems). SNPSP systems were introduced in [6] to include the neuroscience feature of structural plasticity in the SNP systems framework. In SNPSP systems, plasticity rules allow neurons to create or delete synapses.
We use SNPSP systems in this work to provide a constant time, nondeterministic solution to the Subset sum problem. This problem is a well-known computationally hard problem with important use in cryptography. The hardness of the Subset sum problem is applied to practical use in order to secure many systems requiring encryption, see e.g. [1, 2]. Briefly, the Subset sum problem has as its inputs a set of natural numbers V = {vi, v2,..,. vn} and a
natural number S. The task is to find a subset B of V where the elements of B sum exactly to S, see e.g. [7].
An SNPSP system solving Subset sum is given in graphical form in Figure 1. Using plasticity rules (see Figure 1), we are able to reduce the number of neurons in our system by a linear amount (with respect to problem input size n) compared to the number of neurons in the SNP system given in [8].
2015
http://hdl.handle.net/20.500.12678/0000002037
https://meral.edu.mm/records/2037