On the Computational Power of Spiking Neural P Systems

On he Compu a ional Powe o Spiking Neu al P Sys ems Albe o Lepo a i, Claudio Zand on, Claudio Fe e i, Gianca lo Mau i Dipa imen o di In o ma ica, Sis emis ica e Comunicazione Uni e si `a degli S udi di Milano – Bicocca Via Bicocca degli A cimboldi 8, 20126 Milano, I aly {lepo a i,zand on, e e i,mau i}@disco.unimib.i Summa y. In his pape we s udy some compu a ional p ope ies o spiking neu al P sys ems. In pa icula , we show ha by using nonde e minism in a sligh ly ex ended e sion o spiking neu al P sys ems i is possible o sol e in cons an ime bo h he nume ical NP–comple e p oblem Subse Sum and he s ongly NP–comple e p oblem 3-SAT. Then, we show how o simula e a uni e sal de e minis ic spiking neu al P sys em wi h a de e minis ic Tu ing machine, in a ime which is polynomial wi h espec o he execu ion ime o he simula ed sys em. Su p isingly, i u ns ou ha he simula ion can be pe o med in polynomial ime wi h espec o he size o he desc ip ion o he simula ed sys em only i he egula exp essions used in such a sys em a e o a e y es ic ed ype. 1 In oduc ion Memb ane sys ems (also called P sys ems) we e in oduced in [16] as a new class o dis ibu ed and pa allel compu ing de ices, inspi ed by he s uc u e and unc ion- ing o li ing cells. The basic model consis s o a hie a chical s uc u e composed by se e al memb anes, embedded in o a main memb ane called he skin. Memb anes di ide he Euclidean space in o egions, ha con ain some objec s ( ep esen ed by symbols o an alphabe ) and e olu ion ules. Using hese ules, he objec s may e ol e and/o mo e om a egion o a neighbo ing one. Usually, he ules a e applied in a nonde e minis ic and maximally pa allel way; mo eo e , all he objec s ha may e ol e a e o ced o e ol e. A compu a ion s a s om an ini ial con igu a ion o he sys em and e mina es when no e olu ion ule can be applied. The esul o a compu a ion is he mul ise o objec s con ained in o an ou pu memb ane, o emi ed om he skin o he sys em. Fo a sys ema ic in oduc ion o P sys ems we e e he eade o [18], whe eas he la es in o ma ion can be ound in [23]. 228 A. Lepo a i e al. In an a emp o pass om cell-like o issue-like a chi ec u es, in [13] issue P sys ems we e de ined, in which cells a e placed in he nodes o a (di ec ed) g aph. Since hen, his model has been u he elabo a ed, o example, in [4] and [19], wi h ecen esul s abou bo h heo e ical p ope ies [1] and applica ions [14]. This e olu ion has led o explo e also neu al-like a chi ec u es, yielding o he in oduc ion o spiking neu al P sys ems (SN P sys ems, o sho ) [8], based on he neu ophysiological beha io o neu ons sending elec ical impulses (spikes) along axons o o he neu ons. We ecall ha his biological backg ound has al eady led o se e al models in he a ea o neu al compu a ion, e.g., see [11, 12, 6]. Simila ly o issue P sys ems, in SN P sys ems he cells (neu ons) a e placed in he nodes o a di ec ed g aph, called he synapse g aph. The con en s o each neu on consis o a numbe o copies o a single objec ype, called he spike. The i ing ules assigned o a cell allow a neu on o send in o ma ion o o he neu ons in he o m o elec ical impulses (also called spikes) which a e accumula ed a he a ge cell. The applica ion o he ules depends on he con en s o he neu on; in he gene al case, applicabili y is de e mined by checking he con en s o he neu on agains a egula se associa ed wi h he ule. As inspi ed om biology, a e a cell sends ou spikes i becomes “closed” (inac i e) o a speci ied pe iod o ime, ha e lec s he e ac o y pe iod o biological neu ons. Du ing his pe iod, he neu on does no accep new inpu s and canno “ i e” ( ha is, emi spikes). Ano he impo an ea u e o biological neu ons is ha he leng h o he axon may cause a ime delay be o e a spike a i es a he a ge . In SN P sys ems his delay is modeled by associa ing a delay pa ame e o each ule which occu s in he sys em. I no i ing ule can be applied in a neu on, he e may be he possibili y o apply a o ge ing ule, ha emo es om he neu on a p ede ined numbe o spikes. In he o iginal model o SN P sys ems de ined in [8], compu a ions occu as ollows. A con igu a ion speci ies, o each neu on o he sys em, he numbe o spikes i con ains and he numbe o compu a ion s eps a e which he neu on will become “open” ( ha is, no closed). S a ing om an ini ial con igu a ion, a posi i e in ege numbe is gi en in inpu o a speci ied inpu neu on. The numbe is encoded as he in e al o ime s eps elapsed be ween he inse ion o wo spikes in o he neu on. To pass om a con igu a ion o ano he one, o each neu on a ule is chosen among he se o applicable ules, and is execu ed. The compu a ion p oceeds in a sequen ial way in o each neu on, and in pa allel among di e en neu ons. Gene ally, a compu a ion may no hal . Howe e , in any case he ou pu o he sys em is conside ed o be he ime elapsed be ween he a i al o wo spikes in a designa ed ou pu cell. De ined in his way, SN P sys ems compu e unc ions o he kind :N→N( hey can also indi ec ly compu e unc ions o he kind :Nk→Nby using a bijec ion om Nk o N). By igno ing he ou pu neu on we can de ine accep ing SN P sys ems, in which he na u al numbe gi en in inpu is accep ed i he compu a ion hal s, and ejec ed o he wise. On he o he hand, by igno ing he inpu neu on (and hus s a ing om a p ede ined inpu con igu a ion) we can de ine gene a i e SN P sys ems. On he Compu a ional Powe o SN P Sys ems 229 In [8] i was shown ha gene a i e SN P sys ems a e uni e sal, ha is, can gene a e any ecu si ely enume able se o na u al numbe s. Mo eo e , a cha - ac e iza ion o semilinea se s was ob ained by spiking neu al P sys ems wi h a bounded numbe o spikes in he neu ons. These esul s can also be ob ained wi h e en mo e es ic ed o ms o spiking P sys ems; o example, [7] shows ha a leas one o hese ea u es can be a oided while keeping uni e sali y: ime delay ( e ac o y pe iod) g ea e han 0, o ge ing ules, ou deg ee o he synapse g aph g ea e han 2, and egula exp essions o complex o m. Finally, in [20] he be- ha io o spiking neu al P sys ems on in ini e s ings and he gene a ion o in ini e sequences o 0 and 1 was in es iga ed, whe eas in [2] spiking neu al P sys ems we e s udied as language gene a o s (o e he bina y alphabe {0,1}). The es o his pape is o ganized as ollows. In sec ion 2 we gi e some ma h- ema ical p elimina ies, and we de ine he s anda d e sion o SN P sys ems (as ound in [9]) as well as a sligh ly ex ended e sion. In sec ion 3 we show how he NP–comple e p oblems Subse Sum and 3-SAT can be sol ed in cons an ime by exploi ing nonde e minism in ou ex ended SN P sys ems. In sec ion 4 we u n ou a en ion o de e minis ic sys ems, and we show how o simula e hem by us- ing de e minis ic Tu ing machines. Sec ion 5 concludes he pape and gi es some di ec ions o u u e esea ch. 2 P elimina ies Le us s a by ecalling he s anda d de ini ion o a spiking neu al P sys em, aken om [9]. A spiking neu al memb ane sys em (SN P sys em, o sho ), o deg ee m≥1, is a cons uc o he o m Π= (O, σ1, σ2,...,σm, syn, in, ou ), whe e: 1. O={a}is he single on alphabe (ais called spike); 2. σ1, σ2,...,σma e neu ons, o he o m σi= (ni, Ri), wi h 1 ≤i≤m, whe e: a) ni≥0 is he ini ial numbe o spikes con ained in σi; b) Riis a ini e se o ules o he ollowing wo o ms: (1) E/ac→a;d, whe e Eis a egula exp ession o e a, and c≥1, d≥0 a e in ege numbe s; i E=ac, hen i is usually w i en in he ollowing simpli ied o m: ac→a;d; (2) as→λ, o s≥1, wi h he es ic ion ha o each ule E/ac→a;do ype (1) om Ri, we ha e as6∈ L(E) (whe e L(E) deno es he egula language de ined by E); 3. syn ⊆ {1,2,...,m} × {1,2,...,m}, wi h (i, i)6∈ syn o 1 ≤i≤m, is he di ec ed g aph o synapses be ween neu ons; 4. in, ou ∈ {1,2,...,m}indica e he inpu and he ou pu neu ons o Π. 230 A. Lepo a i e al. The ules o ype (1) a e called i ing (also spiking) ules, and hey a e applied as ollows. I he neu on σicon ains k≥cspikes, and ak∈L(E), hen he ule E/ac→a;d∈Rican be applied. The execu ion o his ule emo es cspikes om σi( hus lea ing k−cspikes), and p epa es one spike o be deli e ed o all he neu ons σjsuch ha (i, j)∈syn. I d= 0, hen he spike is immedia ely emi ed, o he whise i is emi ed a ed dcompu a ion s eps o he sys em. (Obse e ha , as usually happens in memb ane compu ing, a global clock is assumed, ma king he ime o he whole sys em, hence he unc ioning o he sys em is synch onized.) I he ule is used in s ep and d≥1, hen in s eps , + 1, + 2, . . . , +d−1 he neu on is closed, so ha i canno ecei e new spikes (i a neu on has a synapse o a closed neu on and ies o send a spike along i , hen ha pa icula spike is los ), and canno i e new ules. In he s ep +d, he neu on spikes and becomes again open, so ha i can ecei e spikes (which can be used s a ing wi h he s ep +d+ 1) and selec ules o be i ed. Rules o ype (2) a e called o ge ing ules, and a e applied as ollows: i he neu on σicon ains exac ly sspikes, hen he ule as→λ om Rican be used, meaning ha all sspikes a e emo ed om σi. No e ha , by de ini ion, i a i ing ule is applicable, hen no o ge ing ule is applicable, and ice e sa. In each ime uni , i a neu on σican use one o i s ules, hen a ule om Ri mus be used. Since wo i ing ules, E1:ac1→a;d1and E2:ac1→a;d2, can ha e L(E1)∩L(E2)6=∅, i is possible ha wo o mo e ules can be applied in a neu on. In such a case, only one o hem is chosen nonde e minis ically. Thus, he ules a e used in he sequen ial manne in each neu on, bu neu ons unc ion in pa allel wi h each o he . The ini ial con igu a ion o he sys em is desc ibed by he numbe s n1, n2, . . ., nmo spikes p esen in each neu on, wi h all neu ons being open. Du ing he compu a ion, a con igu a ion is desc ibed by bo h he numbe o spikes p esen in each neu on and by he s a e o each neu on, which can be exp essed as he numbe o s eps o coun down un il i becomes open ( his numbe is ze o i he neu on is al eady open). A compu a ion in a sys em as abo e s a s in he ini ial con igu a ion. In o de o compu e a unc ion :Nk→N, we in oduce k na u al numbe s n1, n2,...,nkin he sys em by “ eading” om he en i onmen a bina y sequence z= 0b10n110n21...10nk10g, o some b, g ≥0; his means ha he inpu neu on o Π ecei es a spike in each s ep co esponding o a digi 1 om he s ing z. No e ha we inpu exac ly k+ 1 spikes. The esul o he compu a ion is also encoded in he dis ance be ween wo spikes: we impose o he sys em o ou pu exac ly wo spikes and hal (some imes a e he second spike) hence p oducing a ain spike o he o m 0b010 10g0, o some b0, g0≥0 and wi h = (n1, n2,...,nk). I we use an SN P sys em in he gene a i e mode, hen no inpu neu on is conside ed, hence no inpu is aken om he en i onmen ; we s a om he ini ial con igu a ion, and he dis ance be ween he i s wo spikes o he ou pu neu on (o o he numbe s, see he discussion in [9]) is he esul o he compu a ion. On he Compu a ional Powe o SN P Sys ems 231 Dually, we can igno e he ou pu neu on, and i he compu a ion hal s, hen he numbe is accep ed. We de ine he desc ip ion size o an SN P sys em Πas he numbe o bi s which a e necessa y o desc ibe i . Since he alphabe Ois ixed, no bi s a e necessa y o de ine i . In o de o ep esen syn we need a mos m2bi s, whe eas we can ep esen he alues o in and ou by using log mbi s each. E e y neu on σi equi es o speci y a na u al numbe ni, and a se Rio ules. Each ule equi es o speci y i s ype ( i ing o o ge ing), which can be done wi h 1 bi , and in he wo s case i equi es o speci y a egula exp ession and wo na u al numbe s. I we deno e by N he maximum na u al numbe ha appea s in he de ini ion o Π,R he maximum numbe o ules which occu in i s neu ons, and S he maximum size equi ed by he egula exp essions ha occu in Π(mo e on his la e ), hen we need a maximum o log N+R(1+S+ 2 log N) bi s o desc ibe e e y neu on o Π. Hence, o desc ibe Πwe need a o al o m2+2 log m+mlog N+R(1+S+2 logN) bi s. No e ha his quan i y is polynomial wi h espec o m,R,Sand log N. Since he egula languages de e mined by he egula exp essions ha occu in he sys em a e una y languages, he s ings o such languages can be bijec i ely iden i ied by hei leng hs. Hence, when w i ing he egula exp ession E, ins ead o w i ing unions, conca ena ions and Kleene closu es among s ings we can do he same by using he leng hs o such s ings. In his way we ob ain a ep esen a ion o Ewhich is exponen ially mo e compac han he usual ep esen a ion o egula exp essions. As we will see in sec ion 4, his compac ep esen a ion will yield some di icul ies when we will simula e a de e minis ic accep ing SN P sys em by a de e minis ic Tu ing machine. In wha ollows i will be con enien o conside also a sligh ly ex ended e sion o SN P sys ems. P ecisely, we will allow ules o he ype E/ac→ap;d, whe e c≥1, p≥0 and d≥0 a e in ege numbe s. The seman ics o his kind o ules is as ollows: i he con en s o he neu on ma ches he egula exp ession E, hen he ule can be applied. When he ule is applied, cspikes a e emo ed om he con en s o he neu on and pspikes a e p epa ed o be deli e ed o all he neu ons which a e di ec ly connec ed ( h ough an a c o syn) wi h he cu en neu on. I d= 0, hen hese pspikes a e immedia ely sen , o he wise he neu on becomes closed o he nex dcompu a ion s eps, a e which he pspikes will be sen . As be o e, a closed neu on does no ecei e spikes om o he neu ons, and does no apply any ule. I p= 0, hen we ob ain a o ge ing ule as a pa icula case o ou gene al ules. Also in he ex ended SN P sys ems i may happen ha , gi en wo ules E1/ac1→ap1;d1and E2/ac2→ap2;d2, i L(E1)∩L(E2)6=∅ hen o some con- en s o he neu on bo h he ules can be applied. In such a case, we nonde e min- is ically choose one o hem. No e ha we do no equi e ha o ge ing ules a e applied only when no i ing ule can be applied. We say ha he sys em is de e min- is ic i , o e e y neu on ha occu s in he sys em, any wo ules E1/ac1→ap1;d1 and E2/ac2→ap2;d2in he neu on a e such ha L(E1)∩L(E2) = ∅. This means 232 A. Lepo a i e al. ha , o any possible con en s o he neu on, a mos one o he ules ha occu in he neu on may be applied. By using an inpu neu on and an ou pu neu on, we ha e SN P sys ems ha compu e unc ions o he kind :N→N, and hence we co e bo h he gene a i e and he accep ing cases. I ou = 0, hen i is unde s ood ha he ou pu is sen o he en i onmen (as he numbe o spikes p oduced by he sys em, as he dis- ance be ween he i s wo spikes, e c.). As usual, o use an SN P sys em in he gene a i e mode we do no conside he inpu neu on, and hus no inpu is aken om he en i onmen ; we s a om he ini ial con igu a ion, and he dis ance be ween he i s wo spikes o he ou pu neu on (o he numbe o spikes con- ained in o he ou pu neu on a he end o he compu a ion, as discussed abo e) is he esul o he compu a ion. No e ha gene a i e SN P sys ems a e inhe en ly nonde e minis ic, o he wise hey would always ep oduce he same sequence o compu a ion s eps, and hence he same ou pu . Dually, we can igno e he ou pu neu on o ob ain an accep ing SN P sys em. We inpu a numbe in he sys em as he dis ance be ween wo spikes en e ing he inpu neu on (o he numbe o spikes ha occu in he inpu neu on in he ini ial con igu a ion) and, i he compu a ion hal s, hen he numbe is accep ed. The desc ip ion size o an ex ended SN P sys em is de ined exac ly as we did o s anda d sys ems, he only di e ence being ha now we equi e (a mos ) h ee na u al numbe s o desc ibe a ule. 3 Sol ing NP–comple e P oblems wi h Ex ended Spiking Neu al P Sys ems In his sec ion we show ha nonde e minis ic SN P sys ems a e e y powe ul compu ing de ices, a leas in he ex ended e sion de ined in he p e ious sec ion: in ac , hey a e able o sol e NP–comple e p oblems in a cons an numbe o compu a ion s eps. 3.1 Sol ing he Subse Sum p oblem Le us i s conside he Subse Sum p oblem, which can be s a ed as ollows. P oblem 1. Name:Subse Sum. •Ins ance: a (mul i)se V={ 1, 2,..., n}o posi i e in ege numbe s, and a posi i e in ege numbe S •Ques ion: is he e a subse B⊆Vsuch ha P b∈B b=S? I we allow o nonde e minis ically choose among he ules which occu in he neu ons, hen he ex ended SN P sys em depic ed in Figu e 1 sol es any gi en ins ance o Subse Sum in a cons an numbe o s eps. We emphasize he ac On he Compu a ional Powe o SN P Sys ems 233 Fig. 1. A nonde e minis ic ex ended SN P sys em ha sol es he Subse Sum p oblem in cons an ime ha such a solu ion occu s in he semi-uni o m se ing, ha is, o e e y ins ance o Subse Sum we build an SN P sys em ha speci ically sol es ha ins ance. Le (V={ 1, 2,..., n}, S) be he ins ance o Subse Sum o be sol ed, and le B⊆V. In he ini ial con igu a ion o he sys em, he le mos neu ons con ain ( om op o bo om) 1, 2,..., nspikes, espec i ely, whe eas he igh mos neu ons con ain ze o spikes each. In he i s s ep o compu a ion, in each o he le mos neu ons o he SN P sys em depic ed in Figu e 1 i is nonde e minis ically chosen whe he o include o no he elemen iin B; his is accomplished by nonde e minis ically choosing among one ule ha o ge s ispikes (in such a case, i6∈ B) and one ule ha p opaga es ispikes o he igh mos neu ons. A he beginning o he second s ep o compu a ion a ce ain numbe No spikes, ha co esponds o he sum o he iwhich ha e been chosen, occu s in he igh mos neu ons. We ha e h ee possible cases: •N < S: in his case nei he he ule aS→a; 0 no he ule aS+1 →a; 1 (which occu in he neu on a he op and a he bo om o he second laye , espec i ely) i e, and hus no spike is emi ed o he en i onmen ; •N=S: only he ule aS→a; 0 i es, and emi s a single spike o he en i on- mnen . No u he spikes a e emi ed; •N > S: bo h he ules aS→a; 0 and aS+1 →a; 1 i e. The i s ule im- media ely sends one spike o he en i onmen , whe eas he second ule sends ano he spike a he nex compu a ion s ep (due o he delay associa ed wi h he ule). 234 A. Lepo a i e al. Hence, by coun ing he numbe o spikes emi ed o he en i onmen a he second and hi d compu a ion s eps we a e able o ead he solu ion o he gi en ins ance o Subse Sum: he ins ance is posi i e i and only i a single spike is emi ed. The o mal de ini ion o he ex ended (gene a ing) SN P sys em depic ed in Figu e 1 is as ollows: Π= ({a}, σ1,...,σn+2, syn, ou ), whe e: •σi= ( i,{a i→λ, a i→a i; 0}) o 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)}; •ou = 0 indica es ha he ou pu is sen o he en i onmen . Howe e , he e we a e aced wi h a p oblem ha we ha e al eady encoun e ed in [10], and ha we will encoun e again in he es o he pape . In o de o clea ly expose he p oblem, le us conside he ollowing algo i hm ha sol es Subse Sum using he well-known Dynamic P og amming echnique [3]. In pa icula , he algo i hm e u ns 1 on posi i e ins ances, and 0 on nega i e ins ances. Subse Sum({ 1, 2,..., n}, S) o j←0 o S do M[1, j]←0 M[1,0] ←M[1, 1]←1 o i←2 o n do o j←0 o S do M[i, j]←M[i−1, j] i j≥ iand M[i−1, j − i]> M[i, j] hen M[i, j]←M[i−1, j − i] e u n M[n, S] In o de o look o a subse B⊆Vsuch ha Pb∈Bb=S, he algo i hm uses an n×(S+ 1) ma ix Mwhose en ies a e om {0,1}. I ills he ma ix by ows, s a ing om he i s ow. Each ow is illed om le o igh . The en y M[i, j] is illed wi h 1 i and only i he e exis s a subse o { 1, 2,..., i}whose elemen s sum up o j. The gi en ins ance o Subse Sum is hus a posi i e ins ance i and only i M[n, S] = 1 a he end o he execu ion. Since each en y is conside ed exac ly once o de e mine i s alue, he ime complexi y o he algo i hm is p opo ional o n(S+1) = Θ(nS). This means ha he di icul y o he p oblem depends on he alue o S, as well as on he magni ude o he alues in V. In ac , le K=max{ 1, 2,..., n, S}. I Kis polynomially bounded wi h espec o n, hen he abo e algo i hm wo ks in polynomial ime. On he o he hand, i Kis exponen ial wi h espec o n, say K= 2n, hen he abo e algo i hm wo ks in exponen ial ime and space. This beha io is usually On he Compu a ional Powe o SN P Sys ems 235 e e ed o in he li e a u e by elling ha Subse Sum is a pseudo–polynomial NP–comple e p oblem. The ac ha in gene al he unning ime o he abo e algo i hm is no poly- nomial can be immedia ely unde s ood by compa ing i s ime complexi y wi h he ins ance size. The usual size o he ins ances o Subse Sum is Θ(nlog K), since o conciseness e e y “ easonable” encoding is assumed o ep esen each elemen o V(as well as S) using a s ing whose leng h is O(log K). He e all loga i hms a e aken wi h base 2. S a ed di e en ly, he size o he ins ance is usually conside ed o be he numbe o bi s which mus be used o ep esen in bina y Sand all he in ege numbe s which occu in V. I we would ep esen such numbe s using he una y no a ion, hen he size o he ins ance would be Θ(nK). Bu in his case we could w i e a p og am which i s con e s he ins ance in bina y o m and hen uses he abo e algo i hm o sol e he p oblem in polynomial ime wi h espec o he new ins ance size. We can hus conclude ha he di icul y o a nume ical NP–comple e p oblem depends also on he measu e o he ins ance size we adop . The p oblem we men ioned abo e abou he SN P sys em depic ed in Figu e 1 is ha he ules a i→λand a i→a i; 0 which occu in he le mos neu ons, as well as hose ha occu in he igh mos neu ons, check o he exis ence o a numbe o spikes which is exponen ial wi h espec o he usually ag eed ins ance size o Subse Sum. Mo eo e , o ini ialize he sys em he use has o place a numbe o objec s which is also exponen ial. This is no ai , because i means ha he SN P sys em ha sol es he NP–comple e p oblem has an exponen ial size wi h espec o he bina y s ing which is used o desc ibe i ; an exponen ial e o is hus needed o build he sys em, ha easily sol es he p oblem by wo king in una y no a ion (hence in polynomial ime wi h espec o he size o he sys em, bu no wi h espec o i s desc ip ion size). This p oblem is in some aspec s simila o wha has been desc ibed in [10], conce ning adi ional P sys ems ha sol e NP–comple e p oblems. 3.2 The 3-SAT p oblem In his sec ion we show ha SN P sys ems a e also able o sol e non-nume ical NP–comple e p oblems. Such p oblems a e inhe en ly s ongly NP–comple e, ha is, hey emain NP–comple e e en i he numbe s e en ually con ained in o he ins ance a e exp essed in una y o m. Speci ically, we i s p opose a simple ex- ended SN P sys em ha sol es 3-SAT, and hen we show ha also s anda d SN P sys ems a e able o sol e his p oblem. We s a by ecalling some well known de ini ions, in o de o se le he no a- ion. A boolean a iable is a a iable which can assume one o wo possible u h alues: ue and alse. As usually done in he li e a u e, we will deno e ue by 1 and alse by 0. A li e al is ei he a di ec ed o a nega ed boolean a iable. Aclause is a disjunc ion o li e als, whe eas a 3-clause is a disjunc ion o exac ly h ee li e als. Gi en a se X={x1, x2,...,xn}o boolean a iables, an assignmen is a mapping a:X→ {0,1} ha associa es o each a iable a u h alue. The 242 A. Lepo a i e al. Thus, a s ep o he spiking phase equi es O(mlog D)·m·(m2+ log D+ log(w+ Qm))=O(m2log D)(m2+ log D+ log(w+ Qm))s eps. The o al ime equi ed o simula e s eps o Πis hus imes he ime needed o pe o m he wo phases, ha is, ·O(m(Z+ log(w+ Qm) + log Q+ log D)) + O(m2log D)(m2+ log D+ log(w+ Qm)). To show ha his ime is polynomial wi h espec o he desc ip ion size o he sys em Π, we need o explici he ime Z equi ed o selec which ule has o be applied in neu on σi. We s ess he ac ha , since he sys em Πis de e minis ic, a each compu a ion s ep he e is a mos one ule in σiwhich can i e. In o de o selec such a ule, we need o check whe he he e a e enough spikes in he neu on (and clea ly his can be done in polynomial ime), as well as o check i ni∈L(Ei). In gene al, his las ope a ion canno be done in polynomial ime, as i will be p o ed in he nex p oposi ion. None heless, in [9] i is shown ha uni e sali y can be ob ained by using SN P sys ems whe e he egula exp essions associa ed wi h each ule a e o e y simple o ms: ai, wi h i≤3, o a(aa)+. Conside ing such sys ems, i is easy o see ha he ime equi ed o check i he con en s o σiis in he egula se de ined by he egula exp ession can be done in polynomial ime, since in he o me case i su ices o check i he numbe is equal o i( ime p opo ional o log ni), whe eas in he la e case i su ices o check he las bi o ni. Thus, he ime equi ed o selec he ule o apply depends on he numbe o ules in each neu on. Tha is, Zi=O(|Ri|) = O( ), whe e = max1≤i≤m|Ri|is he maximum numbe o ules which can be con ained in a neu on. As a consequence, he o al ime equi ed o simula e s eps o Πis ·O(m( + log(w+ Qm) + log Q+ log D)) + O(m2log D)(m2+ log D+O(log(w+ Qm)). We conclude his sec ion by s essing ha he abo e simula ion could be pe - o med in polynomial ime because he egula exp essions used in he ules a e o a e y es ic ed o m. Indeed, he e is a la ge amoun o compu a ional powe hid- den in o he implici mechanism ha SN P sys ems use o decide whe he a gi en ule can be applied o no , as p o ed in he ollowing p oposi ion. The di icul y o checking whe he he con en s o a neu on is in o he egula se de e mined by he egula exp ession Eo he ule is induced by he ac ha we a e dealing wi h una y languages. As old abo e, in hese languages a s ing is uniquely de e mined by i s leng h. Hence, a compac ep esen a ion o he s ing is ob ained by w i ing (in bina y) i s leng h, a he han by w i ing he s ing i sel . This is an expo- nen ially smalle ep esen a ion, and consequen ly all he p oblems de ined upon his ep esen a ion become ha de , as i happens o all “succin ” ep esen a ions (see [15], chap e 20). Conce ning he succin e sion o he membe ship p oblem (is a gi en s ing in o he language gene a ed by E?) we can p o e he ollowing p oposi ion. P oposi ion 1. Le Πbe an SN P sys em ha ing a single neu on, ha con ains he ule E:ac→a;d, whe e c≥1and d≥0a e na u al numbe s, and E is any egula exp ession ( o a una y language de ined on he alphabe {a}). I E On he Compu a ional Powe o SN P Sys ems 243 is desc ibed in a succin o m, hen deciding whe he his ule can be applied is a leas NP–comple e. P oo . Le us show a polynomial ime educ ion om Subse Sum o his p oblem. Le (V={ 1, 2,..., n}, S) be an ins ance o Subse Sum. I we pu K= max{ 1, 2,..., n, S}, hen he ins ance size is Θ(nK), as discussed in sec ion 3.1. Conside he egula exp ession E=E1◦E2◦...◦En, whe e Ei= (λ∪{a i}), wi h λ he symbol ha ep esen s he emp y wo d. Since we a e dealing wi h una y languages in succin o m, e e y s ing o L(E) can be uniquely de e mined by i s leng h, and hus we can w i e L(Ei) = {0, i}.L(E) is jus ob ained by pe o ming a language heo e ic conca ena ion among he languages L(Ei): L(E) = L(E1)◦ L(E2)◦...◦L(En). Clea ly, he egula exp ession Ecan be ep esen ed using a s ing whose leng h is polynomial wi h espec o he size o he gi en ins ance o Subse Sum. I is immedia ely e i ied ha L(E) con ains 2nelemen s, bijec i ely associa ed wi h he subse s o V. Mo eo e , aS∈L(E) i and only i he e exis s a se B⊆Vsuch ha Pb∈Bb=S. Hence, checking whe he aSis in L(E) o no is equi alen o sol e he Subse Sum p oblem on he gi en ins ance (V, S). 5 Conclusions and Di ec ions o Fu u e Resea ch In his pape we ha e s a ed o s udy he compu a ional powe o spiking neu al P sys ems. In pa icula , by sligh ly ex ending he o iginal de ini ion gi en in [8] and [9] we ha e shown ha by exploi ing nonde e minism i is possible o sol e NP–comple e p oblems such as Subse Sum and 3-SAT. Conce ning de e minis ic sys ems, we ha e shown ha he uni e sal de e - minis ic SN P sys ems de ined in [8, 9] can be simula ed by de e minis ic Tu ing machines wi h a polynomial slowdown. Su p isingly, his was possible only be- cause he uni e sal P sys ems desc ibed in [8, 9] use egula exp essions o a e y es ic ed o m. In ac , i was shown ha i we allow he use o gene al egula exp essions hen we can exploi he mechanism used by SN P sys ems o decide whe he he con en s o a neu on ma ches a egula exp ession o sol e he NP– comple e p oblem Subse Sum. Fu he esea ch is needed o ully unde s and he powe o accep ing SN P sys ems. In pa icula , by encoding hei inpu s as he dis ance be ween subsequen spikes we a e limi ing ou sel es o use numbe s exp essed in una y no a ion. A mo e compac way o encode a k-bi na u al numbe nwould be o send a sequence o spikes du ing a p e ixed sequence o kcompu a ion s eps: he p esence o a spike indica es a 1, i s absence indica es a 0. I is no cu en ly known whe he in his way SN P sys ems can s ill sol e nume ical NP–comple e p oblems such as Subse Sum, o whe he a subsys em ha con e s in ege numbe s om bina y o una y no a ion can be designed, as i was made in [10] o adi ional P sys ems. 244 A. Lepo a i e al. Acknowledgmen s We g a e ully hank Gheo ghe P˘aun o in oducing he au ho s o he s imula ing subjec o spiking neu al P sys ems, and o asking us a “Milano heo em” (in he spi i o [22]) abou hei compu a ional powe , du ing he Fi h B ains o ming Week on Memb ane Compu ing, held in Se ille om Janua y 29 h o Feb ua y 2nd, 2007. Mo eo e , we a e eally indeb ed wi h him o sugges ing us he s anda d nonde e minis ic SN P sys em ha sol es 3-SAT, exposed in sec ion 3. Re e ences 1. A. Alhazo , R. F eund, M. Oswald: Cell/symbol complexi y o issue P sys ems wi h sympo /an ipo ules. In e n. J. Found. Compu e Sci., 17, 1 (2006), 3–26. 2. H. Chen, R. F eund, M. Ionescu, Gh. P˘aun, M.J. P´e ez-Jim´enez: On s ing lan- guages gene a ed by spiking neu al P sys ems. In: M.A. Gu i´e ez-Na anjo, Gh. P˘aun, A. Riscos-N´u˜nez, F.J. Rome o-Campe o, eds., Fou h B ains o ming Week on Mem- b ane Compu ing, Vol. I RGCN Repo 02/2006, Resea ch G oup on Na u al Com- pu ing, Se illa Uni e si y, F´enix Edi o a, 169–194. 3. T.H. Co men, C.H. Leise son, R.L. Ri es : In oduc ion o Algo i hms. MIT P ess, Bos on, 1990. 4. R. F eund, Gh. P˘aun, M.J. P´e ez-Jim´enez: Tissue-like P sys ems wi h channel s a es. Theo e ical Compu e Science, 330 (2004), 101–116. 5. M.R. Ga ey, D.S. Johnson: Compu e s and In ac abili y. A Guide o he Theo y on NP–Comple eness. W. H. F eeman and Company, 1979. 6. W. Ge s ne , W. Kis le : Spiking Neu on Models. Single Neu ons, Popula ions, Plas- ici y. Camb idge Uni e si y P ess, 2002. 7. O.H. Iba a, A. P˘aun, Gh. P˘aun, A. Rod ´ıguez-Pa ´on, P. Sos´ık, S. Woodwo h: No mal o ms o spiking neu al P sys ems. Theo e ical Compu e Science, 372, 2-3 (2007), 196–217. 8. M. Ionescu, Gh. P˘aun, T. Yokomo i: Spiking neu al P sys ems. Fundamen a In o - ma icae, 71, 2-3 (2006), 279–308. 9. M. Ionescu, A. P˘aun, Gh. P˘aun, M.J. P´e ez-Jim´enez: Compu ing wi h spiking neu al P sys ems: aces and small uni e sal sys ems. In C. Mao, T. Yokomo i, eds., DNA Compu ing, 12 h In e na ional Mee ing on DNA Compu ing, DNA12, Seoul, Ko ea, June 5-9, 2006, Re ised Selec ed Pape s. LNCS 4287, Sp inge , 2006, 1–16. 10. A. Lepo a i, C. Zand on, M.A. Gu i´e ez-Na anjo: P sys ems wi h inpu in bina y o m. In e na ional Jou nal o Founda ions o Compu e Science, 17, 1 (2006), 127– 146. 11. W. Maass: Compu ing wi h spikes. Special Issue on Founda ions o In o ma ion P o- cessing o TELEMATIK, 8, 1 (2002), 32–36. 12. W. Maass, C. Bishop (eds.). Pulsed Neu al Ne wo ks, MIT P ess, Camb idge (MA), 1999. 13. C. Ma ´ın-Vide, J. Pazos, Gh. P˘aun, A. Rod ´ıguez-Pa ´on: A new class o symbolic abs ac neu al ne s: Tissue P sys ems. In P oceedings o COCOON 2002, Singapo e, LNCS 2387, Sp inge -Ve lag, Be lin, 290–299. 14. M. Oswald: Independen agen s in a globalized wo ld modelled by issue P sys ems. Con . A i icial Li e and Robo ics, 2006. On he Compu a ional Powe o SN P Sys ems 245 15. C.H. Papadimi iou: Compu a ional Complexi y, Addison-Wesley, 1994. 16. Gh. P˘aun: Compu ing wi h memb anes. Jou nal o Compu e and Sys em Sciences, 61 (2000), 108–143. See also Tu ku Cen e o Compu e Science — TUCS Repo No. 208, 1998. A ailable a : h p://www. ucs. i/Publica ions/ ech epo s/TR208.php 17. Gh. P˘aun: Compu ing wi h memb anes. An In oduc ion. Bulle in o he EATCS, 67 (2/1999), 139–152. 18. Gh. P˘aun: Memb ane Compu ing. An In oduc ion. Sp inge –Ve lag, Be lin, 2002. 19. Gh. P˘aun, Y. Sakakiba a, T. Yokomo i: P sys ems on g aphs o es ic ed o ms. Publica iones Ma hema icae Deb ecen, 60 (2002), 635–660. 20. Gh. P˘aun, M.J. P´e ez-Jim´enez, G. Rozenbe g: In ini e spike ains in spiking neu al P sys ems. Submi ed o publica ion. 21. G. P˘aun, G. Rozenbe g: A guide o memb ane compu ing. Theo e ical Compu e Science, 287, 1 (2002), 73–100. 22. C. Zand on, C. Fe e i, G. Mau i: Sol ing NP–comple e p oblems using P sys ems wi h ac i e memb anes. In I. An oniou, C.S. Calude, M.J. Dinneen, eds., Uncon en- ional Models o Compu a ion, Sp inge -Ve lag, London, 2000, 289–301. 23. The P sys ems Web page: h p://psys ems.disco.unimib.i /