An E icien Cellula Solu ion
o he Pa i ion P oblem
Miguel Angel GUTI´
ERREZ-NARANJO
Ma io J. P´
EREZ-JIM´
ENEZ
Agus ´ın RISCOS-N ´
U˜
NEZ
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
E-mail: {magu ie , ma pe , a iscosn}@us.es
Abs ac . Nume ical p oblems a e no e y equen ly add essed in he P sys-
ems li e a u e. In his pape we p esen an e ec i e solu ion o he Pa i ion
p oblem ia a amily o de e minis ic P sys ems wi h ac i e memb anes using
2-di ision. The design o his solu ion is a sequel o se e al p e ious wo ks on
o he p oblems, mainly he Subse -Sum and he Knapsack p oblems bu also
he VALIDITY and SAT. Se e al imp o emen s a e in oduced and explained.
1 In oduc ion
Cellula Compu ing is a ecen b anch o Na u al Compu ing ini ia ed in [4]. I s goal is
o abs ac compu ing models om he s uc u e and he unc ioning o li ing cells.
The p esen pape is ocused in he design o a amily o P sys ems ha sol es a
nume ical NP-comple e p oblem, and in he o mal e i ica ion o his solu ion. Also he
simila i ies wi h he solu ions p esen ed in [6], [7], [9] and [10] will be highligh ed and
some conclusions will be ex ac ed om hem.
The analysis o he solu ion p esen ed he e will be done om he poin o iew o
he complexi y classes. A complexi y class o a model o compu a ion is a collec ion o
p oblems ha can be sol ed (o languages ha can be decided) by some de ices o his
model wi h simila compu a ional esou ces.
In his pape we p esen a polynomial complexi y class in cellula compu ing wi h
memb anes inspi ed in some ideas o Gh. P˘aun ([3], sec ion 7.1) discussed wi h some
membe s o he Resea ch G oup on Na u al Compu ing om he Uni e si y o Se ille.
This class allows us o de ec some in insic di icul ies o he esolu ion o a p oblem in
he model abo e men ioned.
The pape is o ganized as ollows: i s a o mal de ini ion o ecognize P sys ems is
gi en in he nex sec ion; hen, in sec ion 3 he polynomial complexi y class PMCAM is
in oduced; in sec ions 4 and 5 a cellula solu ion o he Pa i ion p oblem is p esen ed,
oge he wi h some commen s; and inally some inal ema ks a e gi en in sec ion 6.
237
2 P elimina ies
Recall ha a decision p oblem, X, is a pai (IX, θX) such ha IXis a language o e a
ini e alphabe (whose elemen s a e called ins ances) and θXis a o al boolean unc ion
o e IX.
De ini ion 1 AP sys em wi h inpu is a uple (Π,Σ, iΠ), whe e:
•Πis a P sys em, wi h wo king alphabe Γ, wi h pmemb anes labelled by 1, . . . , p, and
ini ial mul ise s M1, . . . , Mpassocia ed wi h hem.
•Σis an (inpu ) alphabe s ic ly con ained in Γ.
•The ini ial mul ise s a e o e Γ−Σ.
•iΠis he label o a dis inguished (inpu ) memb ane.
De ini ion 2 Le (Π,Σ, iΠ)be a P sys em wi h inpu . Le Γbe he wo king alphabe o Π,
µ he memb ane s uc u e, and M1,...,Mp he ini ial mul ise s o Π. Le mbe a mul ise
o e Σ. The ini ial con igu a ion o (Π,Σ, iΠ) wi h inpu mis (µ0, M0), whe e µ0=µ,
M0(j) = Mj, o each j6=iΠ, and M0(iΠ) = MiΠ∪m.
Rema k. 1 We deno e by IΠ he se o all inpu s o he P sys em Π. Tha is, IΠis a
collec ion o mul ise s o e Σ.
The compu a ions o a P sys em wi h inpu m∈M(Σ), a mul ise o e Σ, a e de ined
in a na u al way. The only no el y is ha he ini ial con igu a ion mus be he ini ial
con igu a ion o he sys em associa ed wi h he inpu mul ise m∈M(Σ).
In he case o P sys ems wi h inpu and wi h ex e nal ou pu , he concep o compu a-
ion is in oduced in a simila way bu wi h a small change. In he con igu a ions, we will
no wo k di ec ly wi h he memb ane s uc u e µbu wi h ano he s uc u e associa ed
wi h i including, in some sense, he en i onmen .
De ini ion 3 Le µ= (V(µ), E(µ)) be a memb ane s uc u e. The memb ane s uc u e
wi h en i onmen associa ed wi h µis he oo ed ee Ex (µ)such ha : (a) he oo o
he ee is a new node ha we will deno e en ;(b) he se o nodes is V(µ)∪©en ª; and
(c) he se o edges is E(µ)∪©{en , skin}ª. The node en is called en i onmen o he
s uc u e µ.
No e ha we ha e only included a new node ep esen ing he en i onmen which is only
connec ed wi h he skin, while he o iginal memb ane s uc u e emains unchanged. In
his way, e e y con igu a ion o he sys em in o ms abou he con en s o he en i onmen .
De ini ion 4 Alanguage accep ing P sys em is a P sys em wi h inpu ,
(Π,Σ, iΠ), and wi h ex e nal ou pu , such ha he ou pu alphabe con ains only
wo elemen s: Y es and No.
This de ini ion is s a ed in a gene al way, bu in his pape P sys ems wi hin he ac i e
memb ane model will be used. We e e o [3] (see chap e 7) o a de ailed de ini ion o
e olu ion ules, ansi ion s eps, and con igu a ions in his model.
Now le us de ine he Ou pu unc ion o ou P sys ems. Gi en a compu a ion C=
{Ci}i< , we will deno e by Mj
en he con en o he en i onmen in he con igu a ion Cj.
238
De ini ion 5 The ou pu o a compu a ion C={Ci}i< is:
Ou pu (C) = 


Y es, i Cis hal ing, Y es ∈M −1
en and No /∈M −1
en ,
No, i Cis hal ing, No ∈M −1
en and Y es /∈M −1
en ,
no de ined, o he wise.
I Csa is ies any o he wo i s condi ions, hen we say ha i is a success ul compu-
a ion.
De ini ion 6 A language accep ing P sys em is said o be alid i o e e y hal ing com-
pu a ion, and only o hem, one symbol Y es o one symbol No (bu no bo h) is sen ou
(in he las s ep o he compu a ion).
De ini ion 7 We say ha Cis an accep ing compu a ion ( espec i ely, ejec ing compu-
a ion) i he objec Y es ( espec i ely, No) appea s in he en i onmen associa ed wi h
he co esponding hal ing con igu a ion o C; ha is, i Y es =Ou pu (C)( espec i ely,
No =Ou pu (C)).
De ini ion 8 Alanguage ecognize P sys em is a alid language accep ing P sys em such
ha all i s compu a ions hal .
This ecognize sys ems a e specially sui able when ying o sol e decision p oblems.
3 The Complexi y Class PMCAM
Roughly speaking, a compu a ional complexi y s udy o a solu ion o a p oblem is an
es ima ion o he esou ces ( ime, space, ...) ha a e equi ed h ough all he p ocesses
ha ake place in he way om he ba e ins ance o he p oblem up o he inal answe .
The i s esul s abou “sol abili y” o NP–comple e p oblems in polynomial ime
(e en linea ) by cellula compu ing sys ems wi h memb anes we e ob ained using a ian s
o P sys ems ha lack an inpu memb ane. Thus, he cons uc i e p oo s o such esul s
need o design one sys em o each ins ance o he p oblem.
I we wan ed o pe o m such a solu ion o some decision p oblem in a labo a o y, we
will ind a d awback on his app oach: a sys em cons uc ed o sol e a conc e e ins ance is
useless when ying o sol e ano he ins ance. This handicap can be easily o e aken i we
conside a P sys em wi h inpu . Then, he same sys em could sol e di e en ins ances o
he p oblem, p o ided ha he co esponding inpu mul ise s a e in oduced in he inpu
memb ane.
Ins ead o looking o a single sys em ha sol es a p oblem, we p e e designing a
amily o P sys ems such ha each elemen decides all he ins ances o “equi alen size”,
in ce ain sense.
Be o e in oducing he de ini ion o he complexi y class we deal wi h, we need some
p elimina y no ions.
Le us deno e by AM he class o language ecognize P sys ems wi h ac i e memb anes
using 2-di ision (see [3], sec ion 7.2).
De ini ion 9 Le Lbe a language and Π= (Π( )) ∈Na amily o P sys ems wi h ac-
i e memb anes using 2-di ision. A polynomial encoding o Lin Πis a pai (cod, s)o
polynomial- ime compu able unc ions, cod :L→S ∈NIΠ( ), and s:L→Nsuch ha o
e e y u∈Lwe ha e cod(u)∈IΠ(s(u)).
239
Tha is, o each wo d uo he language L, we ha e a mul ise cod(u) and a numbe
s(u) associa ed wi h i such ha cod(u) is a mul ise o inpu o he P sys em Π(s(u)).
Lemma 3.1 Le L1⊆Σ∗
1and L2⊆Σ∗
2be languages. Le Π= (Π( )) ∈Na amily o
P sys ems wi h ac i e memb anes using 2-di ision. I : Σ∗
1→Σ∗
2is a polynomial- ime
educ ion om L1 o L2, and (cod, s)is a polynomial encoding o L2in Π, hen (g◦ , h◦ )
is a polynomial encoding o L1in Π.
P oo . This esul ollows di ec ly om he p e ious de ini ion. Fo a de ailed p oo , we
e e he eade o [9]. 2
Conside ing all he de ini ions al eady p esen ed, we a e now eady o gi e he de ini ion
o he complexi y class PMCAM, which is based on he one gi en in [9].
De ini ion 10 We will say ha a decision p oblem, X= (IX, θX), is sol able in poly-
nomial ime by a amily o language ecognize P sys ems wi h ac i e memb anes using
2-di ision, and we deno e his by X∈PMCAM, i he e exis s a amily o P sys ems,
Π=¡Π( )¢ ∈N, wi h he ollowing p ope ies:
1. The amily Πis consis en , wi h ega d o he class AM; ha is, ∀ ∈N(Π( )∈
AM).
2. The amily Πis polynomially uni o m, by Tu ing machines; ha is, he e exis s a
de e minis ic Tu ing machine cons uc ing Π( ) om in polynomial ime.
3. The e exis wo unc ions, cod :IX→S ∈NIΠ( )and s:IX→N+, compu able in
polynomial ime, such ha :
•Fo e e y u∈IX,cod(u)∈IΠ(s(u)).
•The amily Πis polynomially bounded, wi h ega d o (X,cod,s); ha is, he e
exis s a polynomial unc ion, p, such ha o each u∈IXe e y compu a ion
o he sys em Π(s(u)) wi h inpu cod(u)is hal ing and, mo eo e , i pe o ms
a mos p(|u|)s eps.
•The amily Πis sound, wi h ega d o (X,cod,s); ha is, o each u∈IXi
is e i ied ha i he e exis s an accep ing compu a ion o he sys em Π(s(u))
wi h inpu cod(u), hen θX(u) = 1.
•The amily Πis comple e, wi h ega d o (X,cod,s); ha is, o each u∈IX
i is e i ied ha i θX(u) = 1, hen e e y compu a ion o he sys em Π(s(u))
wi h inpu cod(u)is an accep ing one.
Rema k. 2 No e ha , as a consequence o he abo e de ini ion, he complexi y class
PMCAM is closed unde complemen (because we use ecognize P sys ems).
P oposi ion 1 Le Xand Ybe decision p oblems such ha Xis educible o Yin poly-
nomial ime. I Y∈PMCAM, hen X∈PMCAM.
Tha is, he complexi y class PMCAM is s able unde polynomial- ime educ ion. The
p oo o his esul can also be ound in [9].
240
4 Sol ing he Pa i ion P oblem in Linea Time
The Pa i ion p oblem can be s a ed as ollows:
Gi en a se Ao nelemen s, whe e each elemen has a “weigh ” wi∈N,
decide whe he o no he e exis s a pa i ion o Ain o wo subse s such ha
hey ha e he same weigh .
We will ep esen he ins ances o he p oblem using uples o he kind (n, (w1, . . . , wn)),
whe e nis he size o he se Aand (w1, . . . , wn) is he lis o weigh s o he elemen s om
A. We can de ine in a na u al way an addi i e unc ion w ha co esponds o he da a in
he ins ance.
We will add ess he esolu ion o he p oblem ia a b u e o ce algo i hm, in he ame-
wo k o language ecognize P sys ems wi h ac i e memb anes using 2-di ision, wi hou
coope a ion no p io i y among ules. Ou s a egy will consis in:
•Gene a ion s age: memb ane di ision is used un il a speci ic memb ane o each pai
(B, Bc) is ob ained, whe e Bis a subse o A ha con ains he elemen a1( his
condi ion is s a ed o a oid conside ing wice he same pai ).
•Calcula ion s age: in each memb ane he weigh o he associa ed subse and o i s
complemen a y a e calcula ed.
•Checking s age: in each memb ane i is checked whe he o no hese wo weigh s
coincide.
•Ou pu s age: he answe is deli e ed acco ding o he esul s o he checkings.
The amily p esen ed he e is
Π={(Π(n),Σ(n), i(n)) : n∈N}.
Fo each elemen o he amily, he inpu alphabe is Σ(n) = {x1, . . . , xn}, he inpu
memb ane is i(n) = e, and he P sys em Π(n) = (Γ(n),{e, , s}, µ, Me,M ,Ms, R) is
de ined as ollows:
•Wo king alphabe :
Γ(n) = {a0, a, b0, b, c, d0, d1, d2, e1, . . . , en, g, ¯g, ˆg, h0, h1, i1, i2, i4, i5, p, ¯p, q, x1, . . . , xn,
Y es, No, No0, z1, . . . , z2n+1,#}.
•Memb ane s uc u e: µ= [ [ ]e[ ] ]s.
•Ini ial mul ise s: Me=e1g;M =b0h0and Ms=z1.
•The se o e olu ion ules, R, consis s o he ollowing ules:
(a) [ei]0
e→[q]−
e[ei]+
e, o i= 1, . . . , n,
[ei]+
e→[ei+1]0
e[ei+1]+
e, o i= 1, . . . , n −1.
The goal o hese ules is o gene a e one memb ane o each subse o A ha con ains
a1. In each s ep (acco ding o he index o ei), we conside an elemen o Aand ei he we
add i o he subse associa ed wi h he memb ane, B, o we pu i in he complemen a y
subse , Bc.
241

(b) [x1→a0]0
e; [x1→¯p]+
e,
[xi→xi−1]+
e, o i= 2, . . . , n,
[xi→¯p]−
e, o i= 2, . . . , n.
In he beginning, he mul iplici ies o he objec s xj(wi h 1 ≤j≤n) encode he
weigh s o he co esponding elemen s o A. They a e no p esen in he de ini ion o he
sys em, bu hey a e inse ed as inpu in he memb ane labelled by ebe o e s a ing he
compu a ion: o each aj∈A,wjcopies o xjha e o be added o he inpu memb ane.
Du ing he compu a ion, a he same ime as elemen s a e added o he subse associa ed
wi h a memb ane, objec s a0and ¯pa e gene a ed o s o e he weigh o such subse and
o i s complemen a y.
(b2) [en]+
e→#,
[a0→#]0
s; [¯p→#]0
s, [g→#]0
s.
This ules pe o m a “cleaning” ask dissol ing he memb anes ha a e no meaning ul
and e asing he con en s ha hese dissolu ions spill in he skin memb ane. This is no
essen ial in he design, bu i is help ul.
(c) [q→i1]−
e, [¯p→p]−
e, [a0→a]−
e,
[g]−
e→[ ]−
e¯g.
When a memb ane ge s nega i ely cha ged, he wo i s s ages (i.e. gene a ion and
calcula ion s ages) end, and hen some ansi ion ules a e applied. Objec s a0and ¯p,
whose mul iplici ies encode he weigh s o he associa ed subse and o i s complemen a y,
a e enamed o he nex s age, when hei mul iplici ies a e compa ed. Also an objec g
is sen ou and he o al weigh o all he elemen s ha ha e no been conside ed in he
gene a ion s age is added o he complemen a y.
(d) [a]−
e→[ ]0
e#, [p]0
e→[ ]−
e#.
These ules implemen he compa ison abo e men ioned ( ha is, hey check whe he
w(B) = w(Bc) holds o no ). They wo k as a loop ha e ases objec s aand pone by one
al e na i ely, changing he cha ge o he memb ane in each s ep.
(e) [i1→i2]−
e, [i2→i1]0
e.
A ma ke ha con ols he p e ious loop is desc ibed he e. The index o ijand he
elec ic cha ge o he memb ane gi e enough in o ma ion o poin ou i he numbe o
objec s ais g ea e han (less han o equal o) he numbe o objec s p.
( ) [i1]0
e→[ ]+
eNo.
I a subse B⊆A e i ies ha w(B)> w(Bc), hen inside he ele an memb ane
ha encodes i ( his will be de ined la e ) he e will be less objec s p han a. This o ces
he loop desc ibed in (e) o hal : he momen will come when he e a e no objec s ple ,
and hen he ule [i2→i1]−
ewill be applied bu i will no be possible o apply he ule
[p]0
e→[ ]−
e# a he same ime. Thus, an objec i1will be p esen in he memb ane and
he la e will be neu ally cha ged, so he ule ( ) will be applied ending he checking
s age wi h nega i e esul .
(g) [i2→i4c]−
e,
[c]−
e→[ ]0
e#, [i4→i5]0
e,
[i5]0
e→[ ]+
eY es, [i5]−
e→[ ]+
eNo.
242
I , on he con a y, w(B)≤w(Bc) holds, hen he objec s awill be exhaus ed be o e
he objec s p. I is impo an o dis inguish be ween he cases whe e he mul iplici y
o pis s ic ly g ea e han he mul iplici y o aand he cases whe e bo h mul iplici ies
coincide. This is why objec cgi es again neu al cha ge o he memb ane and hen
objec i5checks i a ule [p]0
e→[e]−
e# is applied o no .
(h) [p→#]+
e, [a→#]+
e#.
I a e he checking loop o ules in (d) has inished he e a e s ill some objec s po
ain he memb ane, hey can be e ased (again, jus o “cleaning” pu poses).
(i) [¯g→ˆg]+
s,
ˆg[ ]+
e→[ˆg]0
e.
Be o e he answe is sen ou , he sys em has o make su e ha all he ele an
memb anes ha e inished hei checking s ages. This is done using he objec s g ha a e
p esen in he skin and he auxilia y memb ane labelled by (see he nex se o ules).
The e mus be 2n−1copies o g, because each ele an memb ane sends one, and he e is
one ele an memb ane o each B⊆Asuch ha a1∈B, ha is 2n−1in all.
(j) d0[ ]−
→[d0]0
,
[h0→h1]0
, [h1→h0]+
,
[b0]0
→[ ]+
b, ˆg[ ]+
→[ˆg]0
,
b[ ]0
→[b0]+
, [ˆg]+
→[ ]0
ˆg,
[h0]1
→[ ]+
d2, [d2]+
s→[ ]−
sd2.
The memb ane labelled by is p esen in he ini ial con igu a ion, bu emains
inac i e un il an objec d0“wakes i up”. The pu pose o he memb ane is o pe o m
a loop whe e he objec s ˆga e in ol ed, and hus we can de ec i he e a e no objec s
ˆgp esen in he skin egion. This ac will mean ha all he ele an memb anes ha e
inished hei checking s age, and ha he sys em is eady o send ou he answe (Y es
o No).
(k) [No →No0]−
s,
[Y es]−
s→[ ]0
sY es,
[No0]−
s→[ ]0
sNo.
Finally, he ou pu p ocess is ac i a ed. The skin memb ane needs o be nega i ely
cha ged be o e he answe is sen ou . Objec d2 akes ca e o his (see he p e ious se o
ules) and hen, i he answe is a i ma i e, an objec Y es will be sen ou eco e ing he
neu al cha ge o he skin. No e ha he answe Y es has some p io i y o e he nega i e
answe , in he sense ha we i s check i he e is any objec Y es and hen, i i is no he
case, he answe No will be sen ou .
5 Imp o ing he Design
I one s udies how he gene a ion s age wo ks, one can no ice ha he numbe o spa e
memb anes ha a e gene a ed and immedia ely dissol ed ( he ones wi h posi i e cha ge
and con aining he objec en) is ac ually 2n−1, he same amoun ha o ele an mem-
b anes. In he o mal model we do no wo y abou his, because his space is c ea ed
du ing he compu a ion, and hus i is no needed a p io i. Bu i we y o un a simula-
ion o he design in a compu e , hen he space complexi y becomes much mo e impo an .
243
E en i we use he ick o dissol ing he memb anes immedia ely a e being gene a ed,
he esou ces used a e oo much.
A possible solu ion is o a oid he gene a ion o such useless memb anes. This can be
done o example using a di ision s a egy ha ollows a comple e bina y ee s uc u e.
We a e no using his s a egy because we ha e he in en ion o ge some o he ele an
memb anes be o e he gene a ion s age ends, ins ead o ge ing all he memb anes oge he
a e a linea numbe o s eps. This is mo i a ed because we a e looking o be e e iciency
in he bes o a e age case.
He e is a p oposal:
Gene a ion s age
[ei]0
e→[q]0
e[ei]+
e, o i= 1, . . . , n −1,
[en→q]e
0,
[ei]+
e→[ei+1]0
e[ei+1]+
e, o i= 1, . . . , n −2,
[en−1]+
e→[ ]0
e#,
[e0
i→e0
i+1]e
+, [e00
i→e0
i+1]e
+, o i= 1, . . . , n −2,
[e0
i→e00
i]e
0, [e00
i→λ]e
0, o i= 1, . . . , n −1,
[e0
n−1→en]e
+, [e00
n−1→en]e
+.
In his new app oach, we do no p oduce any useless memb ane, so he dissol ing ules
a e no longe needed. Fu he mo e, only wo elec ical cha ges a e used. Al hough he
sequence o elec ical cha ges o a memb ane is s ill meaning ul, he end o he s age is no
ma ked anymo e now by ge ing nega i e cha ge, bu by ha ing neu al cha ge o wo
consecu i e e olu ion s eps (see [1] o an example o using ac i e memb anes wi h only
wo cha ges). This condi ion is con olled by he “wi ness-objec s” e0
iand e00
i, ha show
whe he in he p e ious s ep he cha ge was 0 (e00
i) o + (e0
i).
I we wan o use hese ules ins ead o he ules in (a), hen he checking s age needs
also o be adap ed, and his could be done as ollows:
Weigh calcula ion s age
[x1→a0]0
e, [x1→¯p]+
e,
[x0
1→a0]0
e, [x0
1→¯p]+
e,
[xi→xi−1]+
e, o i= 2, . . . , n,
[x0
i→xi−1]+
e, o i= 2, . . . , n,
[xi→x0
i]0
e, o i= 2, . . . , n,
[x0
i→¯p]0
e, o i= 2, . . . , n.
This s age is almos he same as i was in he o me designs, bu again i is necessa y
o in oduce “wi ness-objec s” o de ec when he gene a ion s age inishes, because in
his momen he calcula ion s age mus also conclude.
244
6 Final Rema ks
The designs p oposed he e y o be as gene al as possible, and a he same ime we y
o be uni o m, in he sense ha he design o a amily o P sys ems ha sol es a p oblem
is no made hinking on one P sys em o each ins ance o he p oblem. Ins ead, each
P sys em o he amily can deal wi h a se o ins ances o he same size (in his case,
wi h he same alue o n, independen ly o he alues o he weigh unc ion), ecei ing a
he beginning o he compu a ion an inpu ha encodes he conc e e ins ance. I is also
impo an ha he numbe o s eps o he compu a ions is polynomial (p e e ably linea )
wi h espec o he inpu gi en; in he case o Pa i ion he numbe o s eps is o a linea
o de .
Se e al nume ical p oblems ha e al eady been sol ed wi h simila echniques: he
Subse -Sum p oblem ([6]), he Knapsack p oblem ([7]) and he Pa i ion p oblem (in
his pape ), among o he s. This ac gi es ise o he ollowing ques ion: is i possible
o o malize a p ocedu e o “ eusing ules”? This ques ion is add essed in [11], in his
olume.
Some i s a emp s in his di ec ion ha e al eady been made, in he amewo k o he
P sys ems simula o in P olog (see [2]). Se e al iles ha e been c ea ed, con aining he
ins uc ions o gene a e he e olu ion ules ha deal wi h he di e en p oblems ( ollowing
he schemes gi en in he co esponding designs), and now we a e wo king o pu hese
iles oge he and euse somehow he in o ma ion.
Ano he esea ch opic ela ed wi h hese ideas is ying o o malize wha means poly-
nomial educ ion pe o med by P sys ems. I will be nice o ha e a de ini ion o a complex-
i y class ha only depends on P sys ems pa ame e s, wi hou including a polynomial- ime
p ecompu ing p ocess (which is somehow unna u al).
Finally, he omnip esen bu den o memb ane compu ing: s ill no implemen ed in
labs (nei he in o he physical means). Chemical p ocesses in na u e a e o en cyclic,
o e e sible. Maybe ins ead o ying o b idge he de ini ion o he P sys ems model
wi h biology, a mo e eachable goal is o b idge he “sub ou ines language” o memb ane
compu ing wi h cellula biochemis y.
Acknowledgemen s. The suppo o his esea ch h ough he p ojec TIC2002-
04220-C03-01 o he Minis e io de Ciencia y Tecnolog´ıa o Spain, co inanced by FEDER
unds, is g a e ully acknowledged.
Re e ences
[1] Alhazo , A., F eund, R., P˘aun, Gh.: P sys ems wi h ac i e memb anes and wo
pola iza ions, in he p esen olume.
[2] Co d´on-F anco, A., Gu i´e ez-Na anjo, M.A., P´e ez-Jim´enez, M.J. Sancho-Capa ini,
F.: A P olog simula o o de e minis ic P sys ems wi h ac i e memb anes, New
Gene a ion Compu ing, o appea .
[3] P˘aun, Gh.: Memb ane Compu ing. An in oduc ion, Sp inge -Ve lag, Be lin, 2002.
[4] P˘aun, Gh.: Compu ing wi h memb anes, Jou nal o Compu e and Sys em Sciences,
61, 1 (2000), 108–143.
245