On Complexity Classes of Spiking Neural P Systems

On Complexity Classes of Spiking Neural P Systems Alfonso Rodr´ıguez-Pat´on1, Petr Sos´ık1,2, Ludˇek Cienciala2 1Departamento de Inteligencia Artificial, Facultad de Inform´atica, Universidad Polit´ecnica de Madrid, Campus de Montegancedo s/n, Boadilla del Monte, 28660 Madrid, Spain 2Institute of Computer Science, Faculty of Philosophy and Science, Silesian University in Opava, 74601 Opava, Czech Republic Summary. A sequence of papers have been recently published, pointing out various intractable problems which may be solved in certain fashions within the framework of spiking neural (SN) P systems. On the other hand, there are also results demonstrating limitations of SN P systems. In this paper we define recognizer SN P systems providing a general platform for this type of results. We intend to give a more systematic characterization of computational power of variants of SN P systems, and establish their relation to standard complexity classes. 1 Introduction The spiking neural P systems, incorporating in membrane computing ideas from spiking neurons, see, e.g., [18], were introduced in [12]. In short, an SN P system consists of a set of neurons placed in the nodes of a graph, representing synapses. The neurons send signals (spikes) along synapses (edges of the graph). This is done by means of firing rules, which are of the form E/ac→a;d, where Eis a regular expression, cis the number of spikes consumed by the rule, and dis the delay from firing the rule and emitting the spike. The rule can be used only if the number of spikes collected by the neuron is “covered” by expression E, in the sense that the current number of spikes in the neuron, n, is such that an∈L(E), where L(E) is the language described by expression E. In the interval between firing a rule and emitting the spike, the neuron is closed/blocked, it does not receive other spikes and cannot fire again. There also are rules for forgetting spikes, of the form as→λ (sspikes are just removed from the neuron). Starting from an initial distribution of spikes in the neurons and using the rules in a synchronized manner (a global clock is assumed), the system evolves. A sequence of transitions among configurations of an SN P system, starting in the initial configuration, is called a computation. One of the neurons is designated as the output neuron and its spikes can also exit 268 A. Rodr´ıguez-Pat´on, P. Sos´ık, L. Cienciala the system. The sequence of steps when the output neuron sends spikes to the environment is called the spike train of the computation. In section 3.2 we propose a definition of (uniform) families of recognizer SN P systems which should be still more elaborated in the future work. Then we use this apparatus to study the computational power of deterministic (or, more generally, confluent) SN P systems under the following conditions: general regular expressions / single-star normal form, polynomial / exponential number of activated neurons, polynomial uniformity / non-uniformity by Turing machines, cyclic / acyclic architecture. Main theoretical tools we use to study these topics are logic circuits and RAM computers which can simulate SN P systems in a convenient way. 2 Prerequisites We assume the reader to be familiar with basic language and automata theory, as well as with basic membrane computing, e.g., from [22] and [26], respectively (we also refer to [21] for an up-to-date information about membrane computing), so that we introduce here only some notation used later in proofs. For an alphabet V,V∗denotes the set of all finite strings of symbols from V, the empty string is denoted by λ, and the set of all nonempty strings over Vis denoted by V+. When V={a}is a singleton, then we write simply a∗and a+ instead of {a}∗,{a}+. The length of a string x∈V∗is denoted by |x|. For definitions of boolean circuits we refer the reader to [2]. Let UCKT(C(n), D(n)),where C(n)≥n, denote the class of problems solvable by logspace-uniform circuit families with unbounded fan-in where element corresponding to nhas size O(C(n)) and depth O(D(n)). 2.1 Regular expressions and normal forms We recall the definition of regular expression mostly in order to fix the notation. Definition 1. For a finite alphabet V:(i) λand each a∈Vare regular expressions, (ii) if E1, E2are regular expressions over V, then also (E1)∪(E2),(E1)(E2), and (E1)∗are regular expressions over V, and (iii) nothing else is a regular expression over V. The catenation operator ·and non-necessary parentheses may be omitted when writing a regular expression. With each expression Ewe associate its language L(E) defined in a usual way. We call two expressions E1and E2equivalent if L(E1) = L(E2). On Complexity Classes of Spiking Neural P Systems 269 Definition 2 ([1]). We say that a regular expression E=E1∪. . . ∪En(where each Eicontains only ·and ∗operators) is in single-star normal form (SSNF) if ∀i∈ {1, . . . , n}, Eihas at most one occurrence of ∗. Lemma 1 ([1]). Every regular expression over one-letter alphabet can be transformed into an equivalent single-star normal form. This transformation, however, might require an exponential time and the size of the resulting expression can be exponential with respect to the size of the original expression. 2.2 Random Access Machines RAM is a computing device with an infinite random access array of data registers M1, M2,...,each of which can store an arbitrary integer, and with a set of labelled instructions P={P1, P2, . . .}each from the instruction set described below. constant −→ Mres Mop1−→ Mres ∗Mop1−→ Mres The contents of a register whose address is stored in register Mop - indirect memory READ Mop1−→ ∗Mres The contents of a register Mop is written into the register whose address is in register Mres - indirect memory WRITE Mop1+Mop2−→ Mres Mop1−Mop2−→ Mres GOTO label GOTO label if Mop1@Mop2@∈ {=, <} HALT Non-deterministic RAM is defined in the same manner as its deterministic version except that more than one instruction can have the same label and their choice is non-deterministic. A parallel RAM (PRAM) has a sequence of RAM’s R1, R2, . . . operating synchronously in parallel. They all have their own local registers and they can read and write to common registers too. This can be done by indirect memory READ or WRITE. In CRCW PRAM (concurrent-read, concurrent-write) if more than one processor attempts to write into the same location in common memory at the same time, the lowest numbered processor succeeds. All processors run the same program. In addition to the programs, another part of specification of a particular CRCW PRAM is a function P(n) from positive integers to positive integers called the processor bound. An input of size nconsists of nbinary words, each of length at most n. A CRCW PRAM is given an input of size nby placing nwords in the first nlocations of common memory, and the first P(n) processors R1, . . . , RP(n) 270 A. Rodr´ıguez-Pat´on, P. Sos´ık, L. Cienciala are started. Each instruction takes one time unit. The computation halts when R1, . . . , RP(n)have all halted. The machine operates in time T(n) if it halts within T(n) steps on every input of size n. When the computation halts, the output can be found in initial contiguous block of common memory of length at most n. The model is essentially identical to the SIMDAG of Goldschlager [8] and similar to the P-RAM of Fortune and Wyllie [7]. Note that [8] and [7] characterized the power of these models when the number of processors grows exponentially in n. Denote by CRCW(P(n), T(n)) the class of problems solvable on CRCW PRAM in O(T(n)) time with O(P(n)) processors. It is known that CRCW(poly(n), poly(n)) = Pwhile CRCW(exp(n), poly(n)) = PSPACE. Lemma 2 ([28]). CRCW(P(n), T(n)) ⊆UCKT(poly(P(n), T(n), n), T(n)) The above result was presented first in [28] where also its detailed proof together with constructions of logical circuits implementing PRAM can be found. The formulation in Lemma 2 is inspired by [14]. 3 Spiking Neural P Systems Aspiking neural membrane system (abbreviated as SN P system), of degree m≥1, is a construct of the form Π= (O, σ1, . . . , σm, syn, in, out), where: 1. O={a}is the singleton alphabet (ais called spike); 2. σ1, . . . , σmare neurons, of the form σi= (ni, Ri),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,c≥1, and d≥0; (2) as→λ, for some s≥1, with the restriction that for each rule E/ac→ a;dof type (1) from Ri, we have as/∈L(E); 3. syn ⊆ {1,2, . . . , m}×{1,2, . . . , m}with (i, i)/∈syn for 1 ≤i≤m(synapses between neurons); 4. in, out ∈ {1,2, . . . , m}indicates the input neuron (resp., output neuron). The rules of type (1) are firing (we also say spiking)rules, and they are applied as follows. If the neuron σicontains kspikes, and ak∈L(E), k ≥c, then the rule E/ac→a;dcan be applied. The application of this rule means consuming (removing) cspikes (thus only k−cremain in σi), the neuron is fired, and it produces a spike after dtime units (as usual in membrane computing, a global On Complexity Classes of Spiking Neural P Systems 271 clock is assumed, marking the time for the whole system, hence the functioning of the system is synchronized). If d= 0, then the spike is emitted immediately, if d= 1, then the spike is emitted in the next step, etc. 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 (this corresponds to the refractory period from neurobiology), 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). 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). The rules of type (2) are forgetting rules; they 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. If a rule E/ac→a;dof type (1) has E=ac, then we will write it in the following simplified form: ac→a;d. In each time unit, if a neuron σican use one of its rules, then a rule from Rimust be used. Since two firing rules, E1/ac1→a;d1and E2/ac2→a;d2, can have L(E1)∩L(E2)6=∅, it is possible that two or more rules can be applied in a neuron, and in that case, only one of them is chosen non-deterministically. Note however that, by definition, if a firing rule is applicable, then no forgetting rule is applicable, and vice versa. Thus, the rules are used in the sequential manner in each neuron, but neurons function in parallel with each other. The system is called deterministic if for every neuron that occurs in the system, any two rules E1/ac1→a;d1and E2/ac2→a;d2in the neuron have L(E1)∩ L(E2) = ∅. The initial configuration of the system is described by the numbers n1, n2, . . . , nm, of spikes present in each neuron. During a computation, the “state” of the system is described by both by the number of spikes present in each neuron, and by the open/closed condition of each neuron: if a neuron is closed, then we have to specify when it will become open again. Using the rules as described above, one can define transitions among configurations. A transition between two configurations C1, C2is denoted by C1=⇒C2. Any sequence of transitions starting in the initial configuration is called a computation. A computation halts if it reaches a configuration where all neurons are open and no rule can be used. With any computation (halting or not) we associate aspike train, the sequence of zeros and ones describing the behavior of the output neuron: if the output neuron spikes, then we write 1, otherwise we write 0. 3.1 Descriptional complexity of SN P systems The size of description of a SN P system is an important measure when one wants to study families of SN P systems. The first detailed specification of descriptional size of a SN P system Πis given in [16]. It is based on the number of bits necessary to fully describe the system Π. Let mbe the number of neurons, Nbe the maximum natural number that appears in the definition of Π, R the maximum number of 272 A. Rodr´ıguez-Pat´on, P. Sos´ık, L. Cienciala rules which occur in its neurons, and Sthe maximum size required by the regular expressions that occur in Π(this will be discussed later). Then the total size of description of Πis polynomial with respect to m, R, S and log N. Some authors introducing space complexity measures for P systems as [25] suggested that an n-tuple of identical objects should occupy a space n. In SN P systems, however, the spikes are not physical objects but an electric potential. Furthermore, if we decided for unary representation of spikes, then it would be also fair to assume unary representation of regular expressions in neurons which, however, could restrict their power significantly. Finally, observe that classical models of P systems and their uniform families (see the next section for definition of families) actually use binary representation of data. A member of the family processing inputs of size ncan use poly(n) different objects and code its input by their (non)presence in the input membrane. Therefore, to represent nspikes, just the number log nof bits is taken as the size of its description, both in neurons and regular expressions. This succinct representation is used also in [16] and other papers. Note, however, that many of the results presented here remain valid even if the unary representation of spikes were adopted. 3.2 Families of SN P systems solving decision problems Standard SN P systems were shown to be universal already in the introductory paper [12]. However, as demonstrated in [20], no standard spiking neural P system with a constant number of neurons can simulate Turing machines with less than exponential time and space overheads. Therefore, for application of SN P systems to solve intractable problems, many authors have (implicitly) used families of SN P systems such that each member of a family solves only a finite set of instances of a given size. In this section we propose a formal specification for families of SN P systems. A first step towards such a specification was taken already in [15] for the case of non-deterministic (and non-confluent) SN P systems. Most of definitions in this section is motivated by [23]. Let us call decision problem a pair X= (IX, θX) where IXis a language over a finite alphabet (whose elements are called instances) and θXis a total boolean function over IX. It was suggested by some authors that a SN P systems solving an instance w∈IXwould halt if and only if θX(w)=1.However, this is incompatible with definitions of basic complexity classes (which do not allow non-halting computations) and also with standard construction of families of recognizer P systems [23] which is extensively used. Hence we suggest the convention used implicitly by many authors ([9, 16] and others) when describing “neural” solutions to Subset Sum, 3-SAT and similar problems: the system always halts and the result is determined by the fact whether the output neuron emits a spike during the computation. Other convention are possible, such as the existence of two output neurons signalling true or false. On Complexity Classes of Spiking Neural P Systems 273 Definition 3. Arecognizer SN P system is a SN P system which has all computations halting, and whose output neuron spikes no more than once during each computation. Its computation is called accepting if the output neuron spikes exactly once, otherwise it is rejecting. This definition is also compatible with the variant when the system is asked to spike at least once in the case of accepting computation. Any such SN P system can be added another neuron connected to the original output, with two initial spikes and the rules a→λand a3→a; 0 which emits only the first spike of those it receives. We distinguish recognizer SN P systems with input or without input. In the first case the input (i.e., an instance w∈IX) is sent in the form of binary spike train bin(w) to the input neuron, where bin(w) is an arbitrary binary encoding of w. There are reasons for choosing binary encoding: it is known that standard SN P systems can simulate logic gates with unbounded fan-in in a unit time [9]. Hence, their computational potential is at least as high as that of logic circuits. The unary input/output convention, however, would decrease their computational power exponentially in many cases, on one hand. On the other hand, to transform the input value into the number of spikes in a neuron, the extended rules or maximal parallelism would be necessary [17]. In the case of SN P systems without input, instances of a problem are encoded within the structure of SN P system. Definition 4. A family Π={Π(w) : w∈IX}(respectively, Π={Π(n) : n∈ N}) of recognizer SN P without input (resp., with input) is polynomially uniform by Turing machines if there exists a deterministic Turing machine working in polynomial time which constructs the system Π(w)(resp., Π(n)) from the instance w∈IX(resp., from n∈N). In the sequel we will for short denote such a family just as uniform. Necessary conditions must be met by families of recognizer SN P systems to solve algorithmically a given decision problem. Conditions of soundness and completeness of Πwith respect to Xare defined in [23]. Conjunction of these two conditions for SN P systems without input (resp., with input) ensures that for every w∈IX, if θX(w) = 1,then every computation of the SN P systems solving wis accepting, and if θX(w)=0,then every such computation is rejecting. Note that this SN P system can be generally nondeterministic, i.e, it may have different possible computations, but with the same result. Such a P system is also called confluent. Definition 5. Let f:N→Nbe a constructible function. A decision problem X is solvable in time bounded by fby a family Π={Π(w) : w∈IX}of recognizer SN P systems of type Rwithout input, denoted by X∈SN∗ R(f),if the following holds: •The family Πis polynomially uniform by Turing machines. •The family Πis ftime-bounded; that is, for each instance w∈IX,every computation of Π(w)performs at most f(|w|)steps. 274 A. Rodr´ıguez-Pat´on, P. Sos´ık, L. Cienciala •The family Πis sound and complete with respect to X. The family Πis said to provide a semi-uniform solution to the problem X. In this case, for each instance of Xwe have a special P system. Specifically, we denote by PSN∗ R=[ fpolynomial SN∗ R(f) the class of problems to which uniform families of SN P systems of type Rwithout input provide semi-uniform solution in polynomial time. Analogously we define families which provide uniform solutions solutions to decision problems. Definition 6. Let f:N→Nbe a constructible function. A decision problem Xis solvable in time bounded by fby a family Π={Π(n) : n∈N}of recognizer SN P systems of type Rwith input, denoted by X∈SNR(f),if the following holds: •The family Πis polynomially uniform by Turing machines. •The family Πis ftime-bounded; that is, for each instance w∈IX,every computation of the member of Πsolving wperforms at most f(|w|)steps. •The family Πis sound and complete with respect to X. The family Πis said to provide a uniform solution to the problem X. Again, we denote by PSNR=[ fpolynomial SNR(f) the class of problems to which uniform families of SN P systems of type Rwith input provide uniform solution in polynomial time. Obviously, for any constructible function fand a class of SN P systems R,SNR(f)⊆SN∗ R(f),and PSNR⊆ PSN∗ R. We use the following notation to describe a specific type Rof SN P systems: −reg for systems with regular expressions of the form an, n ≥1,−del for systems without delays, and ssnf for systems with regular expressions in the single-star normal form. 4 Simulation of SN P systems with RAM Theorem 1. For each confluent (respectively, non-confluent) SN P system Πwith all regular expressions in single-star normal form (SSNF) and with description of size s, there is a deterministic (resp., non-deterministic) RAM constructed in polynomial time with unit costs of operations which simulates tsteps of Πin time O(t(s+t)). Proof. All information about the topology of the SN P system and rules in neurons can be contained within the simulating RAM program. The configuration of each neuron of a SN P systems will be represented in RAM by three registers counting On Complexity Classes of Spiking Neural P Systems 275 (i) the number of spikes in the neuron, (ii) current delay period of the neuron (i.e., the remaining number of steps during which the neuron will be closed), and (iii) the number of spikes prepared to be emitted (0 or 1, but in case of extended SN P systems it can be more). Simulation of single step of a SN P system with RAM consists of the following phases: 1. For each neuron: •If the delay period is 0, check whether the number of spikes in neuron is covered by a regular expression in some of its rules. If more than one rule matches, choose one randomly. If a rule E/ac→a;dor ac→λcan be applied, then a) decrease the number of spikes in neuron by c, b) set the delay period to din the case of firing rule, c) set the number of spikes to be emitted to 1 for firing rule or to 0 for erasing rule. •Else decrement the delay period by 1. 2. For each neuron with delay period 0 and the number of spikes to be emitted ¿0: reset the number of spikes to be emitted and increase by 1 the number of spikes in all neurons connected to the output of the processed neuron. 3. If all neurons have delay period 0, none rule was applied and none spike was emitted, halt the computation. It is easy to verify that almost each elementary operation described above for a single neuron or a synapse can be implemented on RAM in O(1) time, hence the total number of necessary RAM operations for all neurons is O(s). The only exception is the evaluation whether the number of spikes in a neuron is covered by regular expressions. Consider a regular expression E=E1∪. . . ∪En in SSNF. Each Ei,1≤i≤n, can be easily rewritten to the form aq(ar)∗,for q, r ≥0.The evaluation whether Eicovers a number kof spikes present in the neuron consist of checking the divisibility of k−qby r. This operation is performed in time proportional to the number of bits of k. Total number of bits to describe all spikes in all neurons after tsteps of computation is O(s+ log t) for standard SN P systems, or O(s+t) in the case of maximal parallelism or exhaustive rules. Hence, the total number of RAM operations necessary to simulate tsteps is O(t(s+t)). The situation is more complicated when we deal with general regular expressions in neurons. Let us prove the following lemma first. Lemma 3. Matching of a regular expression Eof size sin succinct form over a singleton alphabet with a string akcan be done on a RAM or a Turing machine in non-deterministic polynomial time with respect to slog k. Proof. Assume that we have the syntactic tree of the expression Eat our disposal (its parsing can be done in deterministic polynomial time). We treat the subexpressions of the form anas constants and assign them a leaf node of the tree with the value n. The matching algorithm works as follows: 282 A. Rodr´ıguez-Pat´on, P. Sos´ık, L. Cienciala 22. G. P˘aun, G. Rozenberg, and A. Salomaa, editors. The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford, 2009. 23. M.J. P´erez-Jim´enez. A computational complexity theory in membrane computing. In P˘aun et al. [27], pages 125–148. 24. N. Pippenger and M.J. Fischer. Relations among complexity measures. J. ACM, 26(2):361–381, 1979. 25. A.E. Porreca, A. Leporati, G. Mauri, and C. Zandron. Introducing a space complexity measure for P systems. Int. J. of Computers, Communications & Control, IV(4):301– 310, 2009. 26. G. P˘aun. Membrane Computing – An Introduction. Springer, Berlin, 2002. 27. G. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, G. Rozenberg, and A. Salomaa, editors. Membrane Computing, 10th International Workshop, WMC 2009, volume 5957 of Lecture Notes in Computer Science, Berlin, 2010. Springer. 28. L. Stockmeyer and U. Vishkinj. Simulation of parallel random access machines by circuits. SIAM J. Comput., 13 (2):409–422, 1984. 29. J. van Leeuwen, editor. Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity. Elsevier, Amsterdam, 1990.