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 /