1
Sol ing SUBSET SUM by Spiking Neu al P Sys ems wi h
P e–compu ed Resou ces
Albe o Lepo a i∗C
Dipa imen o di In o ma ica, Sis emis ica e Comunicazione
Uni e si `
a degli S udi di Milano – Bicocca
Viale Sa ca 336/14, 20126 Milano, I aly
albe o.lepo a [email protected]
Miguel A. Gu i´
e ez-Na anjo†
Resea ch G oup on Na u al Compu ing
Depa men o Compu e Science and A i icial In elligence
Uni e si y o Se illa
A da. Reina Me cedes s/n, 41012 Se illa, Spain
[email p o ec ed]
Abs ac . Recen ly he possibili y o using spiking neu al P sys ems o sol ing compu a ionally
ha d p oblems has been conside ed. Such solu ions assume ha some (possibly exponen ially la ge)
p e–compu ed esou ces a e gi en in ad ance, p o ided ha hei s uc u e is “ egula ” and hey
do no con ain nei he “hidden in o ma ion” ha simpli y he solu ion o speci ic ins ances, no
an encoding o all possible solu ions ( ha is, an exponen ial amoun o in o ma ion ha allows o
chea while sol ing he ins ances o he p oblem). In his pape we con inue his esea ch line, and
we in es iga e he possibili y o sol ing nume ical NP-comple e p oblems such as SUBSET SUM.
In pa icula , we i s p opose a semi–uni o m amily o spiking neu al P sys ems in which e e y
sys em sol es a speci ic ins ance o SUBSET SUM. Then, we exploi a echnique used o calcula e
ITERATED ADDITION wi h Boolean ci cui s o ob ain a uni o m amily o spiking neu al P sys ems
in which e e y sys em is able o sol e any ins ance o SUBSET SUM o a ixed size. All he sys ems
∗The wo k o he au ho s was pa ially suppo ed by he p ojec “Azioni In eg a e I alia–Spagna — Theo y and P ac ice o
Memb ane Compu ing” (Acci´on In eg ada Hispano-I aliana HI 2005-0194).
CCo esponding au ho
†The second au ho acknowledges he suppo o he p ojec TIN2006-13425 o he Minis e io de Educaci´on y Ciencia o Spain,
co inanced by FEDER unds, and he suppo o he p ojec o excellence TIC-581 o he Jun a de Andaluc´ıa.
2A. Lepo a i, M.A. Gu i´e ez-Na anjo /Sol ing SUBSET SUM by Spiking Neu al P Sys ems
he e conside ed a e de e minis ic, and hei size gene ally g ows exponen ially wi h espec o he
ins ance size.
Keywo ds: Memb ane compu ing, spiking neu al P sys ems, NP-comple e p oblems, Subse Sum
1. In oduc ion
Spiking neu al P sys ems (SN P sys ems, o sho ) ha e been in oduced in [12] as a new class o dis-
ibu ed and pa allel compu ing de ices, inspi ed by he neu ophysiological beha io o neu ons sending
elec ical impulses (spikes) along axons o o he neu ons. SN P sys ems a e he hi d model o com-
pu a ion in he amewo k o Memb ane Compu ing, oge he wi h he cell-like model [26] inspi ed by
he compa men al s uc u e and unc ioning o a li ing cell and he issue-like model [21, 22], based
on in e cellula communica ion and coope a ion be ween neu ons. In pa icula , [32] is he i s pape in
which P sys ems wi h memb anes a anged on an a bi a y g aph ha e been conside ed. SN P sys ems
can also be iewed as an e olu ion o P sys ems [26, 27, 29, 31] ( he la es in o ma ion can be ound
in [37]) co esponding o a shi om cell-like o neu al-like a chi ec u es whe e ime is used o encode
in o ma ion. 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 [8, 19, 20].
In SN P sys ems he cells (also called 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. E e y cell may also con ain a numbe o i ing and o ge ing ules. Fi ing ules 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 applicabili y o each ule is de e mined by checking he con en s o
he neu on agains a egula se associa ed wi h he ule. In each ime uni , i a neu on can use one o i s
ules, hen one o such ules mus be used. I wo o mo e ules could be applied, hen only one o hem
is nonde e minis ically chosen. 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 . 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, and hence he unc ioning o he sys em
is synch onized. When 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.
Fo mally, a spiking neu al memb ane sys em (SN P sys em, o sho ) o deg ee m≥1, as de ined
in [11], 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),1≤i≤m, whe e:
A. Lepo a i, M.A. Gu i´e ez-Na anjo/Sol ing SUBSET SUM by Spiking Neu al P Sys ems 3
(a) ni≥0is 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) i ing (also spiking) ules E/ac→a;d, whe e Eis a egula exp ession o e a, and
c≥1,d≥0a 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) o ge ing ules as→λ, o s≥1, wi h he es ic ion ha o each ule E/ac→a;d
o ype (1) om Ri, we ha e as6∈ L(E)(whe e L(E)is 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 Π.
A i ing ule E/ac→a;d∈Rican be applied in neu on σii i con ains k≥cspikes, and
ak∈L(E). 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 wise i is emi ed a e dcompu a ion s eps o he sys em. As s a ed abo e,
du ing hese dcompu a ion s eps he neu on is closed, and 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 (and e en selec ) ules. A o ge ing ule as→λcan be applied in neu on σii i con ains exac ly s
spikes, and no i ing ules a e applicable. The execu ion o his ule simply emo es all he sspikes om
σi.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 con en s o each neu on and i s s a e, which can be exp essed as he numbe o s eps o wai
un il i becomes open (ze o i he neu on is al eady open). Thus, h 1/ 1,..., m/ miis he con igu a ion
whe e neu on σicon ains i≥0spikes and i will be open a e i≥0s eps, o i= 1,2,...,m; wi h
his no a ion, he ini ial con igu a ion o he sys em is C0=hn1/0,...,nm/0i.
Acompu a ion s a s in he ini ial con igu a ion. In o de o compu e a unc ion :N→N, a
posi i e in ege numbe is gi en as inpu o a speci ied inpu neu on. In he o iginal model, as well as in
some ea ly a ian s, he 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 i is execu ed. 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. O he possibili ies exis o encode inpu and ou pu numbe s, as discussed
in [11]: as he numbe o spikes con ained in a gi en neu on a he beginning ( esp., he end) o he
compu a ion, as he numbe o spikes i ed in a gi en in e al o ime, e c.
A use ul ex ension o he s anda d model de ined abo e, al eady conside ed in [15, 16, 17, 13], is
o use se e al inpu neu ons, so ha he in oduc ion o he encoding o an ins ance o he p oblem o
be sol ed can be done in a as e way, in oducing pa s o he code in pa allel in a ious inpu neu ons.
Fo mally, we can de ine an SN P sys em o deg ee (m, ℓ), wi h m≥1and 0≤ℓ≤m, jus like a
s anda d SN P sys em o deg ee m, he only di e ence being ha now he e a e ℓinpu neu ons deno ed
by in1, . . . , inℓ. A alid inpu o an SN P sys em o deg ee (m, ℓ)is a se o ℓbina y sequences, ha
collec i ely encode an ins ance o a p oblem.
4A. Lepo a i, M.A. Gu i´e ez-Na anjo /Sol ing SUBSET SUM by Spiking Neu al P Sys ems
The p e ious de ini ions co e many ypes o sys ems/beha io s. By neglec ing he ou pu neu on
we can de ine accep ing SN P sys ems, in which he na u al numbe (o he ec o o na u al numbe s, in
he case o sys ems ha ing ℓ > 1inpu neu ons) gi en in inpu is accep ed i he compu a ion hal s. 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. In [12] 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 be ob ained also o some es ic ed o ms o SN P sys ems: [10] shows
ha one o he ollowing ea u es can be a oided while keeping uni e sali y: ime delay 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.
In [6] i is shown ha uni e sali y is kep e en i we emo e some combina ions o wo o he abo e
ea u es. Finally, in [30] he beha io o SN P sys ems on in ini e s ings and he gene a ion o in ini e
sequences o 0and 1was in es iga ed, whe eas in [3] SN P sys ems we e s udied as language gene a o s
(o e he bina y alphabe {0,1}).
Spiking neu al P sys ems can also be used o sol e decision p oblems, bo h in a semi–uni o m and in
auni o m way. When sol ing a p oblem Qin he semi–uni o m se ing, o each speci ied ins ance Io
Qwe build an SN P sys em ΠQ,I, whose s uc u e and ini ial con igu a ion depend upon I, ha hal s (o
emi s a speci ied numbe o spikes in a gi en in e al o ime) i and only i Iis a posi i e ins ance o
Q. On he o he hand, a uni o m solu ion o Qconsis s in a amily {ΠQ(n)}n∈No SN P sys ems such
ha , when ha ing an ins ance I ∈ Qo size n, we in oduce a polynomial (in n) numbe o spikes in
a designa ed (se o ) inpu neu on(s) o ΠQ(n)and he compu a ion hal s (o , al e na i ely, a speci ied
numbe o spikes is emi ed in a gi en in e al o ime) i and only i Iis a posi i e ins ance. The
p e e ence o uni o m solu ions o e semi–uni o m ones is gi en by he ac ha hey a e mo e s ic ly
ela ed o he s uc u e o he p oblem, a he han o speci ic ins ances. I he ins ances o a p oblem Q
depend upon wo pa ame e s (as is he case o SUBSET SUM, whe e n+1 is he numbe o in ege alues
o he gene ic ins ance (V={ 1, 2,..., n}, S), and kis he numbe o bi s needed o ep esen each
o hese alues), hen we will deno e he amily o SN P sys ems ha sol es Q by {ΠQ(hn, ki)}n,k∈N,
whe e hn, kiindica es he posi i e in ege numbe ob ained by applying an app op ia e bijec ion ( o
example, Can o ’s pai ing) om N2 o N.
The p esen pape conside s SN P sys ems o sol ing decision p oblems, con inuing he pape s
[15], [16] and [17], whe e one deals wi h he NP-comple e decision p oblems SUBSET SUM,SAT and
3-SAT. Fo all hese p oblems, cons an ime and polynomial ime solu ions we e p o ided by using SN P
sys ems cons uc ed bo h in he semi–uni o m and in he uni o m se ing, wo king in a non–de e minis ic
way, and also using a se ies o ing edien s added o SN P sys ems o he s anda d o m: ules ha p oduce
se e al spikes a a ime, he possibili y o ha e a choice be ween spiking ules and o ge ing ules,
o ge ing ules con olled by egula exp essions, ules applied in he maximally pa allel way, e c. He e
we conside a di e en si ua ion: we assume ha a p e–compu ed (s anda d) SN P sys em is gi en in
ad ance, possibly ha ing an exponen ial size wi h espec o he size o he ins ances o he p oblem we
wan o sol e, and we p o ide a semi–uni o m and a uni o m cons uc ions ha sol e SUBSET SUM in a
polynomial ime. All he sys ems we will p opose wo k in a de e minis ic way. No e ha his se ing was
al eady conside ed in [13], whe e polynomial ime uni o m solu ions o SAT and 3-SAT we e p o ided.
An impo an obse a ion is ha we will no speci y how ou p e–compu ed sys ems could be buil .
Howe e , we equi e ha such sys ems ha e a egula s uc u e, and ha hey do no con ain nei he
“hidden in o ma ion” ha simpli y he solu ion o speci ic ins ances, no an encoding o all possible
A. Lepo a i, M.A. Gu i´e ez-Na anjo/Sol ing SUBSET SUM by Spiking Neu al P Sys ems 5
solu ions ( ha is, an exponen ial amoun o in o ma ion ha allows o chea while sol ing he ins ances
o he p oblem). These equi emen s we e inspi ed by open p oblem Q27 in [29]. Le us no e in passing
ha he egula i y o he s uc u e o he sys em is ela ed o he concep o uni o mi y, ha in some sense
measu es he di icul y o cons uc ing he sys em. Fo example, when conside ing amilies {C(n)}n∈N
o Boolean ci cui s, o o he compu ing de ices whose numbe o inpu s depends upon an in ege pa am-
e e n≥1, i is equi ed ha o each n∈Na “ easonable” desc ip ion (see [2] o u he discussion
on he meaning o he e m “ easonable” in his con ex ) o C(n), he ci cui o he amily which has n
inpu s, can be p oduced in polynomial ime and loga i hmic space (wi h espec o n) by a de e minis ic
Tu ing machine whose inpu is 1n, he una y ep esen a ion o n. In his pape we will no del e u he
in o he de ails conce ning uni o mi y; we jus ely on eade ’s in ui ion, by s a ing ha i should be
possible o build he en i e s uc u e o he sys em using only a polynomial amoun o in o ma ion and a
con olled eplica ion mechanism, as i al eady happens in P sys ems wi h cell di ision.
The pape is o ganized as ollows. In Sec ion 2 we ecall he de ini ion o he SUBSET SUM p oblem,
as well as a classical solu ion algo i hm based on he dynamic p og amming pa adigm. In Sec ion 3 we
elabo a e such an algo i hm o ob ain a amily o SN P sys ems ha sol es SUBSET SUM in a semi–
uni o m way. In Sec ion 4 we p opose a comple ely di e en cons uc ion, ha allows us o uni o mly
sol e all he ins ances o SUBSET SUM o any speci ied size; he ins ances a e p o ided in inpu o
he sys ems o he amily by speci ying hei alues in bina y o m. Finally, Sec ion 5 con ains he
conclusions and some di ec ions o u he esea ch.
2. The SUBSET SUM P oblem
SUBSET SUM is one o he mos known NP-comple e decision p oblems. We can s a e i as ollows, in a
o m which is equi alen o he one gi en in [7, p. 223].
P oblem 1. NAME: SUBSET SUM.
•INSTANCE: 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.
•QUESTION: is he e a sub(mul i)se B⊆Vsuch ha P
b∈B
b=S?
The ollowing well known algo i hm [5] sol es SUBSET SUM by using he dynamic p og amming
echnique. In pa icula , he algo i hm e u ns 1on posi i e ins ances, and 0on nega i e ins ances.
SUBSET 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]

6A. Lepo a i, M.A. Gu i´e ez-Na anjo /Sol ing SUBSET SUM by Spiking Neu al P Sys ems
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 M
whose 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 1i 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 SUBSET 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 may wo k in
exponen ial ime and space. This beha io is usually e e ed o in he li e a u e by elling ha SUBSET
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 polynomial 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
SUBSET 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 . Indeed, SUBSET SUM is no NP-comple e in he s ong sense,
meaning ha i does no emain NP-comple e when we ep esen i s ins ances in una y o m [7]. S a ed
o he wise, s ongly NP-comple e p oblems emain NP-comple e e en when he numbe s con ained in o
hei ins ances a e small.
As a consequence o hese obse a ions, he SN P sys ems ha we will conside in Sec ion 4 will
ake in inpu he ins ances o SUBSET SUM as n+ 1 s ings encoded in bina y o m, whe e he leng h o
each s ing will be k= log K. Be o e p esen ing he uni o m solu ion o Sec ion 4, in he nex sec ion
we i s elabo a e he abo e dynamic p og amming algo i hm o p o ide a semi–uni o m amily o SN P
sys ems ha sol es he SUBSET SUM p oblem.
3. A Semi–uni o m Solu ion o SUBSET SUM
Le SS(n, k)deno e he se o ins ances o SUBSET SUM which can be buil by using n+1 posi i e k-bi
in ege numbe s. In his sec ion we p esen a semi–uni o m amily {Π(I)}I∈SS(n,k)o SN P sys ems
such ha o e e y I ∈ SS(n, k) he sys em Π(I)de e mines whe he I= ({ 1, 2,..., n}, S)is a
posi i e ins ance o SUBSET SUM. The size o Π(I)will be Θ(nS), hence exponen ial wi h espec o
he ins ance size. Howe e , he compu a ion ime o Π(I)will be linea in nand independen o k.
Sys em Π(I)is depic ed in Figu e 1 in a schema ic way. The sys em is composed o nlaye s, ho -
izon ally a anged (no e ha Figu e 1 is o a ed by 90 deg ees coun e clockwise), one o each i e a ion
o he dynamic p og amming algo i hm illus a ed in he p e ious sec ion. The compu a ion s a s in
A. Lepo a i, M.A. Gu i´e ez-Na anjo/Sol ing SUBSET SUM by Spiking Neu al P Sys ems 7
Figu e 1. A schema ic iew o he sys em Π(I)used o sol e a speci ic ins ance I= ({ 1, 2,..., n}, S)o
SUBSET SUM, whe e each o he alues 1, 2,..., n, S is a k-bi posi i e in ege numbe .
8A. Lepo a i, M.A. Gu i´e ez-Na anjo /Sol ing SUBSET SUM by Spiking Neu al P Sys ems
he i s ( he uppe mos ) laye , and p oceeds downwa ds un il he lowes (i.e., he n- h) laye has been
eached. The neu ons o he i s laye con ain he i ing ule a→a; 0, ha p opaga es he spikes e en-
ually con ained in hese neu ons o he app op ia e neu ons o he second laye . All he o he neu ons,
om laye 2 down o laye n, con ain wo i ing ules:
a→a; 0 and a2→a; 0
ha make he neu ons ope a e like OR Boolean ga es.
The connec ions among he neu ons depend upon he ins ance I= ({ 1, 2,..., n}, S)o SUBSET
SUM o be sol ed. P ecisely, o de e mine he alue o M[i, j]in he abo e algo i hm we need o compu e
he maximum be ween he alues M[i−1, j]and M[i−1, j− i], p o ided ha j− i≥0, o he wise we
pu M[i, j]equal o M[i−1, j]. The a ionale behind hese o mulas is he ollowing: as s a ed abo e,
M[i, j]has o be se o 1i and only i he e exis s a subse o { 1, 2,..., i}such ha he sum o i s
elemen s is equal o j. Thus we ha e wo possibili ies: ei he he subse con ains i, o no . In he o me
case, he e mus be a subse o { 1, 2,..., i−1}such ha he sum o i s elemen s is equal o j− i
( ha is, M[i−1, j − i]mus be 1); in he la e case, he e mus be a subse o { 1, 2,..., i−1}whose
elemen s sum up o j( ha is, M[i−1, j] = 1). I j < i hen clea ly icanno be in any subse o
{ 1, 2, . . . , i}whose sum is equal o j, and hus in his case we only check he alue o M[i−1, j]. I
i= 1 hen hese o mulas canno clea ly be applied. Howe e , we no e ha he only wo subse s o { 1}
we can build a e he emp y se ∅and { 1}i sel , hence M[1,0] = M[1, 1] = 1 whe eas M[1, j] = 0
o all j6∈ {0, 1}. Since he admissible alues o M[i−1, j]and o M[i−1, j − i]a e 0and 1,
compu ing he maximum is he same as compu ing a logical OR. In he sys em depic ed in Figu e 1, he
j- h neu on om he le , 0≤j≤S, co esponds o M[i, j]. We deno e 1( esp., 0) by he p esence
( esp., absence) o a spike. Such a neu on, o 1≤i≤n, has a synapse going o he neu on ha
Figu e 2. The wo cases o be conside ed o compu e he alue o M[i, j].
co esponds o M[i+ 1, j], and possibly (i i+1 +j≤S) ano he synapse going o he neu on ha
co esponds o M[i+ 1, j + i+1]. Such connec ions implemen he abo e ules ha de e mine he alue
o M[i, j], as one can easily check by looking a Figu e 2 (whe e he a en ion is ocused on he synapses
ha s a om he (i−1)- h laye and a i e o he neu on ha co esponds o M[i, j]). In he las laye ,
only he neu on ha co esponds o M[n, S]has a synapse going o a neu on named ou , which is he
ou pu neu on and does no con ain any ule.
A. Lepo a i, M.A. Gu i´e ez-Na anjo/Sol ing SUBSET SUM by Spiking Neu al P Sys ems 9
In he ini ial con igu a ion o he sys em, one spike is pu in he neu ons ha co espond o M[1,0]
and M[1, 1]; all he o he neu ons a e emp y. Du ing he i- h compu a ion s ep, wi h 1≤i≤n−1, he
neu ons in he i- h laye pe o m hei compu a ion, and send he co esponding esul o he app op ia e
neu ons o he nex laye . A he n- h compu a ion s ep, all he neu ons in he las laye send he spikes
p oduced by hem o he en i onmen (whe e hey a e los ) bu he igh mos neu on, ha sends he esul
o i s compu a ion (0o 1spikes) o neu on ou . Hence, he ins ance Io SUBSET SUM ep esen ed by
he s uc u e and he ini ial con igu a ion o Π(I)is posi i e i and only i one spike a i es in neu on ou
du ing he n- h compu a ion s ep. A e he esul o he compu a ion (0o 1spikes in neu on ou ) has
been p oduced, he compu a ion hal s and he spike e en ually con ained in neu on ou emains he e.
The compu a ion ime o Π(I)is linea in n, independen o he alues 1, 2,..., nand Scon ained
in I, bu he numbe o neu ons in he sys em is n(S+ 1) + 1, which is exponen ial wi h espec o
he ins ance size. This las ac would be conside ed unaccep able in adi ional complexi y heo y, bu
ecall ha in his pape (as well as in [13]) we a e assuming ha exponen ial size esou ces — encoded
in exponen ial size SN P sys ems o egula s uc u e — a e admi ed, p o ided ha hey do no con ain
hidden in o ma ion ha allow o chea while sol ing he ins ances o he p oblem.
The s uc u e o Π(I)is indeed e y egula : all he ins ances composed o nin ege alues plus
a equi ed sum equal o Sp oduce sys ems ha ing nlaye s, each composed o S+ 1 neu ons. The
alues 1, 2,..., nde e mine some o he connec ions be ween he neu ons (all he o he connec ions
go om e e y neu on in each laye o he neu on ha occu s in he same posi ion in he nex laye );
p ecisely, o all i∈ {1,2,...,n−1} he alue ide e mines he p esence o a synapse om e e y j- h
neu on in laye i, such ha j+ i+1 ≤S, o he (j+ i+1)- h neu on o laye i+ 1. Value 1also
de e mines he neu on in he i s laye (apa om he le mos ) ha will ecei e one spike in he ini ial
con igu a ion. An open ques ion, ha we will no add ess in his pape , is: wha kind o ope a ions a e
needed o augmen he powe o de e minis ic Tu ing machines so ha , gi en any ins ance Io SUBSET
SUM, he new machine is able o p oduce a “ easonable” desc ip ion o Π(I)in a polynomial ime?
No e ha in his case we should also ecas he meaning o he e m “ easonable”, since in [7] his no ion
conce ns only polynomial size cons uc ions.
4. A Uni o m Solu ion o SUBSET SUM
Le us p esen now a uni o m amily {Π(hn, ki)}n,k∈No SN P sys ems ha sol es he SUBSET SUM
p oblem in a uni o m way. P ecisely, o all n, k ∈N he sys em Π(hn, ki)will sol e all he ins ances
I ∈ SS(n, k)which a e composed o n+ 1 posi i e k-bi in ege numbe s. Such ins ances a e p o ided
in inpu in bina y o m, as a sequence o (n+1)kbi s ha a e ed o he sys em in pa allel (which means
ha each bi is inse ed in o an app op ia e inpu neu on).
Figu e 3 depic s he sys em Π(hn, ki)in a schema ic way. The ins ance I ∈ SS(n, k)is inse ed in o
he le mos neu ons, which a e labelled wi h a name ha indica es he bi which has o be inse ed. These
neu ons simply p opaga e hei spikes o subsys ems SUM1, SUM2,..., SUM2n−1by using a i ing ule
o ype a→a; 0. The SUM subsys ems a e bijec i ely associa ed o e e y possible non-emp y subse
o { 1, 2, . . . , n}. As he name indica es, e e y SUM subsys em compu es he sum o he elemen s o
he co esponding subse o { 1, 2,..., n}, and hus he synapses ou going om he le mos neu ons
e lec his si ua ion; ha is, a synapse lea ing om neu on i,j,1≤i≤nand 1≤j≤k, eaches
he subsys em SUMℓi and only i alue iis in ol ed in he sum compu ed by SUMℓ. The sums a e
16 A. Lepo a i, M.A. Gu i´e ez-Na anjo /Sol ing SUBSET SUM by Spiking Neu al P Sys ems
[9] Gu i´e ez-Na anjo, M. A., P´e ez-Jim´enez, M. J., Riscos-N´u˜nez, A.: A Fas P Sys em o Finding a Balanced
2–pa i ion. So Compu ing,9(9), 2005, 673–678.
[10] Iba a, O. H., P˘aun, A., P˘aun, Gh., Rod ´ıguez-Pa ´on,A., Sos´ık, P., Woodwo h, S.: No mal Fo ms o Spiking
Neu al P Sys ems, Theo e ical Compu e Science,372(2–3), 2007, 196–217.
[11] Ionescu, M., P˘aun, A., P˘aun, Gh., P´e ez-Jim´enez, M. J.: Compu ing wi h Spiking Neu al P Sys ems: T aces
and Small Uni e sal Sys ems, DNA Compu ing, 12 h In e na ional Mee ing on DNA Compu ing (DNA12),
Re ised Selec ed Pape s (C. Mao, T. Yokomo i, B.-T. Zhang, Eds.), LNCS 4287, Sp inge -Ve lag, Be lin,
2006, 1–16.
[12] Ionescu, M., P˘aun, Gh., Yokomo i, T.: Spiking Neu al P Sys ems, Fundamen a In o ma icae,71(2-3), 2006,
279–308.
[13] Ishdo j, T.-O., Lepo a i, A.: Uni o m Solu ions o SAT and 3-SAT by Spiking Neu al P Sys ems wi h P e-
compu ed Resou ces, Na u al Compu ing, in p ess, DOI 10.1007/s11047-008-9081-0.A p elimina y e sion
appea ed as Tu ku Cen e o Compu e Science – TUCS Repo No. 876, 2008.
[14] K ishna, S. N., Rama, R.: A Va ian o P Sys ems wi h Ac i e Memb anes: Sol ing NP-comple e P oblems,
Romanian Jou nal o In o ma ion Science and Technology,2(4), 1999, 357–367.
[15] Lepo a i, A., Mau i, G., Zand on,C., P˘aun, Gh., P´e ez-Jim´enez, M. J.: Uni o mSolu ions o SAT and SUBSET
SUM by Spiking Neu al P Sys ems, submi ed.
[16] Lepo a i, A., Zand on,C., Fe e i, C., Mau i, G.: On he Compu a ional Powe o Spiking Neu al P Sys ems,
In e n. J. Uncon en ional Compu ing, 2007, in p ess.
[17] Lepo a i, A. Zand on,, C., Fe e i, C., Mau i, G.: Sol ing Nume ical NP–comple e P oblems wi h Spiking
Neu al P Sys ems, Memb ane Compu ing, In e na ional Wo kshop, WMC8, Selec ed and In i ed Pape s, (G.
Ele he akis, P. Ke alas, Gh. P˘aun, G. Rozenbe g, A. Salomaa, Eds.), LNCS 4860, Sp inge -Ve lag, Be lin,
2007. 336–352.
[18] Lepo a i, A., Zand on, C., Gu i´e ez-Na anjo, M. A.: P Sys ems wi h Inpu in Bina y Fo m, In e na ional
Jou nal o Founda ions o Compu e Science,17(1), 2006, 127–146.
[19] Maass, W.: Compu ing wi h spikes, Special Issue on Founda ions o In o ma ion P ocessing o TELEMATIK,
8(1), 2002, 32–36.
[20] Maass, W., Bishop, C. (Eds.), Pulsed Neu al Ne wo ks, MIT P ess, Camb idge (MA), 1999.
[21] Ma ´ın Vide, C., Pazos, J., P˘aun, Gh., Rod ´ıguez Pa ´on, A.: A New Class o Symbolic Abs ac Neu al Ne s:
Tissue P Sys ems, Compu ing and Combina o ics, 8 h Annual In e na ional Con e ence, COCOON 2002,
LNCS 2387, Sp inge -Ve lag, Be lin, 2002, 290–299.
[22] Ma ´ın Vide, C., Pazos, J., P˘aun, Gh., Rod ´ıguez Pa ´on, A.: Tissue P sys ems, Theo e ical Compu e Science,
296, 2003, 295–326.
[23] Ob ulowicz, A: De e minis ic P Sys ems o Sol ing SAT p oblem, Romanian Jou nal o In o ma ion Science
and Technology,4(1–2), 2001, 551–558.
[24] Papadimi iou, C. H.: Compu a ional Complexi y, Addison-Wesley, 1994.
[25] P˘aun, A., P˘aun, Gh.: Small Uni e sal Spiking Neu al P Sys ems, BioSys ems,90(1), 2007, 48–60.
[26] P˘aun, Gh.: Compu ing wi h Memb anes, Jou nal o Compu e and Sys em Sciences,1(61), 2000, 108–143.
See also Tu ku Cen e o Compu e Science – TUCS Repo No. 208, 1998.
[27] P˘aun, Gh.: Compu ing wi h Memb anes. An In oduc ion, Bulle in o he EATCS,67, 1999, 139–152.

A. Lepo a i, M.A. Gu i´e ez-Na anjo/Sol ing SUBSET SUM by Spiking Neu al P Sys ems 17
[28] P˘aun, Gh.: P Sys ems wi h Ac i e Memb anes: A acking NP-comple e P oblems, Jou nal o Au oma a,
Languages and Combina o ics,6(1), 2001, 75–90.
[29] P˘aun, Gh.: Memb ane Compu ing. An In oduc ion, Sp inge –Ve lag, Be lin, 2002.
[30] P˘aun, Gh., P´e ez-Jim´enez, M. J., Rozenbe g, G.: In ini e spike ains in spiking neu al P sys ems, submi ed.
[31] P˘aun, Gh., Rozenbe g, G.: A Guide o Memb ane Compu ing, Theo e ical Compu e Science,287(1), 2002,
73–100.
[32] P˘aun, Gh., Sakakiba a, Y., Yokomo i, T.: P Sys ems on G aphs o Res ic ed Fo ms, Publica iones Ma he-
ma icae Deb ecen,60, 2002, 635–660.
[33] P´e ez-Jim´enez, M. J., Riscos-N´u˜nez, A.: A Linea – ime Solu ion o he KNAPSACK P oblem Using P Sys-
ems wi h Ac i e Memb anes, Memb ane Compu ing, In e na ional Wo kshop, WMC 2003, Re ised Selec ed
and In i ed Pape s (C. Ma ´ın-Vide, Gh. P˘aun, G. Rozenbe g, A. Salomaa, Eds.), LNCS 2933, Sp inge -
Ve lag, Be lin, 2004, 250–268.
[34] P´e ez-Jim´enez, M. J., Riscos-N´u˜nez, A.: Sol ing he SUBSET SUM P oblem by Ac i e Memb anes, New
Gene a ion Compu ing,23(4), 2005, 367–384.
[35] Vollme , H.: In oduc ion o Ci cui Complexi y: A Uni o m App oach, Sp inge –Ve lag, Be lin, 1999.
[36] Zand on, C., Fe e i, C., Mau i, G.: Sol ing NP-comple e P oblems Using P Sys ems wi h Ac i e Mem-
b anes, Uncon en ional Models o Compu a ion (I. An oniou, C.S. Calude, M.J. Dinneen, Eds.), Sp inge -
Ve lag, Be lin, 2000, 289–301.
[37] The P sys ems Web page: h p://ppage.psys ems.eu