On the Computational Power of Spiking Neural P Systems

On the Computational Power of Spiking Neural P Systems Alberto Leporati, Claudio Zandron, Claudio Ferretti, Giancarlo Mauri Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano – Bicocca Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy {leporati,zandron,ferretti,mauri}@disco.unimib.it Summary. In this paper we study some computational properties of spiking neural P systems. In particular, we show that by using nondeterminism in a slightly extended version of spiking neural P systems it is possible to solve in constant time both the numerical NP–complete problem Subset Sum and the strongly NP–complete problem 3-SAT. Then, we show how to simulate a universal deterministic spiking neural P system with a deterministic Turing machine, in a time which is polynomial with respect to the execution time of the simulated system. Surprisingly, it turns out that the simulation can be performed in polynomial time with respect to the size of the description of the simulated system only if the regular expressions used in such a system are of a very restricted type. 1 Introduction Membrane systems (also called P systems) were introduced in [16] as a new class of distributed and parallel computing devices, inspired by the structure and functioning of living cells. The basic model consists of a hierarchical structure composed by several membranes, embedded into a main membrane called the skin. Membranes divide the Euclidean space into regions, that contain some objects (represented by symbols of an alphabet) and evolution rules. Using these rules, the objects may evolve and/or move from a region to a neighboring one. Usually, the rules are applied in a nondeterministic and maximally parallel way; moreover, all the objects that may evolve are forced to evolve. A computation starts from an initial configuration of the system and terminates when no evolution rule can be applied. The result of a computation is the multiset of objects contained into an output membrane, or emitted from the skin of the system. For a systematic introduction to P systems we refer the reader to [18], whereas the latest information can be found in [23]. 228 A. Leporati et al. In an attempt to pass from cell-like to tissue-like architectures, in [13] tissue P systems were defined, in which cells are placed in the nodes of a (directed) graph. Since then, this model has been further elaborated, for example, in [4] and [19], with recent results about both theoretical properties [1] and applications [14]. This evolution has led to explore also neural-like architectures, yielding to the introduction of spiking neural P systems (SN P systems, for short) [8], based on the neurophysiological behavior of neurons sending electrical impulses (spikes) along axons to other neurons. We recall that this biological background has already led to several models in the area of neural computation, e.g., see [11, 12, 6]. Similarly to tissue P systems, in SN P systems the cells (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. The firing rules assigned to a cell 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 application of the rules depends on the contents of the neuron; in the general case, applicability is determined by checking the contents of the neuron against a regular set associated with the rule. As inspired from biology, after 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 of biological 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. In the original model of SN P systems defined in [8], computations occur as follows. A configuration specifies, for each neuron of the system, the number of spikes it contains and the number of computation steps after which the neuron will become “open” (that is, not closed). Starting from an initial configuration, a positive integer number is given in input to a specified input neuron. 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 is executed. The computation proceeds in a sequential way into each neuron, and in parallel among different neurons. 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. Defined in this way, SN P systems compute functions of the kind f:N→N(they can also indirectly compute functions of the kind f:Nk→Nby using a bijection from Nkto N). By ignoring the output neuron we can define accepting SN P systems, in which the natural number given in input is accepted if the computation halts, and rejected otherwise. On the other hand, by ignoring the input neuron (and thus starting from a predefined input configuration) we can define generative SN P systems. On the Computational Power of SN P Systems 229 In [8] 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 also be obtained with even more restricted forms of spiking P systems; for example, [7] shows that at least one of these features can be avoided while keeping universality: time delay (refractory period) greater than 0, forgetting rules, outdegree of the synapse graph greater than 2, and regular expressions of complex form. Finally, in [20] the behavior of spiking neural P systems on infinite strings and the generation of infinite sequences of 0 and 1 was investigated, whereas in [2] spiking neural P systems were studied as language generators (over the binary alphabet {0,1}). The rest of this paper is organized as follows. In section 2 we give some mathematical preliminaries, and we define the standard version of SN P systems (as found in [9]) as well as a slightly extended version. In section 3 we show how the NP–complete problems Subset Sum and 3-SAT can be solved in constant time by exploiting nondeterminism in our extended SN P systems. In section 4 we turn our attention to deterministic systems, and we show how to simulate them by using deterministic Turing machines. Section 5 concludes the paper and gives some directions for future research. 2 Preliminaries Let us start by recalling the standard definition of a spiking neural P system, taken from [9]. A spiking neural membrane system (SN P system, for short), of degree m≥1, 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), with 1 ≤i≤m, where: a) ni≥0 is the initial number of spikes contained in σi; b) Riis a finite set of rules of the following two forms: (1) E/ac→a;d, where Eis a regular expression over a, and c≥1, d≥0 are integer numbers; if E=ac, then it is usually written in the following simplified form: ac→a;d; (2) as→λ, for s≥1, with the restriction that for each rule E/ac→a;dof type (1) from Ri, we have as6∈ L(E) (where L(E) denotes 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 Π. 230 A. Leporati et al. The rules of type (1) are called firing (also spiking)rules, and they are applied as follows. If the neuron σicontains k≥cspikes, and ak∈L(E), then the rule E/ac→a;d∈Rican be applied. 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, otherwhise it is emitted afted dcomputation steps of the system. (Observe that, as usually happens in membrane computing, a global clock is assumed, marking the time for the whole system, hence the functioning of the system is synchronized.) If the rule is used in step tand d≥1, then in steps t, t + 1, t + 2, . . . , t +d−1 the neuron is closed, so that 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 new rules. In the step t+d, the neuron spikes and becomes again open, so that it can receive spikes (which can be used starting with the step t+d+ 1) and select rules to be fired. Rules of type (2) are called forgetting rules, and are applied as follows: if the neuron σicontains exactly sspikes, then the rule as→λfrom Rican be used, meaning that all sspikes are removed from σi. Note that, by definition, if a firing rule is applicable, then no forgetting rule is applicable, and vice versa. In each time unit, if a neuron σican use one of its rules, then a rule from Ri must be used. Since two firing rules, E1:ac1→a;d1and E2:ac1→a;d2, can have L(E1)∩L(E2)6=∅, it is possible that two or more rules can be applied in a neuron. In such a case, only one of them is chosen nondeterministically. Thus, the rules are used in the sequential manner in each neuron, but neurons function in parallel with each other. 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 number of spikes present in each neuron and by the state of each neuron, which can be expressed as the number of steps to count down until it becomes open (this number is zero if the neuron is already open). A computation in a system as above starts in the initial configuration. In order to compute a function f:Nk→N, we introduce k natural numbers n1, n2,...,nkin the system by “reading” from the environment a binary sequence z= 0b10n110n21...10nk10g, for some b, g ≥0; this means that the input neuron of Πreceives a spike in each step corresponding to a digit 1 from the string z. Note that we input exactly k+ 1 spikes. The result of the computation is also encoded in the distance between two spikes: we impose to the system to output exactly two spikes and halt (sometimes after the second spike) hence producing a train spike of the form 0b010r10g0, for some b0, g0≥0 and with r=f(n1, n2,...,nk). If we use an SN P system in the generative mode, then no input neuron is considered, hence no input is taken from the environment; we start from the initial configuration, and the distance between the first two spikes of the output neuron (or other numbers, see the discussion in [9]) is the result of the computation. On the Computational Power of SN P Systems 231 Dually, we can ignore the output neuron, and if the computation halts, then the number is accepted. We define the description size of an SN P system Πas the number of bits which are necessary to describe it. Since the alphabet Ois fixed, no bits are necessary to define it. In order to represent syn we need at most m2bits, whereas we can represent the values of in and out by using log mbits each. Every neuron σirequires to specify a natural number ni, and a set Riof rules. Each rule requires to specify its type (firing or forgetting), which can be done with 1 bit, and in the worst case it requires to specify a regular expression and two natural numbers. If we denote by Nthe maximum natural number that appears in the definition of Π,Rthe maximum number of rules which occur in its neurons, and Sthe maximum size required by the regular expressions that occur in Π(more on this later), then we need a maximum of log N+R(1+S+ 2 log N) bits to describe every neuron of Π. Hence, to describe Πwe need a total of m2+2 log m+mlog N+R(1+S+2 logN) bits. Note that this quantity is polynomial with respect to m,R,Sand log N. Since the regular languages determined by the regular expressions that occur in the system are unary languages, the strings of such languages can be bijectively identified by their lengths. Hence, when writing the regular expression E, instead of writing unions, concatenations and Kleene closures among strings we can do the same by using the lengths of such strings. In this way we obtain a representation of Ewhich is exponentially more compact than the usual representation of regular expressions. As we will see in section 4, this compact representation will yield some difficulties when we will simulate a deterministic accepting SN P system by a deterministic Turing machine. In what follows it will be convenient to consider also a slightly extended version of SN P systems. Precisely, we will allow rules of the type E/ac→ap;d, where c≥1, p≥0 and d≥0 are integer numbers. The semantics of this kind of rules is as follows: if the contents of the neuron matches the regular expression E, then the rule can be applied. When the rule is applied, cspikes are removed from the contents of the neuron and pspikes are prepared to be delivered to all the neurons which are directly connected (through an arc of syn) with the current neuron. If d= 0, then these pspikes are immediately sent, otherwise the neuron becomes closed for the next dcomputation steps, after which the pspikes will be sent. As before, a closed neuron does not receive spikes from other neurons, and does not apply any rule. If p= 0, then we obtain a forgetting rule as a particular case of our general rules. Also in the extended SN P systems it may happen that, given two rules E1/ac1→ap1;d1and E2/ac2→ap2;d2, if L(E1)∩L(E2)6=∅then for some contents of the neuron both the rules can be applied. In such a case, we nondeterministically choose one of them. Note that we do not require that forgetting rules are applied only when no firing rule can be applied. We say that the system is deterministic if, for every neuron that occurs in the system, any two rules E1/ac1→ap1;d1 and E2/ac2→ap2;d2in the neuron are such that L(E1)∩L(E2) = ∅. This means 232 A. Leporati et al. that, for any possible contents of the neuron, at most one of the rules that occur in the neuron may be applied. By using an input neuron and an output neuron, we have SN P systems that compute functions of the kind f:N→N, and hence we cover both the generative and the accepting cases. If out = 0, then it is understood that the output is sent to the environment (as the number of spikes produced by the system, as the distance between the first two spikes, etc.). As usual, to use an SN P system in the generative mode we do not consider the input neuron, and thus no input is taken from the environment; we start from the initial configuration, and the distance between the first two spikes of the output neuron (or the number of spikes contained into the output neuron at the end of the computation, as discussed above) is the result of the computation. Note that generative SN P systems are inherently nondeterministic, otherwise they would always reproduce the same sequence of computation steps, and hence the same output. Dually, we can ignore the output neuron to obtain an accepting SN P system. We input a number in the system as the distance between two spikes entering the input neuron (or the number of spikes that occur in the input neuron in the initial configuration) and, if the computation halts, then the number is accepted. The description size of an extended SN P system is defined exactly as we did for standard systems, the only difference being that now we require (at most) three natural numbers to describe a rule. 3 Solving NP–complete Problems with Extended Spiking Neural P Systems In this section we show that nondeterministic SN P systems are very powerful computing devices, at least in the extended version defined in the previous section: in fact, they are able to solve NP–complete problems in a constant number of computation steps. 3.1 Solving the Subset Sum problem Let us first consider the Subset Sum problem, which can be stated as follows. 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 subset B⊆Vsuch that P b∈B b=S? If we allow to nondeterministically choose among the rules which occur in the neurons, then the extended SN P system depicted in Figure 1 solves any given instance of Subset Sum in a constant number of steps. We emphasize the fact On the Computational Power of SN P Systems 233 Fig. 1. A nondeterministic extended SN P system that solves the Subset Sum problem in constant time that such a solution occurs in the semi-uniform setting, that is, for every instance of Subset Sum we build an SN P system that specifically solves that instance. Let (V={v1, v2,...,vn}, S) be the instance of Subset Sum to be solved, and let B⊆V. In the initial configuration of the system, the leftmost neurons contain (from top to bottom) v1, v2,...,vnspikes, respectively, whereas the rightmost neurons contain zero spikes each. In the first step of computation, in each of the leftmost neurons of the SN P system depicted in Figure 1 it is nondeterministically chosen whether to include or not the element viin B; this is accomplished by nondeterministically choosing among one rule that forgets vispikes (in such a case, vi6∈ B) and one rule that propagates vispikes to the rightmost neurons. At the beginning of the second step of computation a certain number Nof spikes, that corresponds to the sum of the viwhich have been chosen, occurs in the rightmost neurons. We have three possible cases: •N < S: in this case neither the rule aS→a; 0 nor the rule aS+1 →a; 1 (which occur in the neuron at the top and at the bottom of the second layer, respectively) fire, and thus no spike is emitted to the environment; •N=S: only the rule aS→a; 0 fires, and emits a single spike to the environmnent. No further spikes are emitted; •N > S: both the rules aS→a; 0 and aS+1 →a; 1 fire. The first rule immediately sends one spike to the environment, whereas the second rule sends another spike at the next computation step (due to the delay associated with the rule). 234 A. Leporati et al. Hence, by counting the number of spikes emitted to the environment at the second and third computation steps we are able to read the solution of the given instance of Subset Sum: the instance is positive if and only if a single spike is emitted. The formal definition of the extended (generating) SN P system depicted in Figure 1 is as follows: Π= ({a}, σ1,...,σn+2, syn, out), where: •σi= (vi,{avi→λ, avi→avi; 0}) for all i∈ {1,2,...,n}; •σn+1 = (0,{aS→a; 0}); •σn+2 = (0,{aS+1 →a; 1); •syn =Sn i=1{(i, n + 1),(i, n + 2)}; •out = 0 indicates that the output is sent to the environment. However, here we are faced with a problem that we have already encountered in [10], and that we will encounter again in the rest of the paper. In order to clearly expose the problem, let us consider the following algorithm that solves Subset Sum using the well-known Dynamic Programming technique [3]. In particular, the algorithm returns 1 on positive instances, and 0 on 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] 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 Mwhose 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 1 if 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 works in exponential time and space. This behavior is usually On the Computational Power of SN P Systems 235 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. The problem we mentioned above about the SN P system depicted in Figure 1 is that the rules avi→λand avi→avi; 0 which occur in the leftmost neurons, as well as those that occur in the rightmost neurons, check for the existence of a number of spikes which is exponential with respect to the usually agreed instance size of Subset Sum. Moreover, to initialize the system the user has to place a number of objects which is also exponential. This is not fair, because it means that the SN P system that solves the NP–complete problem has an exponential size with respect to the binary string which is used to describe it; an exponential effort is thus needed to build the system, that easily solves the problem by working in unary notation (hence in polynomial time with respect to the size of the system, but not with respect to its description size). This problem is in some aspects similar to what has been described in [10], concerning traditional P systems that solve NP–complete problems. 3.2 The 3-SAT problem In this section we show that SN P systems are also able to solve non-numerical NP–complete problems. Such problems are inherently strongly NP–complete, that is, they remain NP–complete even if the numbers eventually contained into the instance are expressed in unary form. Specifically, we first propose a simple extended SN P system that solves 3-SAT, and then we show that also standard SN P systems are able to solve this problem. We start by recalling some well known definitions, in order to settle the notation. A boolean variable is a variable which can assume one of two possible truth values: true and false. As usually done in the literature, we will denote true by 1 and false by 0. A literal is either a directed or a negated boolean variable. Aclause is a disjunction of literals, whereas a 3-clause is a disjunction of exactly three literals. Given a set X={x1, x2,...,xn}of boolean variables, an assignment is a mapping a:X→ {0,1}that associates to each variable a truth value. The 242 A. Leporati et al. Thus, a step of the spiking phase requires O(mlog D)·m·(m2+ log D+ log(w+ tQm))=O(m2log D)(m2+ log D+ log(w+tQm))steps. The total time required to simulate tsteps of Πis thus ttimes the time needed to perform the two phases, that is, t·O(m(Z+ log(w+tQm) + log Q+ log D)) + O(m2log D)(m2+ log D+ log(w+tQm)). To show that this time is polynomial with respect to the description size of the system Π, we need to explicit the time Zrequired to select which rule has to be applied in neuron σi. We stress the fact that, since the system Πis deterministic, at each computation step there is at most one rule in σiwhich can fire. In order to select such a rule, we need to check whether there are enough spikes in the neuron (and clearly this can be done in polynomial time), as well as to check if ni∈L(Ei). In general, this last operation cannot be done in polynomial time, as it will be proved in the next proposition. Nonetheless, in [9] it is shown that universality can be obtained by using SN P systems where the regular expressions associated with each rule are of very simple forms: ai, with i≤3, or a(aa)+. Considering such systems, it is easy to see that the time required to check if the contents of σiis in the regular set defined by the regular expression can be done in polynomial time, since in the former case it suffices to check if the number is equal to i(time proportional to log ni), whereas in the latter case it suffices to check the last bit of ni. Thus, the time required to select the rule to apply depends on the number of rules in each neuron. That is, Zi=O(|Ri|) = O(r), where r= max1≤i≤m|Ri|is the maximum number of rules which can be contained in a neuron. As a consequence, the total time required to simulate tsteps of Πis t·O(m(r+ log(w+tQm) + log Q+ log D)) + O(m2log D)(m2+ log D+O(log(w+tQm)). We conclude this section by stressing that the above simulation could be performed in polynomial time because the regular expressions used in the rules are of a very restricted form. Indeed, there is a large amount of computational power hidden into the implicit mechanism that SN P systems use to decide whether a given rule can be applied or not, as proved in the following proposition. The difficulty of checking whether the contents of a neuron is into the regular set determined by the regular expression Eof the rule is induced by the fact that we are dealing with unary languages. As told above, in these languages a string is uniquely determined by its length. Hence, a compact representation of the string is obtained by writing (in binary) its length, rather than by writing the string itself. This is an exponentially smaller representation, and consequently all the problems defined upon this representation become harder, as it happens for all “succint” representations (see [15], chapter 20). Concerning the succint version of the membership problem (is a given string into the language generated by E?) we can prove the following proposition. Proposition 1. Let Πbe an SN P system having a single neuron, that contains the rule E:ac→a;d, where c≥1and d≥0are natural numbers, and E is any regular expression (for a unary language defined on the alphabet {a}). If E On the Computational Power of SN P Systems 243 is described in a succint form, then deciding whether this rule can be applied is at least NP–complete. Proof. Let us show a polynomial time reduction from Subset Sum to this problem. Let (V={v1, v2,...,vn}, S) be an instance of Subset Sum. If we put K= max{v1, v2,...,vn, S}, then the instance size is Θ(nK), as discussed in section 3.1. Consider the regular expression E=E1◦E2◦...◦En, where Ei= (λ∪{avi}), with λthe symbol that represents the empty word. Since we are dealing with unary languages in succint form, every string of L(E) can be uniquely determined by its length, and thus we can write L(Ei) = {0, vi}.L(E) is just obtained by performing a language theoretic concatenation among the languages L(Ei): L(E) = L(E1)◦ L(E2)◦...◦L(En). Clearly, the regular expression Ecan be represented using a string whose length is polynomial with respect to the size of the given instance of Subset Sum. It is immediately verified that L(E) contains 2nelements, bijectively associated with the subsets of V. Moreover, aS∈L(E) if and only if there exists a set B⊆Vsuch that Pb∈Bb=S. Hence, checking whether aSis in L(E) or not is equivalent to solve the Subset Sum problem on the given instance (V, S). 5 Conclusions and Directions for Future Research In this paper we have started to study the computational power of spiking neural P systems. In particular, by slightly extending the original definition given in [8] and [9] we have shown that by exploiting nondeterminism it is possible to solve NP–complete problems such as Subset Sum and 3-SAT. Concerning deterministic systems, we have shown that the universal deterministic SN P systems defined in [8, 9] can be simulated by deterministic Turing machines with a polynomial slowdown. Surprisingly, this was possible only because the universal P systems described in [8, 9] use regular expressions of a very restricted form. In fact, it was shown that if we allow the use of general regular expressions then we can exploit the mechanism used by SN P systems to decide whether the contents of a neuron matches a regular expression to solve the NP– complete problem Subset Sum. Further research is needed to fully understand the power of accepting SN P systems. In particular, by encoding their inputs as the distance between subsequent spikes we are limiting ourselves to use numbers expressed in unary notation. A more compact way to encode a k-bit natural number nwould be to send a sequence of spikes during a prefixed sequence of kcomputation steps: the presence of a spike indicates a 1, its absence indicates a 0. It is not currently known whether in this way SN P systems can still solve numerical NP–complete problems such as Subset Sum, or whether a subsystem that converts integer numbers from binary to unary notation can be designed, as it was made in [10] for traditional P systems. 244 A. Leporati et al. Acknowledgments We gratefully thank Gheorghe P˘aun for introducing the authors to the stimulating subject of spiking neural P systems, and for asking us a “Milano theorem” (in the spirit of [22]) about their computational power, during the Fifth Brainstorming Week on Membrane Computing, held in Seville from January 29th to February 2nd, 2007. Moreover, we are really indebted with him for suggesting us the standard nondeterministic SN P system that solves 3-SAT, exposed in section 3. References 1. A. Alhazov, R. Freund, M. Oswald: Cell/symbol complexity of tissue P systems with symport/antiport rules. Intern. J. Found. Computer Sci., 17, 1 (2006), 3–26. 2. H. Chen, R. Freund, M. Ionescu, Gh. P˘aun, M.J. P´erez-Jim´enez: On string languages generated by spiking neural P systems. In: M.A. Guti´errez-Naranjo, Gh. P˘aun, A. Riscos-N´u˜nez, F.J. Romero-Campero, eds., Fourth Brainstorming Week on Membrane Computing, Vol. I RGCN Report 02/2006, Research Group on Natural Computing, Sevilla University, F´enix Editora, 169–194. 3. T.H. Cormen, C.H. Leiserson, R.L. Rivest: Introduction to Algorithms. MIT Press, Boston, 1990. 4. R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez: Tissue-like P systems with channel states. Theoretical Computer Science, 330 (2004), 101–116. 5. M.R. Garey, D.S. Johnson: Computers and Intractability. A Guide to the Theory on NP–Completeness. W. H. Freeman and Company, 1979. 6. W. Gerstner, W. Kistler: Spiking Neuron Models. Single Neurons, Populations, Plasticity. Cambridge University Press, 2002. 7. O.H. Ibarra, A. P˘aun, Gh. P˘aun, A. Rodr´ıguez-Pat´on, P. Sos´ık, S. Woodworth: Normal forms for spiking neural P systems. Theoretical Computer Science, 372, 2-3 (2007), 196–217. 8. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2-3 (2006), 279–308. 9. M. Ionescu, A. P˘aun, Gh. P˘aun, M.J. P´erez-Jim´enez: Computing with spiking neural P systems: traces and small universal systems. In C. Mao, T. Yokomori, eds., DNA Computing, 12th International Meeting on DNA Computing, DNA12, Seoul, Korea, June 5-9, 2006, Revised Selected Papers. LNCS 4287, Springer, 2006, 1–16. 10. A. Leporati, C. Zandron, M.A. Guti´errez-Naranjo: P systems with input in binary form. International Journal of Foundations of Computer Science, 17, 1 (2006), 127– 146. 11. W. Maass: Computing with spikes. Special Issue on Foundations of Information Processing of TELEMATIK, 8, 1 (2002), 32–36. 12. W. Maass, C. Bishop (eds.). Pulsed Neural Networks, MIT Press, Cambridge (MA), 1999. 13. C. Mart´ın-Vide, J. Pazos, Gh. P˘aun, A. Rodr´ıguez-Pat´on: A new class of symbolic abstract neural nets: Tissue P systems. In Proceedings of COCOON 2002, Singapore, LNCS 2387, Springer-Verlag, Berlin, 290–299. 14. M. Oswald: Independent agents in a globalized world modelled by tissue P systems. Conf. Artificial Life and Robotics, 2006. On the Computational Power of SN P Systems 245 15. C.H. Papadimitriou: Computational Complexity, Addison-Wesley, 1994. 16. Gh. P˘aun: Computing with membranes. Journal of Computer and System Sciences, 61 (2000), 108–143. See also Turku Centre for Computer Science — TUCS Report No. 208, 1998. Available at: http://www.tucs.fi/Publications/techreports/TR208.php 17. Gh. P˘aun: Computing with membranes. An Introduction. Bulletin of the EATCS, 67 (2/1999), 139–152. 18. Gh. P˘aun: Membrane Computing. An Introduction. Springer–Verlag, Berlin, 2002. 19. Gh. P˘aun, Y. Sakakibara, T. Yokomori: P systems on graphs of restricted forms. Publicationes Mathematicae Debrecen, 60 (2002), 635–660. 20. Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg: Infinite spike trains in spiking neural P systems. Submitted for publication. 21. G. P˘aun, G. Rozenberg: A guide to membrane computing. Theoretical Computer Science, 287, 1 (2002), 73–100. 22. C. Zandron, C. Ferretti, G. Mauri: Solving NP–complete problems using P systems with active membranes. In I. Antoniou, C.S. Calude, M.J. Dinneen, eds., Unconventional Models of Computation, Springer-Verlag, London, 2000, 289–301. 23. The P systems Web page: http://psystems.disco.unimib.it/