Solving SUBSET SUM by Spiking Neural P Systems with Pre-computed Resources

1 Solving SUBSET SUM by Spiking Neural P Systems with Pre–computed Resources Alberto Leporati∗C Dipartimento di Informatica, Sistemistica e Comunicazione Universit` a degli Studi di Milano – Bicocca Viale Sarca 336/14, 20126 Milano, Italy [email protected] Miguel A. Guti´ errez-Naranjo† Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] Abstract. Recently the possibility of using spiking neural P systems for solving computationally hard problems has been considered. Such solutions assume that some (possibly exponentially large) pre–computed resources are given in advance, provided that their structure is “regular” and they do not contain neither “hidden information” that simplify the solution of specific instances, nor an encoding of all possible solutions (that is, an exponential amount of information that allows to cheat while solving the instances of the problem). 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 specific 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 any instance of SUBSET SUM of a fixed size. All the systems ∗The work of the authors was partially supported by the project “Azioni Integrate Italia–Spagna — Theory and Practice of Membrane Computing” (Acci´on Integrada Hispano-Italiana HI 2005-0194). CCorresponding author †The second author acknowledges the support of the project TIN2006-13425 of the Ministerio de Educaci´on y Ciencia of Spain, cofinanced by FEDER funds, and the support of the project of excellence TIC-581 of the Junta de Andaluc´ıa. 2A. Leporati, M.A. Guti´errez-Naranjo /Solving SUBSET SUM by Spiking Neural P Systems here considered are deterministic, and their size generally grows exponentially with respect to the instance size. Keywords: Membrane computing, spiking neural P systems, NP-complete problems, Subset Sum 1. Introduction Spiking neural P systems (SN P systems, for short) have been introduced in [12] as a new class of distributed and parallel computing devices, inspired by the neurophysiological behavior of neurons sending electrical impulses (spikes) along axons to other neurons. SN P systems are the third model of computation in the framework of Membrane Computing, together with the cell-like model [26] inspired by the compartmental structure and functioning of a living cell and the tissue-like model [21, 22], based on intercellular communication and cooperation between neurons. In particular, [32] is the first paper in which P systems with membranes arranged on an arbitrary graph have been considered. SN P systems can also be viewed as an evolution of P systems [26, 27, 29, 31] (the latest information can be found in [37]) corresponding to a shift from cell-like to neural-like architectures where time is used to encode information. We recall that this biological background has already led to several models in the area of neural computation, e.g., see [8, 19, 20]. In SN P systems the cells (also called neurons) are placed in the nodes of a directed graph, called the synapse graph. The contents of each neuron consist of a number of copies of a single object type, called the spike. Every cell may also contain a number of firing and forgetting rules. Firing rules allow a neuron to send information to other neurons in the form of electrical impulses (also called spikes) which are accumulated at the target cell. The applicability of each rule is determined by checking the contents of the neuron against a regular set associated with the rule. In each time unit, if a neuron can use one of its rules, then one of such rules must be used. If two or more rules could be applied, then only one of them is nondeterministically chosen. Thus, the rules are used in the sequential manner in each neuron, but neurons function in parallel with each other. Observe that, as usually happens in membrane computing, a global clock is assumed, marking the time for the whole system, and hence the functioning of the system is synchronized. When a cell sends out spikes it becomes “closed” (inactive) for a specified period of time, that reflects the refractory period of biological neurons. During this period, the neuron does not accept new inputs and cannot “fire” (that is, emit spikes). Another important feature ofbiological neurons is that the length of the axon may cause a time delay before a spike arrives at the target. In SN P systems this delay is modeled by associating a delay parameter to each rule which occurs in the system. If no firing rule can be applied in a neuron, there may be the possibility to apply a forgetting rule, that removes from the neuron a predefined number of spikes. Formally, a spiking neural membrane system (SN P system, for short) of degree m≥1, as defined in [11], is a construct of the form Π = (O, σ1, σ2,...,σm, syn, in, out), where: 1. O={a}is the singleton alphabet (ais called spike); 2. σ1, σ2,...,σmare neurons, of the form σi= (ni, Ri),1≤i≤m, where: A. Leporati, M.A. Guti´errez-Naranjo/Solving SUBSET SUM by Spiking Neural P Systems 3 (a) ni≥0is the initial number of spikes contained in σi; (b) Riis a finite set of rules of the following two forms: (1) firing (also spiking) rules E/ac→a;d, where Eis a regular expression over a, and c≥1,d≥0are integer numbers; if E=ac, then it is usually written in the following simplified form: ac→a;d; (2) forgetting rules as→λ, for s≥1, with the restriction that for each rule E/ac→a;d of type (1) from Ri, we have as6∈ L(E)(where L(E)is the regular language defined by E); 3. syn ⊆ {1,2,...,m} × {1,2,...,m}, with (i, i)6∈ syn for 1≤i≤m, is the directed graph of synapses between neurons; 4. in, out ∈ {1,2,...,m}indicate the input and the output neurons of Π. A firing rule E/ac→a;d∈Rican be applied in neuron σiif it contains k≥cspikes, and ak∈L(E). The execution of this rule removes cspikes from σi(thus leaving k−cspikes), and prepares one spike to be delivered to all the neurons σjsuch that (i, j)∈syn. If d= 0 then the spike is immediately emitted, otherwise it is emitted after dcomputation steps of the system. As stated above, during these dcomputation steps the neuron is closed, and it cannot receive new spikes (if a neuron has a synapse to a closed neuron and tries to send a spike along it, then that particular spike is lost), and cannot fire (and even select) rules. A forgetting rule as→λcan be applied in neuron σiif it contains exactly s spikes, and no firing rules are applicable. The execution of this rule simply removes all the sspikes from σi.The initial configuration of the system is described by the numbers n1, n2,...,nmof spikes present in each neuron, with all neurons being open. During the computation, a configuration is described by both the contents of each neuron and its state, which can be expressed as the number of steps to wait until it becomes open (zero if the neuron is already open). Thus, hr1/t1,...,rm/tmiis the configuration where neuron σicontains ri≥0spikes and it will be open after ti≥0steps, for i= 1,2,...,m; with this notation, the initial configuration of the system is C0=hn1/0,...,nm/0i. Acomputation starts in the initial configuration. In order to compute a function f:N→N, a positive integer number is given as input to a specified input neuron. In the original model, as well as in some early variants, the number is encoded as the interval of time steps elapsed between the insertion of two spikes into the neuron. To pass from a configuration to another one, for each neuron a rule is chosen among the set of applicable rules, and it is executed. Generally, a computation may not halt. However, in any case the output of the system is considered to be the time elapsed between the arrival of two spikes in a designated output cell. Other possibilities exist to encode input and output numbers, as discussed in [11]: as the number of spikes contained in a given neuron at the beginning (resp., the end) of the computation, as the number of spikes fired in a given interval of time, etc. A useful extension to the standard model defined above, already considered in [15, 16, 17, 13], is to use several input neurons, so that the introduction of the encoding of an instance of the problem to be solved can be done in a faster way, introducing parts of the code in parallel in various input neurons. Formally, we can define an SN P system of degree (m, ℓ), with m≥1and 0≤ℓ≤m, just like a standard SN P system of degree m, the only difference being that now there are ℓinput neurons denoted by in1, . . . , inℓ. A valid input for an SN P system of degree (m, ℓ)is a set of ℓbinary sequences, that collectively encode an instance of a problem. 4A. Leporati, M.A. Guti´errez-Naranjo /Solving SUBSET SUM by Spiking Neural P Systems The previous definitions cover many types of systems/behaviors. By neglecting the output neuron we can define accepting SN P systems, in which the natural number (or the vector of natural numbers, in the case of systems having ℓ > 1input neurons) given in input is accepted if the computation halts. On the other hand, by ignoring the input neuron (and thus starting from a predefined input configuration) we can define generative SN P systems. In [12] it was shown that generative SN P systems are universal, that is, can generate any recursively enumerable set of natural numbers. Moreover, a characterization of semilinear sets was obtained by spiking neural P systems with a bounded number of spikes in the neurons. These results can be obtained also for some restricted forms of SN P systems: [10] shows that one of the following features can be avoided while keeping universality: time delay greater than 0, forgetting rules, outdegree of the synapse graph greater than 2, and regular expressions of complex form. In [6] it is shown that universality is kept even if we remove some combinations of two of the above features. Finally, in [30] the behavior of SN P systems on infinite strings and the generation of infinite sequences of 0and 1was investigated, whereas in [3] SN P systems were studied as language generators (over the binary alphabet {0,1}). Spiking neural P systems can also be used to solve decision problems, both in a semi–uniform and in auniform way. When solving a problem Qin the semi–uniform setting, for each specified instance Iof Qwe build an SN P system ΠQ,I, whose structure and initial configuration depend upon I, that halts (or emits a specified number of spikes in a given interval of time) if and only if Iis a positive instance of Q. On the other hand, a uniform solution of Qconsists in a family {ΠQ(n)}n∈Nof SN P systems such that, when having an instance I ∈ Qof size n, we introduce a polynomial (in n) number of spikes in a designated (set of) input neuron(s) of ΠQ(n)and the computation halts (or, alternatively, a specified number of spikes is emitted in a given interval of time) if and only if Iis a positive instance. The preference for uniform solutions over semi–uniform ones is given by the fact that they are more strictly related to the structure of the problem, rather than to specific instances. If the instances of a problem Q depend upon two parameters (as is the case of SUBSET SUM, where n+1 is the number of integer values of the generic instance (V={v1, v2,...,vn}, S), and kis the number of bits needed to represent each of these values), then we will denote the family of SN P systems that solves Q by {ΠQ(hn, ki)}n,k∈N, where hn, kiindicates the positive integer number obtained by applying an appropriate bijection (for example, Cantor’s pairing) from N2to N. The present paper considers SN P systems for solving decision problems, continuing the papers [15], [16] and [17], where one deals with the NP-complete decision problems SUBSET SUM,SAT and 3-SAT. For all these problems, constant time and polynomial time solutions were provided by using SN P systems constructed both in the semi–uniform and in the uniform setting, working in a non–deterministic way, and also using a series of ingredients added to SN P systems of the standard form: rules that produce several spikes at a time, the possibility to have a choice between spiking rules and forgetting rules, forgetting rules controlled by regular expressions, rules applied in the maximally parallel way, etc. Here we consider a different situation: we assume that a pre–computed (standard) SN P system is given in advance, possibly having an exponential size with respect to the size of the instances of the problem we want to solve, and we provide a semi–uniform and a uniform constructions that solve SUBSET SUM in a polynomial time. All the systems we will propose work in a deterministic way. Note that this setting was already considered in [13], where polynomial time uniform solutions to SAT and 3-SAT were provided. An important observation is that we will not specify how our pre–computed systems could be built. However, we require that such systems have a regular structure, and that they do not contain neither “hidden information” that simplify the solution of specific instances, nor an encoding of all possible A. Leporati, M.A. Guti´errez-Naranjo/Solving SUBSET SUM by Spiking Neural P Systems 5 solutions (that is, an exponential amount of information that allows to cheat while solving the instances of the problem). These requirements were inspired by open problem Q27 in [29]. Let us note in passing that the regularity of the structure of the system is related to the concept of uniformity, that in some sense measures the difficulty of constructing the system. For example, when considering families {C(n)}n∈N of Boolean circuits, or other computing devices whose number of inputs depends upon an integer parameter n≥1, it is required that for each n∈Na “reasonable” description (see [2] for further discussion on the meaning of the term “reasonable” in this context) of C(n), the circuit of the family which has n inputs, can be produced in polynomial time and logarithmic space (with respect to n) by a deterministic Turing machine whose input is 1n, the unary representation of n. In this paper we will not delve further into the details concerning uniformity; we just rely on reader’s intuition, by stating that it should be possible to build the entire structure of the system using only a polynomial amount of information and a controlled replication mechanism, as it already happens in P systems with cell division. The paper is organized as follows. In Section 2 we recall the definition of the SUBSET SUM problem, as well as a classical solution algorithm based on the dynamic programming paradigm. In Section 3 we elaborate such an algorithm to obtain a family of SN P systems that solves SUBSET SUM in a semi– uniform way. In Section 4 we propose a completely different construction, that allows us to uniformly solve all the instances of SUBSET SUM of any specified size; the instances are provided in input to the systems of the family by specifying their values in binary form. Finally, Section 5 contains the conclusions and some directions for further research. 2. The SUBSET SUM Problem SUBSET SUM is one of the most known NP-complete decision problems. We can state it as follows, in a form which is equivalent to the one given in [7, p. 223]. Problem 1. NAME: SUBSET SUM. •INSTANCE: a (multi)set V={v1, v2,...,vn}of positive integer numbers, and a positive integer number S. •QUESTION: is there a sub(multi)set B⊆Vsuch that P b∈B b=S? The following well known algorithm [5] solves SUBSET SUM by using the dynamic programming technique. In particular, the algorithm returns 1on positive instances, and 0on negative instances. SUBSET SUM({v1, v2,...,vn}, S) for j←0to S do M[1, j]←0 M[1,0] ←M[1, v1]←1 for i←2to n do for j←0to S do M[i, j]←M[i−1, j] if j≥viand M[i−1, j −vi]> M[i, j] then M[i, j]←M[i−1, j −vi] 6A. Leporati, M.A. Guti´errez-Naranjo /Solving SUBSET SUM by Spiking Neural P Systems return M[n, S] In order to look for a subset B⊆Vsuch that Pb∈Bb=S, the algorithm uses an n×(S+ 1) matrix M whose entries are from {0,1}. It fills the matrix by rows, starting from the first row. Each row is filled from left to right. The entry M[i, j]is filled with 1if and only if there exists a subset of {v1, v2,...,vi} whose elements sum up to j. The given instance of SUBSET SUM is thus a positive instance if and only if M[n, S] = 1 at the end of the execution. Since each entry is considered exactly once to determine its value, the time complexity of the algorithm is proportional to n(S+ 1) = Θ(nS). This means that the difficulty of the problem depends on the value of S, as well as on the magnitude of the values in V. In fact, let K=max{v1, v2,...,vn, S}. If Kis polynomially bounded with respect to n, then the above algorithm works in polynomial time. On the other hand, if Kis exponential with respect to n, say K= 2n, then the above algorithm may work in exponential time and space. This behavior is usually referred to in the literature by telling that SUBSET SUM is a pseudo–polynomial NP–complete problem. The fact that in general the running time of the above algorithm is not polynomial can be immediately understood by comparing its time complexity with the instance size. The usual size for the instances of SUBSET SUM is Θ(nlog K), since for conciseness every “reasonable” encoding is assumed to represent each element of V(as well as S) using a string whose length is O(log K). Here all logarithms are taken with base 2. Stated differently, the size of the instance is usually considered to be the number of bits which must be used to represent in binary Sand all the integer numbers which occur in V. If we would represent such numbers using the unary notation, then the size of the instance would be Θ(nK). But in this case we could write a program which first converts the instance in binary form and then uses the above algorithm to solve the problem in polynomial time with respect to the new instance size. We can thus conclude that the difficulty of a numerical NP–complete problem depends also on the measure of the instance size we adopt. Indeed, SUBSET SUM is not NP-complete in the strong sense, meaning that it does not remain NP-complete when we represent its instances in unary form [7]. Stated otherwise, strongly NP-complete problems remain NP-complete even when the numbers contained into their instances are small. As a consequence of these observations, the SN P systems that we will consider in Section 4 will take in input the instances of SUBSET SUM as n+ 1 strings encoded in binary form, where the length of each string will be k= log K. Before presenting the uniform solution of Section 4, in the next section we first elaborate the above dynamic programming algorithm to provide a semi–uniform family of SN P systems that solves the SUBSET SUM problem. 3. A Semi–uniform Solution to SUBSET SUM Let SS(n, k)denote the set of instances of SUBSET SUM which can be built by using n+1 positive k-bit integer numbers. In this section we present a semi–uniform family {Π(I)}I∈SS(n,k)of SN P systems such that for every I ∈ SS(n, k)the system Π(I)determines whether I= ({v1, v2,...,vn}, S)is a positive instance of SUBSET SUM. The size of Π(I)will be Θ(nS), hence exponential with respect to the instance size. However, the computation time of Π(I)will be linear in nand independent of k. System Π(I)is depicted in Figure 1 in a schematic way. The system is composed of nlayers, horizontally arranged (note that Figure 1 is rotated by 90 degrees counterclockwise), one for each iteration of the dynamic programming algorithm illustrated in the previous section. The computation starts in A. Leporati, M.A. Guti´errez-Naranjo/Solving SUBSET SUM by Spiking Neural P Systems 7 Figure 1. A schematic view of the system Π(I)used to solve a specific instance I= ({v1, v2,...,vn}, S)of SUBSET SUM, where each of the values v1, v2,...,vn, S is a k-bit positive integer number. 8A. Leporati, M.A. Guti´errez-Naranjo /Solving SUBSET SUM by Spiking Neural P Systems the first (the uppermost) layer, and proceeds downwards until the lowest (i.e., the n-th) layer has been reached. The neurons of the first layer contain the firing rule a→a; 0, that propagates the spikes eventually contained in these neurons to the appropriate neurons of the second layer. All the other neurons, from layer 2 down to layer n, contain two firing rules: a→a; 0 and a2→a; 0 that make the neurons operate like OR Boolean gates. The connections among the neurons depend upon the instance I= ({v1, v2,...,vn}, S)of SUBSET SUM to be solved. Precisely, to determine the value of M[i, j]in the above algorithm we need to compute the maximum between the values M[i−1, j]and M[i−1, j−vi], provided that j−vi≥0, otherwise we put M[i, j]equal to M[i−1, j]. The rationale behind these formulas is the following: as stated above, M[i, j]has to be set to 1if and only if there exists a subset of {v1, v2,...,vi}such that the sum of its elements is equal to j. Thus we have two possibilities: either the subset contains vi, or not. In the former case, there must be a subset of {v1, v2,...,vi−1}such that the sum of its elements is equal to j−vi (that is, M[i−1, j −vi]must be 1); in the latter case, there must be a subset of {v1, v2,...,vi−1}whose elements sum up to j(that is, M[i−1, j] = 1). If j < vithen clearly vicannot be in any subset of {v1, v2, . . . , vi}whose sum is equal to j, and thus in this case we only check the value of M[i−1, j]. If i= 1 then these formulas cannot clearly be applied. However, we note that the only two subsets of {v1} we can build are the empty set ∅and {v1}itself, hence M[1,0] = M[1, v1] = 1 whereas M[1, j] = 0 for all j6∈ {0, v1}. Since the admissible values of M[i−1, j]and of M[i−1, j −vi]are 0and 1, computing the maximum is the same as computing a logical OR. In the system depicted in Figure 1, the j-th neuron from the left, 0≤j≤S, corresponds to M[i, j]. We denote 1(resp., 0) by the presence (resp., absence) of a spike. Such a neuron, for 1≤i≤n, has a synapse going to the neuron that Figure 2. The two cases to be considered to compute the value of M[i, j]. corresponds to M[i+ 1, j], and possibly (if vi+1 +j≤S) another synapse going to the neuron that corresponds to M[i+ 1, j +vi+1]. Such connections implement the above rules that determine the value of M[i, j], as one can easily check by looking at Figure 2 (where the attention is focused on the synapses that start from the (i−1)-th layer and arrive to the neuron that corresponds to M[i, j]). In the last layer, only the neuron that corresponds to M[n, S]has a synapse going to a neuron named out, which is the output neuron and does not contain any rule. A. Leporati, M.A. Guti´errez-Naranjo/Solving SUBSET SUM by Spiking Neural P Systems 9 In the initial configuration of the system, one spike is put in the neurons that correspond to M[1,0] and M[1, v1]; all the other neurons are empty. During the i-th computation step, with 1≤i≤n−1, the neurons in the i-th layer perform their computation, and send the corresponding result to the appropriate neurons of the next layer. At the n-th computation step, all the neurons in the last layer send the spikes produced by them to the environment (where they are lost) but the rightmost neuron, that sends the result of its computation (0or 1spikes) to neuron out. Hence, the instance Iof SUBSET SUM represented by the structure and the initial configuration of Π(I)is positive if and only if one spike arrives in neuron out during the n-th computation step. After the result of the computation (0or 1spikes in neuron out) has been produced, the computation halts and the spike eventually contained in neuron out remains there. The computation time of Π(I)is linear in n, independent of the values v1, v2,...,vnand Scontained in I, but the number of neurons in the system is n(S+ 1) + 1, which is exponential with respect to the instance size. This last fact would be considered unacceptable in traditional complexity theory, but recall that in this paper (as well as in [13]) we are assuming that exponential size resources — encoded in exponential size SN P systems of regular structure — are admitted, provided that they do not contain hidden information that allow to cheat while solving the instances of the problem. The structure of Π(I)is indeed very regular: all the instances composed of ninteger values plus a required sum equal to Sproduce systems having nlayers, each composed of S+ 1 neurons. The values v1, v2,...,vndetermine some of the connections between the neurons (all the other connections go from every neuron in each layer to the neuron that occurs in the same position in the next layer); precisely, for all i∈ {1,2,...,n−1}the value videtermines the presence of a synapse from every j-th neuron in layer i, such that j+vi+1 ≤S, to the (j+vi+1)-th neuron of layer i+ 1. Value v1also determines the neuron in the first layer (apart from the leftmost) that will receive one spike in the initial configuration. An open question, that we will not address in this paper, is: what kind of operations are needed to augment the power of deterministic Turing machines so that, given any instance Iof SUBSET SUM, the new machine is able to produce a “reasonable” description of Π(I)in a polynomial time? Note that in this case we should also recast the meaning of the term “reasonable”, since in [7] this notion concerns only polynomial size constructions. 4. A Uniform Solution to SUBSET SUM Let us present now a uniform family {Π(hn, ki)}n,k∈Nof SN P systems that solves the SUBSET SUM problem in a uniform way. Precisely, for all n, k ∈Nthe system Π(hn, ki)will solve all the instances I ∈ SS(n, k)which are composed of n+ 1 positive k-bit integer numbers. Such instances are provided in input in binary form, as a sequence of (n+1)kbits that are fed to the system in parallel (which means that each bit is inserted into an appropriate input neuron). Figure 3 depicts the system Π(hn, ki)in a schematic way. The instance I ∈ SS(n, k)is inserted into the leftmost neurons, which are labelled with a name that indicates the bit which has to be inserted. These neurons simply propagate their spikes to subsystems SUM1, SUM2,..., SUM2n−1by using a firing rule of type a→a; 0. The SUM subsystems are bijectively associated to every possible non-empty subset of {v1, v2, . . . , vn}. As the name indicates, every SUM subsystem computes the sum of the elements of the corresponding subset of {v1, v2,...,vn}, and thus the synapses outgoing from the leftmost neurons reflect this situation; that is, a synapse leaving from neuron vi,j,1≤i≤nand 1≤j≤k, reaches the subsystem SUMℓif and only if value viis involved in the sum computed by SUMℓ. The sums are 16 A. Leporati, M.A. Guti´errez-Naranjo /Solving SUBSET SUM by Spiking Neural P Systems [9] Guti´errez-Naranjo, M. A., P´erez-Jim´enez, M. J., Riscos-N´u˜nez, A.: A Fast P System for Finding a Balanced 2–partition. Soft Computing,9(9), 2005, 673–678. [10] Ibarra, O. H., P˘aun, A., P˘aun, Gh., Rodr´ıguez-Pat´on,A., Sos´ık, P., Woodworth, S.: Normal Forms for Spiking Neural P Systems, Theoretical Computer Science,372(2–3), 2007, 196–217. [11] Ionescu, M., P˘aun, A., P˘aun, Gh., P´erez-Jim´enez, M. J.: Computing with Spiking Neural P Systems: Traces and Small Universal Systems, DNA Computing, 12th International Meeting on DNA Computing (DNA12), Revised Selected Papers (C. Mao, T. Yokomori, B.-T. Zhang, Eds.), LNCS 4287, Springer-Verlag, Berlin, 2006, 1–16. [12] Ionescu, M., P˘aun, Gh., Yokomori, T.: Spiking Neural P Systems, Fundamenta Informaticae,71(2-3), 2006, 279–308. [13] Ishdorj, T.-O., Leporati, A.: Uniform Solutions to SAT and 3-SAT by Spiking Neural P Systems with Precomputed Resources, Natural Computing, in press, DOI 10.1007/s11047-008-9081-0.A preliminary version appeared as Turku Centre for Computer Science – TUCS Report No. 876, 2008. [14] Krishna, S. N., Rama, R.: A Variant of P Systems with Active Membranes: Solving NP-complete Problems, Romanian Journal of Information Science and Technology,2(4), 1999, 357–367. [15] Leporati, A., Mauri, G., Zandron,C., P˘aun, Gh., P´erez-Jim´enez, M. J.: UniformSolutionsto SAT and SUBSET SUM by Spiking Neural P Systems, submitted. [16] Leporati, A., Zandron,C., Ferretti, C., Mauri, G.: On the Computational Power of Spiking Neural P Systems, Intern. J. Unconventional Computing, 2007, in press. [17] Leporati, A. Zandron,, C., Ferretti, C., Mauri, G.: Solving Numerical NP–complete Problems with Spiking Neural P Systems, Membrane Computing, International Workshop, WMC8, Selected and Invited Papers, (G. Eleftherakis, P. Kefalas, Gh. P˘aun, G. Rozenberg, A. Salomaa, Eds.), LNCS 4860, Springer-Verlag, Berlin, 2007. 336–352. [18] Leporati, A., Zandron, C., Guti´errez-Naranjo, M. A.: P Systems with Input in Binary Form, International Journal of Foundations of Computer Science,17(1), 2006, 127–146. [19] Maass, W.: Computing with spikes, Special Issue on Foundations of Information Processing of TELEMATIK, 8(1), 2002, 32–36. [20] Maass, W., Bishop, C. (Eds.), Pulsed Neural Networks, MIT Press, Cambridge (MA), 1999. [21] Mart´ın Vide, C., Pazos, J., P˘aun, Gh., Rodr´ıguez Pat´on, A.: A New Class of Symbolic Abstract Neural Nets: Tissue P Systems, Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, LNCS 2387, Springer-Verlag, Berlin, 2002, 290–299. [22] Mart´ın Vide, C., Pazos, J., P˘aun, Gh., Rodr´ıguez Pat´on, A.: Tissue P systems, Theoretical Computer Science, 296, 2003, 295–326. [23] Obtulowicz, A: Deterministic P Systems for Solving SAT problem, Romanian Journal of Information Science and Technology,4(1–2), 2001, 551–558. [24] Papadimitriou, C. H.: Computational Complexity, Addison-Wesley, 1994. [25] P˘aun, A., P˘aun, Gh.: Small Universal Spiking Neural P Systems, BioSystems,90(1), 2007, 48–60. [26] P˘aun, Gh.: Computing with Membranes, Journal of Computer and System Sciences,1(61), 2000, 108–143. See also Turku Centre for Computer Science – TUCS Report No. 208, 1998. [27] P˘aun, Gh.: Computing with Membranes. An Introduction, Bulletin of the EATCS,67, 1999, 139–152. A. Leporati, M.A. Guti´errez-Naranjo/Solving SUBSET SUM by Spiking Neural P Systems 17 [28] P˘aun, Gh.: P Systems with Active Membranes: Attacking NP-complete Problems, Journal of Automata, Languages and Combinatorics,6(1), 2001, 75–90. [29] P˘aun, Gh.: Membrane Computing. An Introduction, Springer–Verlag, Berlin, 2002. [30] P˘aun, Gh., P´erez-Jim´enez, M. J., Rozenberg, G.: Infinite spike trains in spiking neural P systems, submitted. [31] P˘aun, Gh., Rozenberg, G.: A Guide to Membrane Computing, Theoretical Computer Science,287(1), 2002, 73–100. [32] P˘aun, Gh., Sakakibara, Y., Yokomori, T.: P Systems on Graphs of Restricted Forms, Publicationes Mathematicae Debrecen,60, 2002, 635–660. [33] P´erez-Jim´enez, M. J., Riscos-N´u˜nez, A.: A Linear–time Solution to the KNAPSACK Problem Using P Systems with Active Membranes, Membrane Computing, International Workshop, WMC 2003, Revised Selected and Invited Papers (C. Mart´ın-Vide, Gh. P˘aun, G. Rozenberg, A. Salomaa, Eds.), LNCS 2933, SpringerVerlag, Berlin, 2004, 250–268. [34] P´erez-Jim´enez, M. J., Riscos-N´u˜nez, A.: Solving the SUBSET SUM Problem by Active Membranes, New Generation Computing,23(4), 2005, 367–384. [35] Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach, Springer–Verlag, Berlin, 1999. [36] Zandron, C., Ferretti, C., Mauri, G.: Solving NP-complete Problems Using P Systems with Active Membranes, Unconventional Models of Computation (I. Antoniou, C.S. Calude, M.J. Dinneen, Eds.), SpringerVerlag, Berlin, 2000, 289–301. [37] The P systems Web page: http://ppage.psystems.eu