Spiking Neural P Systems with Structural Plasticity: Attacking the Subset Sum Problem

Spiking Neural P Systems with Structural Plasticity: Attacking the Subset Sum Problem Francis George C. Cabarle1(B), Nestine Hope S. Hernandez1, and Miguel ´ Angel Mart´ınez-del-Amor2 1Algorithms and Complexity Lab, Department of Computer Science, University of the Philippines Diliman, Diliman, 1101 Quezon City, Philippines [email protected], [email protected] 2Department of Computer Science and AI, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] Abstract. Spiking neural P systems with structural plasticity (in short, SNPSP systems) are models of computations inspired by the function and structure of biological neurons. In SNPSP systems, neurons can create or delete synapses using plasticity rules.Wereporttwofamilies of solutions:anon-uniform and a uniform one, to the NP-complete problem Subset Sum using SNPSP systems. Instead of the usual rule-level nondeterminism (choosing which rule to apply) we use synapse-level nondeterminism (choosing which synapses to create or delete). The nondeterminism due to plasticity rules have the following improvements from a previous solution: in our non-uniform solution, plasticity rules allowed for a normal form to be used (i.e. without forgetting rules or rules with delays, system is simple, only synapse-level nondeterminism); in our uniform solution the number of neurons and the computation steps are reduced. Keywords: Membrane computing ·Spiking neural P system ·Structural plasticity ·NP-complete ·Subset Sum 1 Introduction Membrane computing,[18]abranchofnatural computing, aims to abstract and obtain computing ideas, data structures and operations from the function and structure of living cells. Several introductory and advanced books [8,19] (including a handbook [21]) have been produced for this branch, as well as a recent collection of applications to systems and synthetic biology [9]. As early as 2006, membrane algorithms [16] have been introduced for approximation inspired by P systems (the model of computations in membrane computing). The P systems webpage [1] includes an updated list of workshops, conferences, and books on or related to membrane computing (including a collection of PhD theses). The Thomson Reuters Institute for Scientific Information (in short, ISI) has identified membrane computing as a “fast emerging research front” as early as October 2003, see e.g. [2]. In this work, the specific P systems we consider are spiking neural P systems (in short, SNP systems) first introduced in [12]. In particular, we focus on a variant of SNP systems known as spiking neural P systems with structural plasticity (in short, SNPSP systems), recently introduced in [4] and improved and extended in [7]. We do not go into the details of SNP systems here, including their neuroscience inspirations, computing power (i.e. what a model can or cannot compute) and computational complexity (i.e. time and space efficiency in solving problems). We refer the reader instead to good introductions in [12,20] and the SNP systems chapter in the membrane computing handbook [21]. In SNPSP systems, neurons are placed on the vertices of a directed graph, and the edges between neurons are called synapses.Asidefromspiking rules (more details below) which are used to consume and produce spikes, SNPSP systems have plasticity rules. Plasticity rules allow a neuron σito create or delete synapses from itself (i.e. outgoing edges of σi) but cannot create or delete synapses towards itself (incoming edges of σi). The plasticity rules in SNPSP systems are inspired by actual structural plasticity in biological neurons [3]. In this work we use SNPSP systems to provide families of solutions to the NP-complete problem Subset Sum. The hardness of the Subset Sum problem is applied to practical and important use in order to secure many systems requiring encryption, e.g. in [11]. Of course, when we refer to solutions to a problem, we mean to say that we provide an algorithm solving the problem, where the algorithm in this case is the constructed SNPSP system. This paper is organized as follows: some preliminaries for the rest of this work are given in Sect. 2. Syntax and semantics of SNPSP systems in Sect. 3. The Subset Sum problem as well as some existing solutions using SNP systems are provided in Sect. 4. Complexity classes of SNPSP systems, with respect to the type of solution, are also provided in Sect. 4. A non-uniform family of solutions is given in Sect. 5. A uniform family of solution is provided in Sect.6. Lastly, Sect. 7provides some final remarks and future research directions. 2 Preliminaries Before proceeding to the syntax (i.e. elements that constitute a model) and semantics (i.e. the meaning and use of elements of a model) of SNPSP systems, we briefly recall regular expressions. Regular expressions will be used by neurons to check which spiking or plasticity rules to apply. We denote the set of natural (counting) numbers as N={0,1,2,...}, where N+=N−{0}.Let Vbe an alphabet, V∗is the set of all finite strings over Vwith respect to concatenation and the identity element λ(the empty string). The set of all non-empty strings over Vis denoted as V+,so V+=V∗−{λ}. A language L⊆V∗is regular if there is a regular expression Eover Vsuch that L(E)=L. A regular expression over an alphabet Vis constructed starting from λand the symbols of Vusing the operations union, concatenation, and +. Specifically, (i)λand each a∈Vare regular expressions, (ii)ifE1and E2are regular expressions over Vthen (E1∪E2), E1E2,andE+ 1are regular expressions over V, and (iii) nothing else is a regular expression over V. With each expression Ewe associate a language L(E) defined in the following way: (i) L(λ)={λ} and L(a)={a}for all a∈V, (ii) L(E1∪E2)=L(E1)∪L(E2), L(E1E2)= L(E1)L(E2), and L(E+ 1)=L(E1)+, for all regular expressions E1,E2over V. Unnecessary parentheses are omitted when writing regular expressions. If V={a}, we simply write a∗and a+instead of {a}∗and {a}+.Ifa∈V,we write a0=λ. 3 Spiking Neural P Systems with Structural Plasticity In this section we define SNP systems with structural plasticity. Motivations and recent results in SNPSP systems are included in a series of papers in [5–7]. A spiking neural P system with structural plasticity (SNPSP systems) of degree m≥1 is a construct of the form Π=(O,σ1,...,σ m,syn,out), where: –O={a}is the singleton alphabet (ais called spike); –σ1,...,σ mare neurons of the form (ni,R i),1≤i≤m;ni≥0 indicates the initial number of spikes in σi;Riis a finite rule set of σiwith two forms: 1. Spiking rule: E/ac→a, where Eis a regular expression over O,c≥1; 2. Plasticity rule: E/ac→αk(i, N), where Eis a regular expression over O, c≥1, α∈{+,−,±,∓},k≥1, and N⊆{1,...,m}−{i}; –syn ⊆{1,...,m}×{1,...,m}, with (i, i)/∈syn for 1 ≤i≤m(synapses between neurons); –in, out ∈{1,...,m}indicate the input and output neuron labels. Given neuron σi(we also say neuron ior simply σi) we denote the set of neuron labels with σias their presynaptic (postsynaptic, respectively) neuron as pres(i), i.e. pres(i)={j|(i, j)∈syn}(as pos(i)={j|(j, i)∈syn}, respectively). Essentially, |pres(i)|and |pos(i)|is the out- and in-degree of the neuron (i.e. vertex) σi, respectively. Spiking rules are applied as follows: If neuron σicontains bspikes and ab∈L(E), with b≥c, then a rule E/ac→a∈Rican be applied. Applying such a rule means consuming cspikes from σi, thus only b−cspikes remain in σi. Neuron isends one spike to every neuron with a label in pres(i)at the same step as rule application. A writing convention we adopt is as follows: if a rule E/ac→ahas L(E)={ac}, we simply write this as ac→a. Plasticity rules are applied as follows. If at step twe have that σihas b≥c spikes and ab∈L(E), a rule E/ac→αk(i, N)∈Rican be applied. The set Nis a collection of neurons to which σican create a synapse to, or remove a synapse from, using the applied plasticity rule. The rule consumes cspikes and performs one of the following, depending on α: –Ifα:= + and N−pres(i)=∅,orifα:= −and pres(i)=∅, then there is nothing more to do, i.e. cspikes are consumed but no synapses are created or removed. The former case corresponds to the case when σihas a synapse to all neurons with labels in N, while the latter corresponds to the case when σi has no more outgoing synapses to delete. –forα:= +,if |N−pres(i)|≤k, deterministically create a synapse to every σl,l∈Nj−pres(i). If however |N−pres(i)|>k,nondeterministically select kneurons in N−pres(i), and create one synapse to each selected neuron. –forα:= −,if |pres(i)|≤k, deterministically delete all synapses in pres(i). If however |pres(i)|>k,nondeterministically select kneurons in pres(i), and delete each synapse to the selected neurons. If α:= ±(α:= ∓, respectively), create (delete, respectively) synapses at step t and then delete (create, respectively) synapses at step t+1. Only the application priority of synapse creation or deletion is changed, but the semantics of synapse creation and deletion remain the same as when α∈{+,−}. Neuron ican receive spikes from tuntil t+ 1, but σican only apply another rule at time t+2. An important note is that for σiapplying a rule with α∈{+,±,∓}, creating a synapse always involves a sending of one spike when σiconnects to a neuron. This single spike is sent at the time the synapse creation is applied, i.e. whenever synapse (i, j) is created between σiand σjduring synapse creation, we have σi immediately transferring one spike to σj. SNPSP systems are locally sequential (at each step, at most one rule is applied per neuron) but globally parallel (neurons operate in parallel). Note that the application of rules in neurons are synchronized, i.e. a global clock is assumed and if a neuron can apply a rule then it must do so. A configuration of an SNPSP system is based on (a) distribution of spikes in neurons, and (b) neuron connections based on syn. For some step t, we can represent: (a)ass1,...,s m where si,1≤i≤m, is the number of spikes contained in σi;for(b) we can derive pres(i)andpos(i)fromsyn, for a given σi. The initial configuration therefore is represented as n1, ..., n m, with the possibility of a disconnected graph. Rule application (as defined above) allows for transitions from one configuration to another. A computation is defined as a sequence of transitions,froman initial configuration, and following rule application semantics. A computation halts if the system reaches a halting configuration, i.e. a configuration where no rules can be applied. The output neuron applying a rule (we also say firing) triggers an output of the system, which will be defined below. The output neuron sends spikes to the environment,andpres(out)=∅.Theinput neuron receives spikes from the environment and pos(in)=∅. An example of an SNPSP system is Π=({a},σ l,σ m,σ n,syn,n) where σl=(1,{a→±1(l,{m, n}}),σ m=σn=(0,{a→a}),syn={(m, n)},and the output neuron is σn. However and in what follows, for the sake of brevity we omit formally defining the SNPSP system construct. We instead provide a graphical representation as in Fig. 1. A computation of Πis as follows: the initial Fig. 1. An SNPSP system Π. configuration is 1,0,0representing the corresponding spike distribution in the neuron order σl,σ m,σ n. Since a∈L(a),the plasticity rule of σlcan be applied (we denote this as step t). Since α:= ±and k=1<|{m, n}|,σlmust nondeterministically choose to create either synapse (l,m)or(l,n)att.Atttherefore we have either the synapse set syn=syn ∪{(l,m)}or syn =syn ∪{(l, n)}.Alsoattwe have σl immediately sending a spike to σmif (l,m) is created, and the spike distribution is now 0,1,0.If(l,n) is created, the spike distribution is 0,0,1, since σn immediately receives a spike from σiduring synapse creation. At step t+1the created synapse at tis deleted, since α:= ±,sowehavesyn ={(m, n)}again. Notice that if (l,m) was created, the single spike is sent out to the environment (i.e. σnspikes) at step t+ 2. Otherwise the spike is sent to the environment at t+ 1 (if (l, n) was created). 4 Solving Subset Sum with SNPSP systems SNP systems have been used to solve many NP-complete problems, see e.g. [13–15,17,22]. These solutions are usually categorized as either non-uniform or uniform solutions. A problem Qis solved in a non-uniform way if for each specified instance Iof Qwe build an SNPSP system ΠQ,I , whose structure and initial configuration depend on I. Furthermore, ΠQ,I halts and the output neuron spikes at a specified time interval if and only if Iis a positive instance of Q. A uniform solution to Qconsists of a family {ΠQ(n)}n∈Nof SNPSP systems such that, given an instance I∈Qof size n, we introduced a polynomial (in n) number of spikes in specified (set of) input neuron(s) of ΠQ(n). Again, ΠQ(n) halts and the output neuron spikes at a specified time, if and only if Iis a positive instance. More formally, let X=(IX,Θ X) be a decision problem, and g:N→N a computable function, where IXis a set of instances and ΘXis a predicate over IX.WesayXis solvable by a family Π={Π(n)|n∈N}of SNPSP systems, in time bounded by g,inanondeterministic and uniform way (denoted as X∈NSNP(g)) if the following hold: – The family Πis polynomially uniform by Turing machines, i.e. there exists a deterministic Turing machine working in polynomial time which constructs Π(n),n∈N. – There exist polynomial time computable functions, cod and s,overIX, such that •For each instance w∈IX,s(w) is a natural number, and cod(w) is a valid input (using some encoding) of the SNPSP system Π(s(w)). •The family Πis g-bounded with respect to (X, cod, s), i.e. for each instance w∈IX, the minimum length of an accepting computation of Π(s(w)) with input cod(w) is bounded by g(|w|). •The family Πis sound with respect to (X, cod, s), i.e. for each w∈IX, if there exists an accepting computation of Π(s(w)) with input cod(w), then ΘX(w)=1. •The family Πis complete with respect to (X, cod, s), i.e. for every w∈IX, if ΘX(w) = 1 then there exists a computation of Π(w) with input cod(w) which is an accepting computation. We say X=(IX,Θ X) is solvable in polynomial time by a family Π= {Π(n)|n∈N}of SNPSP systems, in a nondeterministic and uniform way (denoted as X∈NPSNP) if there exists a k∈Nsuch that Xis solvable by the family Πin time bounded by a polynomial, in a nondeterministic and uniform way. The preference of uniform solutions over non-uniform solutions is given by the fact that the former are more strictly related to the structure of the problem, instead of specific instances of the problem. For non-uniform solutions, input neurons are not needed since the problem instance is embedded in the system structure (e.g. number of spikes, neurons, or rules) while in uniform solutions, at least one input neuron is needed to introduce the instance into the system. Deterministic and nondeterministic solutions (both for non-uniform and uniform solutions) can be found in [13–15,17,22]. Note that nondeterministic solutions allow for more “compact” solutions, in terms of the number of neurons in the system. Unless P=NP, we need exponential space (i.e. neurons) to deterministically solve hard problems in polynomial time. The NP-complete problem considered here, Subset sum,can be defined as follows: Problem: Subset Sum [10] – Instance: S, and a (multi)set V={v1,v 2,...,v n},with S, vi∈Nand 1≤i≤n; – Question: Is there a sub(multi)set B⊆Vsuch that  b∈B b=S? In [15], the Subset sum problem was also solved in a nondeterministic and non-uniform way using SNP systems with extended rules: extended rules, as compared to spiking rules, are of the form E/ac→apwith the meaning that each step a neuron can produce p≥1 spikes instead of only one spike. Additionally, [15] used some neurons that applied rules sequentially, while some neurons applied their rules in an exhaustive manner (i.e. it is possible to apply a rule more than once in one step). A follow-up and improved (uniform) solution was then given in [14]. There are several ways of encoding an instance of Subset Sum as the input to the system. Two common ways (used in this work, and as [15] and [14]) involve either (i) starting with an initial configuration where each σi stores vinumber of spikes, 1 ≤i≤n(for the non-uniform solution), or (ii) each σinireceives a number of spikes from the environment equal to non-zero multiples of vi,1≤i≤n(for the uniform solution). 5 A Non-uniform Solution to Subset Sum We begin by providing a family Πof nondeterministic and non-uniform SNPSP systems solving Subset Sum in constant time, as given in [7]. Actually, the non-uniform solution provided in this section fixes a “bug” in the non-uniform solution given in [7]. The non-uniform solution provided in [7] indeed solves the Subset Sum problem, but it is possible for the solution to produce false positive results. The size of each Π∈Πis dependent on the value of nand each vi,1≤i≤n. The number of neurons is a function of the magnitude of each vi. The construct of each SNPSP system Πss,I ,Π ss ∈Π,that solves instance I of the Subset Sum problem is as follows: Πss,I ={a},σi,σ i(Y),σ i(N),σ i(j),σ out 1≤i≤n, 1≤j≤vi,syn,out  where V={v1,v 2,...,v n}and we need to check for the value S. We refer to Fig. 2for a graphical representation of Πss . Compared to the non-uniform solution in [15], each Πss has the following normal form (i.e. a simplifying set of restrictions): (i)simple, i.e. each neuron has exactly one rule; (ii) only synapselevel nondeterminism, i.e. nondeterministic choice exists only in choosing which synapse to create and not which rule to apply (known as rule-level nondeterminism;(iii) no forgetting rule or rule with a delay is used. The initial configuration is where every σihas one spike, and every other neuron has none. In step 1, each neuron σinondeterministically chooses to create either synapse i, i(Y)or i, i(N).Ifi, i(N)is created, neuron σi(N)consumes a spike but has presi(N)=∅, hence no more computations can proceed. If i, i(Y)is created, then at step 2, σi(Y)then it sends one spike each to σi(1) to σi(vi), i.e. vinumber of spikes are produced since  presi(Y) =vi. Once neurons σi(1) to σi(vi)receive one spike each, they send one spike each to σout at step 3. If exactly Snumber of spikes are received by σout then σout will send a spike to the environment. Therefore if an affirmative answer to the problem instance exists, a spike would be sent to the environment in four steps since the initial configuration. Otherwise, no spike sent to the environment in four steps indicates a negative answer to the instance. Whether σout sends a spike or not, the system still halts in four steps. This ends the description of the non-uniform solution. Fig. 2. The non-uniform SNPSP system Πss solving Subset Sum. In Πss the computation time is constant (four steps) but the number of neurons is dependent on the individual values of the input numbers vi,1≤ i≤n. In this case, our non-uniform solution using exactly one (plasticity) rule in some neurons is enough to replace the functions of rules with delays and forgetting rules in the non-uniform solution in [15]. At the price of extending the computation time, we obtain a uniform solution in the following section. 6 A Uniform Solution to Subset Sum Next, we provide a family Πsolving Subset Sum in a nondeterministic and uniform way in constant time. In this case, the system only “knows” the value of n, while Sand each vi,1≤i≤nmust be introduced into the system using n+1 input neurons. This uniform family of solutions improves the solution provided in the previous section and the uniform solution in [15]. Each SNPSP system Πus (n),Π us ∈Π,that solves instance Iof size nof the problem is illustrated in Fig. 3. We introduce 2vi,1≤i≤nspikes into the corresponding input neuron ini, while we introduce 2Sspikes into inn+1. Figure 3 shows these spikes already present in the n+1 input neurons. These even number of spikes cannot be used by σiniuntil a spike is received from σci. Neurons σci,1≤i≤nare the only neurons with nondeterminism (synapse-level). These neurons nondeterministically allow their corresponding σinineurons to spike (if σcicreates synapse (ci,in i)) or not (if σcicreates synapse (ci,x)). Note that there is no σxso that (ci,x) is never actually created. Neurons σciapply their rules at step 1, and at step 3 neurons ei,1spike if they become activated from their corresponding inineuron. It also takes 3 steps before σh3and σh4begin to spike, starting with the spiking of σh1at step 1. Neurons σh3and σh4“feed” a spike to each other starting at step 3. A spike is also sent from σh4to σt1(the “comparison trigger” neuron). At step 4 the odd number of spikes in σt1, sent by the activated ei,1neurons and σh4), allows the use of its forgetting rule to remove all of its spikes. At step 5 only σh4sends a spike to σt1.Atstep6,σt1sends one spike each to σh4and σt2, while σt1receives one more spike from σh4.Atstep7,σh4stores two spikes so it can never spike again, while σt1sends one more spike to σt2.At step 8, σt2sends a spike to σacc and σnn+1 which become activated with an odd number of spikes now. Both σacc and σnn+1 empty their spikes (removing two spikes each step) while sending one spike each to σout. If the number of spikes accumulated in σacc equals the 2Snumber of spikes in σnn+1 , then the system will halt without producing a spike to the environment. Otherwise, σout will receive one spike from either σacc or σnn+1 and send one spike to the environment. Halting without σout producing a spike, and halting with σout producing a spike, corresponds to a positive and negative answer to the problem instance, respectively. This ends the description of the uniform solution. The number of neurons is constant, with 4n+ 9 neurons. The system halts in at most 2 n i=1 vi+ 6 steps: we have one initial step; at most max{vi|1≤i≤ n}+ 1 to move the spikes from σinito σt1; one step for σt1to send its first (out of two) spike; σacc and σinn+1 become activated after two steps, once σt1has sent two spikes; at most n i=1 visteps for comparison between the spikes of σacc and σinn+1 ; the last step is for σout to send one spike to the environment. Since max{vi|1≤i≤n}≤n i=1 vi, we obtain the upper bound for the halting time. Fig. 3. The uniform SNPSP system Πus solving Subset Sum. Actually, the forgetting rules in Πus can be removed by using a plasticity rule that functions like a forgetting rule, which is done by the σcineurons (synapse (ci,x) is never created). The number of neurons and the halting time will still remain the same. In comparison, the non-uniform system in [15] solving Subset Sum (using forgetting rules, rules with delays, and standard rules) computes in four steps, while their uniform solution halts in at most 3 n i=1 vi+6 steps using 5n+ 13 neurons (also using delays, forgetting rules, and standard rules). Thus, one benefit of using synapse-level nondeterminism in this case is decreasing the needed neurons by a linear amount. Also in this case, fewer number of neurons helped improve the computation time: spikes have fewer neurons to pass through, so the spike of σout is sent to the environment sooner rather than later. 7 Final Remarks In this work, we fixed the non-uniform solution to Subset Sum in [7]using SNPSP systems. We also provided a uniform family of solutions to Subset Sum