A uni o m solu ion o SAT using memb ane c ea ion
Miguel A. Gu i´
e ez-Na anjo, Ma io J. P´
e ez-Jim´
enez∗, F ancisco J. Rome o-Campe o
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
Abs ac
In li ing cells, new memb anes a e p oduced basically h ough wo p ocesses: mi osis and au opoiesis. These wo p ocesses
ha e inspi ed wo a ian s o cell-like memb ane sys ems, namely P sys ems wi h ac i e memb anes and P sys ems wi h memb ane
c ea ion. In his pape , we p o ide he i s u ni o m, e icien so lu ion o h e SAT p oblem in h e amewo k o e cognise P
sys ems wi h memb ane c ea ion using dissolu ion ules. Recen ly he au ho s ha e p o ed ha i he dissolu ion ules a e no
allowed o be used, hen he polynomial complexi y class associa ed wi h his a ian o P sys ems is he s anda d complexi y
class P. This esul , oge he wi h he main esul o his pape , shows he su p ising ole o he appa en ly “innocen ” ope a ion o
memb ane dissolu ion. The use o his ype o ule es ablishes he di e ence be ween e iciency and non-e iciency o P sys ems
wi h memb ane c ea ion, and p o ides a ba ie be ween P and NP (assuming P 6= NP).
Keywo ds: Na u al compu ing; Memb ane compu ing; Cellula complexi y classes; SAT p oblem
1. In oduc ion
Memb ane compu ing is an eme gen b anch o na u al compu ing in oduced by P˘
aun in [12]. Since hen, i has
ecei ed impo an a en ion om he scien i ic communi y. In ac , memb ane compu ing has been selec ed by he
Ins i u e o Scien i ic In o ma ion, USA, as a Fas Eme ging Resea ch F on in Compu e Science, and [11] was
men ioned in [14] as a highly ci ed pape in Oc obe 2003.
This non-de e minis ic model o compu a ion s a s om he assump ion ha he p ocesses aking place in he
compa men al s uc u es o li ing cells can be in e p e ed as compu a ions. The de ices o his model a e called P
sys ems.
Roughly speaking, a P sys em consis s o a cell-like memb ane s uc u e, in he compa men s o which one
places mul ise s o objec s ha e ol e acco ding o gi en ules in a synch onous non-de e minis ic maximally pa allel
manne .1The ep esen a ion o da a as mul ise s is an abs ac ion om he way in which chemical compounds a e
ound in li ing cells. Memb ane compu ing is a c oss-disciplina y ield, wi h con ibu ions by compu e scien is s,
∗Co esponding au ho . Tel.: +34 954557952; ax: +34 954557952.
E-mail add ess: [email p o ec ed] (M.J. P´
e ez-Jim´
enez).
1An in oduc ion can be ound in [6], and upda ed in o ma ion a [15].
biologis s, o mal linguis s and complexi y heo e icians, en iching each o he s’ esul s and p oblems, and p omising
new esea ch lines.
In his pape , we p esen a con ibu ion om he compu a ional side. We in oduce a amily o P sys ems wi h
memb ane c ea ion, cons uc ed in a uni o m way, ha sol es he p oblem o de e mining, o a gi en o mula in
conjunc i e no mal o m, whe he i is sa is iable o no ( he SAT p oblem).
The pape is o ganised as ollows: i s P sys ems wi h memb ane c ea ion a e in oduced in he nex sec ion. In
Sec ion 3, ecognise P sys ems (de ices ha cap u e he in ui i e idea unde lying he concep o an algo i hm) a e
p esen ed. The solu ion in he amewo k o memb ane c ea ion o he SAT p oblem is gi en in Sec ion 4. Finally,
some o mal de ails and conclusions a e gi en.
2. P sys ems wi h memb ane c ea ion
Polynomial solu ions o NP-comple e p oblems in memb ane compu ing a e p oduced by ading ime o space.
This is inspi ed by he capabili y o cells o p oduce an exponen ial numbe o new memb anes (new wo kspaces)
in polynomial ime. Basically, he e a e wo ways o p oducing new memb anes in li ing cells: mi osis (memb ane
di ision) and au opoiesis (memb ane c ea ion, see [5]). Bo h ways o gene a ing new memb anes ha e gi en ise o
di e en a ian s o P sys ems: P sys ems wi h ac i e memb anes, whe e he new wo kspace is gene a ed by memb ane
di ision, and P sys ems wi h memb ane c ea ion, whe e he new memb anes a e c ea ed om objec s. Bo h models
ha e been p o ed o be uni e sal, bu up o now he e is no heo e ical esul p o ing ha hese models simula e
each o he in polynomial ime. P sys ems wi h ac i e memb anes ha e been success ully used o design solu ions o
NP-comple e p oblems, as SAT [10], Subse Sum [7], Knapsack [8], Bin Packing [9] and Pa i ion [2], bu as P˘
aun
poin ed in [13]“memb ane di ision was much mo e ca e ully in es iga ed han memb ane c ea ion as a way o ob ain
ac able solu ions o ha d p oblems”.
In his pape , we in es iga e he second a ian men ioned abo e. Memb anes a e c ea ed in li ing cells, o
ins ance, in he p ocess o esicle media ed anspo , and in o de o keep molecules close o each o he o acili a e
hei eac ions. Memb anes can also be c ea ed in a labo a o y—see [5]. He e, we abs ac he ope a ion o he c ea ion
o new memb anes unde he in luence o exis ing chemical subs ances o de ine P sys ems wi h memb ane c ea ion.
Recall ha a P sys em wi h memb ane c ea ion is a cons uc o he o m Π=(O,H, µ, w1, . . . , wm,R), whe e
m≥1 is he ini ial deg ee o he sys em; Ois he alphabe o objec s, and His a ini e se o labels o memb anes;
µis a memb ane s uc u e, consis ing o mmemb anes injec i ely labelled wi h elemen s o H, and w1, . . . , wma e
s ings o e O, desc ibing he mul ise s o objec s placed in he m egions o µ;Ris a ini e se o ules, o he o ms:
(a) [a→ ]hwhe e h∈H,a∈Oand is a s ing o e Odesc ibing a mul ise o objec s (objec e olu ion ules)
associa ed wi h memb anes and depending only on he label o he memb ane.
(b) a[ ]h→ [b]hwhe e h∈H,a,b∈O (send-in communica ion ules). An objec is in oduced in he memb ane,
possibly modi ied.
(c) [a]h→ [ ]hbwhe e h∈H,a,b∈O (send-ou communica ion ules). An objec is sen ou o he memb ane,
possibly modi ied.
(d) [a]h→bwhe e h∈H,a,b∈O (dissolu ion ules). A memb ane is dissol ed in eac ion wi h an objec , which
can be modi ied.
(e) [a→ [ ]h2]h1whe e h1,h2∈H,a∈Oand is a s ing o e Odesc ibing a mul ise o objec s (c ea ion ules).
In eac ion wi h an objec , a new memb ane is c ea ed. This new memb ane is placed inside o he memb ane o
he objec , which igge s he ule and has associa ed an ini ial mul ise and a label.
Rules a e applied acco ding o he ollowing p inciples:
•Rules om (a) o (d) a e used as is usual in he amewo k o memb ane compu ing, i.e., in a maximal pa allel
way. In one s ep, each objec in a memb ane can only be used o one ule (non- de e minis ically chosen), bu any
objec which can e ol e by a ule mus do i (wi h he es ic ions indica ed below).
•Rules o ype (e) a e used also in a maximal pa allel way. Each objec ain a memb ane labelled wi h h1p oduces
a new memb ane wi h label h2, placing in i he mul ise o objec s desc ibed by he s ing .
•I a memb ane is dissol ed, i s con en (mul ise and in e io memb anes) becomes pa o he immedia ely ex e nal
one. The skin is ne e dissol ed.
•All he elemen s which a e no in ol ed in any o he ope a ions o be applied emain unchanged.
•Rules associa ed wi h he label ha e used o all memb anes wi h his label, i espec i e o whe he he memb ane
is an ini ial one o whe he i was c ea ed.
•Se e al ules can be applied o di e en objec s in he same memb ane simul aneously. The excep ions a e he ules
o ype (d), since a memb ane can be dissol ed only once.
3. Recognise P sys ems wi h memb ane c ea ion
Recognise P sys ems we e in oduced in [8], and a e he na u al amewo k o s udy and sol e decision p oblems,
since deciding whe he an ins ance has an a i ma i e o nega i e answe is equi alen o deciding i a s ing belongs
o he language associa ed wi h he p oblem o no .
In he li e a u e, ecognise P sys ems a e associa ed in a na u al way wi h P sys ems wi h inpu . The da a ela ed o
an ins ance o he decision p oblem has o be p o ided o he P sys em in o de o i o compu e he app op ia e answe .
This is done by codi ying each ins ance as a mul ise placed in an inpu memb ane. The ou pu o he compu a ion,
(yes o no), is sen o he en i onmen . In his way, P sys ems wi h inpu and ex e nal ou pu a e de ices which can
be seen as black boxes, in which he use p o ides he da a be o e he compu a ion s a s, and he P sys em sends
o he en i onmen he ou pu in he las s ep o he compu a ion. Ano he impo an ea u e o P sys ems is hei
non-de e minism. The design o a amily o ecognise P sys ems has o conside i , because all possibili ies in he
non-de e minis ic compu a ions ha e o ou pu he same answe . This can be summa ised in he ollowing de ini ions
( aken om [1]).
De ini ion 1. AP sys em wi h inpu is a uple (Π,Σ,iΠ), whe e: (a) Πis a P sys em, wi h wo king alphabe Γ,
wi h pmemb anes labelled by 1, . . . , p, and ini ial mul ise s w1, . . . , wpassocia ed wi h hem; (b) Σis an (inpu )
alphabe s ic ly con ained in Γ; he ini ial mul ise s a e o e Γ−Σ; and (c) iΠis he label o a dis inguished (inpu )
memb ane.
Le mbe a mul ise o e Σ. The ini ial con igu a ion o (Π,Σ,iΠ)wi h inpu m is (µ, w1, . . . , wiΠ∪m, . . . wp).
De ini ion 2. A ecognise P sys em is a P sys em wi h inpu , (Π,Σ,iΠ), and wi h ex e nal ou pu such ha :
(1) The wo king alphabe con ains wo dis inguished elemen s, yes and no.
(2) All i s compu a ions hal .
(3) I Cis a compu a ion o Π, hen ei he some objec yes o some objec no (bu no bo h) mus ha e been eleased
in o he en i onmen , and only in he las s ep o he compu a ion.
We say ha Cis an accep ing compu a ion ( espec i ely, ejec ing compu a ion) i he objec yes ( espec i ely, no)
appea s in he ex e nal en i onmen associa ed wi h he co esponding hal ing con igu a ion o C.
In he nex sec ion, we p esen a uni o m solu ion o he SAT p oblem in linea ime in he ollowing sense.
De ini ion 3. Le Fbe a class o ecognise P sys ems. A decision p oblem X=(IX, θX)is sol able in polynomial
ime by a amily Π=(Π(n))n∈N, o P sys ems om F, and we deno e his by X∈PMCF, i he ollowing holds:
•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 Π(n) om n∈Nin polynomial ime.
•The e exis a pai (cod,s)o polynomial- ime compu able unc ions o e IXsuch ha :
−Fo each ins ance u∈IX,s(u)is a na u al numbe and cod(u)is an inpu mul ise o he sys em Π(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∈IX, each compu a ion o Π(s(u)) wi h inpu cod(u)pe o ms a mos p(|u|)s eps.
−The amily Πis sound wi h ega d o (X,cod,s); i.e., o each u∈IX, i he e exis s an accep ing compu a ion
o Π(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 θX(u)=1, hen e e y
compu a ion o Π(s(u)) wi h inpu cod(u)is an accep ing one.
In he abo e de ini ion we ha e imposed a equi emen o e e y P sys em Π(n) o be con luen , in he ollowing
sense: e e y compu a ion o a sys em wi h he same inpu mus always gi e he same answe .
I can be p o ed ha he class PMCFis closed unde polynomial- ime educ ion and complemen , see [10]. In his
pape , we will deal wi h he class MC o ecognise P sys ems wi h memb ane c ea ion.
4. Sol ing SAT in linea ime wi h memb ane c ea ion
The SAT p oblem is he ollowing: Gi en a Boolean o mula in conjunc i e no mal o m (CNF), o de e mine
whe he o no i is sa is iable, ha is, whe he he e exis s an assignmen o i s a iables on which i e alua es o ue.
In his sec ion, we desc ibe a amily o P sys ems which sol es his p oblem. We will add ess he esolu ion ia
a b u e o ce algo i hm, in he amewo k o ecognise P sys ems wi h memb ane c ea ion, which consis s in he
ollowing s ages:
•Gene a ion and e alua ion s age: Using memb ane c ea ion, we will gene a e all possible assignmen s associa ed
wi h he o mula and e alua e i o each.
•Checking s age: In each memb ane, we check whe he o no he o mula e alua es o ue on he assignmen
associa ed wi h i .
•Ou pu s age: The sys ems sends ou o he en i onmen he igh answe .
Le us conside he pai unc ion h,ide ined by hn,mi = ((n+m)(n+m+1)/2)+n. This unc ion is
polynomial- ime compu able (i is p imi i e ecu si e and bijec i e om N2on o N). Fo any gi en o mula in CNF,
ϕ=C1∧ · · · ∧ Cm, wi h n a iables and mclauses, we cons uc a P sys em Π(hn,mi)sol ing i . The e o e he
amily p esen ed he e is
Π= {(Π(hn,mi), Σ(hn,mi), i(hn,mi)) :(n,m)∈N2}.
Fo each elemen o he amily, he inpu memb ane is i(hn,mi)= , he inpu alphabe is Σ(hn,mi)= {xi,j,xi,j:
1≤i≤m,1≤j≤n}and he P sys em Π(hn,mi)=(Γ(hn,mi), {a, , ,1, . . . , m}, µ, wa, w ,R(hn,mi)) is
de ined as:
•Wo king alphabe : Γ(hn,mi)=Σ(hn,mi)∪ {xi,j,l,xi,j,l,zi,zi,l, j, j,l,dj:l= , ,1≤i≤n,1≤j≤
m} ∪ {yes,no,yesi,noj:0≤i≤9,0≤j≤2n+11} ∪ {q,k0,k1,k2, 0, 1, 2, 3}.
No e ha he size o he alphabe is 6nm +5n+4m+32 ∈Θ(nm), and ecall ha he size o an ins ance o he SAT
p oblem, a o mula wi h n a iables and mclauses, is o he o de Ω(nm); he e o e he size o he wo king alphabe
is linea on he size o he inpu .
•Ini ial memb ane s uc u e: µ= [ [ ]a]
•Ini ial Mul ise s: wa= {no0}w = {z0, ,z0, }
•The se o e olu ion ules, R(hn,mi), consis s o he ollowing ( ecall ha λdeno es he emp y s ing):
1.[zj, → [zj+1k0] ]l[zj, → [zj+1k0] ]l o l= , and j=0, . . . , n−2.
The goal o hese ules is o c ea e one memb ane o each assignmen o he a iables o he o mula. The new
memb ane wi h label , whe e he objec zj+1is placed, ep esen s he assignmen xj+1= ue; on he o he hand he
new memb ane wi h label , whe e he objec zj+1is placed ep esen s he assignmen xj+1= alse.
2.[xi j →xi,j, xi,j, ]l[ i→ i, i, ]l
[xi,j→xi,j, xi,j, ]l[zk→zk, zk, ]l) o l= , ;k=0, . . . , n−1
i=1, . . . , m;j=1, . . . n.
These ules duplica e he objec s ep esen ing he o mula so i can be e alua ed on he wo possible assignmen s,
xj= ue (xi,j, ,xi,j, ) and xj= alse (xi,j, ,xi,j, ). The objec s ia e also duplica ed ( i, , i, ) in o de o keep
ack o he clauses ha e alua e o ue on he p e ious assignmen s o he a iables. The objec s zkp oduce he
objec s zk, and zk, which will c ea e he new memb anes ep esen ing he wo possible assignmen s o he nex
a iable.
3.xi,1, [ ] → [ i] ,xi,1, [ ] → [λ]
xi,1, [ ] → [λ] ,xi,1, [ ] → [ i] ) o i=1, . . . , m.
Acco ding o hese ules, he o mula is e alua ed in he wo possible assignmen s o he a iable ha is being
analysed. The objec s xi,1, ( espec i ely xi,1, ) ge in o he memb ane labelled wi h ( espec i ely ), being
ans o med in o he objec s i ep esen ing ha he clause numbe ie alua es o ue on he assignmen xj+1= ue
( esp. xj+1= alse). On he o he hand, he objec s xi,1, ( espec i ely xi,1, ) ge in o he memb ane labelled wi h
( espec i ely ), p oducing no objec s. This signi ies ha hese objec s do no make he clause ue in he assignmen
xj+1= ue ( espec i ely xj+1= alse).
4.xi,j, [ ] → [xi,j−1] ,xi,j, [ ] → [xi,j−1]
xi,j, [ ] → [xi,j−1] ,xi,j, [ ] → [xi,j−1]
i, [ ] → [ i] , i, [ ] → [ i]





o i=1, . . . , m
j=2, . . . , n.
In o de o analyse he nex a iable, he second subsc ip s o he objec s xi,j,land xi,j,la e dec eased when hey a e
sen in o he co esponding memb ane, labelled wi h l. Mo eo e , ollowing he las ule, he objec s i,lge in o he
new memb anes o keep ack o he clauses ha e alua e o ue on he p e ious assignmen s.
5.[ks→ks+1]l[k2]l→λ o l= , ;s=0,1.
The objec s ki o i=0,1,2 a e coun e s ha dissol e memb anes when hey a e no use ul any longe du ing he
es o he compu a ion.
6.[zn−1, → [zn] ]l,[zn−1, → [zn] ]l,[zn→d1. . . dmq]l o l= , .
A he end o he gene a ion s age, he objec s zn−1,lc ea e wo new memb anes whe e he o mula will be e alua ed
on he wo possible assignmen s o he las a iable xn. The objec znis placed in bo h memb anes, and will p oduce
he objec s d1, . . . , dm,yes0, which will ake pa in he checking s age.
7.[di→ [ 0]i]l i, [ ]i→ [ i]i,[ i]i→λ
[ s→ s+1]i,[ 2]i→ 3) o i=1, . . . , m
s=0,1.
Following hese ules, each objec dic ea es a new memb ane wi h label iwhe e he objec 0is placed; his objec
will ac as a coun e . The objec ige s in o he memb ane labelled wi h iand dissol es i , p e en ing he coun e , i,
om eaching he objec 2. The ac ha he objec 2appea s in a memb ane wi h label imeans ha he e is no objec
i; ha is, he clause numbe idoes no e alua e o ue on he assignmen associa ed wi h he memb ane; he e o e
nei he does he o mula e alua e o ue no i s associa ed assignmen .
8.[q→ [yes0]a]l 3[ ]a→ [ 3]a[ 3]a→λ
[yesh→yesh+1]a,[yes5]a→yes6[yes6]l→yes7[ ]l) o l= ,
h=0, . . . , 4.
The objec qc ea es a memb ane wi h label awhe e he objec yes0is placed. The objec yeshe ol es o he objec
yesh+1; a he same ime he objec s 3can ge in o he memb ane labelled wi h aand dissol e i , p e en ing he objec
yes6 om being sen ou om his memb ane.
9.[nop→nop+1]a,[no2n+10]a→no2n+11
yes7[ ]a→ [yes8]a,[yes8]a→yes9
[yes9] →yes[ ] [no2n+11] →no[ ]





o p=0, . . . , 2n+9.
F om he beginning o he compu a ion, he objec nope ol es o he objec nop+1inside he memb ane labelled
wi h a. I any objec yes7is p oduced du ing he compu a ion, i means ha he o mula e alua es o ue on some
assignmen o i s a iables, and i ge s in o his memb ane and dissol es i , p oducing he objec yes9 ha will send
ou o he en i onmen he objec yes. On he o he hand, i no objec yes7appea s in he skin, he objec no2n+10
will dissol e he memb ane labelled wi h a, p oducing he objec no2n+11 ha will send ou o he en i onmen he
objec no.
4.1. An o e iew o he compu a ion
Fi s o all, gi en a o mula in CNF, ϕ=C1∧ · · · ∧ Cmsuch ha Va (ϕ) = {x1, . . . , xn}, we de ine s(ϕ) = hn,mi
and cod(ϕ) = {xi,j:xj∈Ci} ∪ {xi,j: ¬xi,j∈Ci}. Then (cod,s)is a pai o polynomial- ime compu able
unc ions o e ISAT such ha s(ϕ) is a na u al numbe and cod(ϕ) is an inpu mul ise o e Π(s(u)). Nex , we desc ibe
in o mally how he P sys em wi h Π(s(ϕ)) and wi h inpu cod(ϕ) wo ks.
In he ini ial con igu a ion, we ha e, on he one hand, he inpu mul ise cod(ϕ) and he objec s z0, and z0, placed
in he skin (memb ane labelled wi h ); and on he o he hand, we ha e in he memb ane labelled wi h a he objec
no0. This objec e ol es du ing he compu a ion ollowing he i s ule in he se 9.
In he i s s ep o he compu a ion, he objec z0, c ea es a new memb ane wi h label , which ep esen s he
assignmen x1= ue and he objec z0, c ea es a new memb ane wi h label , which ep esen s he assignmen
x1= alse. In hese wo new memb anes, he objec s z1and k0a e placed. A he same ime, he inpu mul ise
ep esen ing he o mula is duplica ed ollowing he wo i s ules in 2. In he nex s ep, acco ding o he ules in
3, he o mula is e alua ed on he wo possible assignmen s o x1. In he same s ep, he ules in 4 dec ease he
second subsc ip o he objec s ep esen ing he o mula (xi,j,l,xi,j,lwi h j≥2) in o de o analyse he nex a iable.
Mo eo e , a he same ime, he objec z1p oduces he objec z1, and z1, and he sys em is eady o analyse he
nex a iable. And so he gene a ion and e alua ion s ages go un il all he possible assignmen s o he a iables a e
gene a ed, and he o mula is e alua ed on each one o hem. Obse e ha i akes wo s eps o gene a e he possible
assignmen s o a a iable and o e alua e he o mula on hem; he e o e he gene a ion and e alua ion s ages ake 2n

s eps. No e ha he objec k0in he ules in 5 is a coun e ha dissol es he memb ane when he objec k2appea s;
ha is, i dissol es he memb ane once he memb ane is no use ul any longe in he es o he compu a ion.
The checking s age s a s when he objec znp oduces he objec s d1, . . . , dmand he objec q. In he i s s ep o he
checking s age, each objec di, o i=1, . . . , mc ea es a new memb ane labelled wi h i, whe e he objec 0is placed,
and he objec qc ea es a new memb ane wi h label a, placing he objec yes0in i . The objec s i, which signi y ha
he clause numbe ie alua es o ue on he assignmen associa ed wi h he memb ane, a e sen in o he memb anes
by he las ule in 4, so he sys em keeps ack o he clauses ha a e ue. The objec s i, ge in o he memb ane
wi h label i, and dissol e i in he ollowing wo s eps, p e en ing he coun e 2 om dissol ing he memb ane and
p oducing he objec 3acco ding o he las ule in 7. I , o some i, he e is no objec i, which means ha he clause
idoes no e alua e o ue on he associa ed assignmen , hen he objec 2will dissol e he memb ane labelled wi h i,
hus p oducing he objec 3 ha will ge in o he memb ane wi h label awhe e he objec yeshe ol es ollowing he
ules in 8. The objec 3dissol es he memb ane, p e en ing he p oduc ion o he objec yes6. The e o e he checking
s age akes 6 s eps.
Finally he ou pu s age akes place acco ding o he ules in 9. On he one hand, i some objec yes6is p esen in any
memb ane (which ep esen s ha he o mula e alua es o ue on he assignmen associa ed wi h his memb ane) i is
sen ou o he skin being ans o med in o he objec yes7. In he nex s ep, yes7ge s in o he memb ane labelled wi h
a, being ans o med in o yes8; hen i dissol es he memb ane, p oducing he objec yes9. This dissolu ion p e en s
he objec no2n+11 om being p oduced. And inally he objec yes is sen ou o he en i onmen . On he o he hand,
i he e is no objec yes6, hen he memb ane wi h label ais no dissol ed, and hus he objec no2n+11 is p oduced,
and he objec no is sen ou o he en i onmen . Obse e ha he ou pu s age akes 5 s eps i he answe is yes, and 6
s eps i he answe is no.
5. Some o mal de ails
In he p e ious sec ion, we ha e p esen ed a amily Πo ecognise P sys ems which sol e he SAT p oblem. Fo
each Boolean o mula, a P sys em Π(hn,mi)is cons uc ed, whe e nis he numbe o a iables and mis he numbe o
clauses. Fi s o all, obse e ha he e olu ion ules o Π(s(ϕ)) a e de ined in a ecu si e manne om ϕ, in pa icula
om nand m. Le us lis he necessa y esou ces o cons uc Π(s(ϕ)):
•Size o he alphabe : 6nm +5n+4m+32 ∈Θ(nm)
•Ini ial numbe o memb anes: 2 ∈Θ(1)
•Ini ial numbe o objec s: 3 ∈Θ(1)
•Sum o he leng hs o he ules: 86nm +84n+144m+121 ∈Θ(nm).
The e o e a Tu ing machine wo king in polynomial ime can build Π(s(ϕ)) om he o mula ϕ.
Finally, we can p o e, using a o mal desc ip ion o he compu a ion, ha he P sys em Π(s(ϕ)) wi h inpu cod(ϕ)
always hal s and sends o he en i onmen he objec yes o no in he las s ep. The numbe o s eps o such a P sys em
is 2n+11 i he ou pu is yes and 2n+12 i he ou pu is no; he e o e he e exis s a linea bound o he numbe o
s eps o he compu a ion.
Hence, he amily Πo ecognise P sys ems wi h memb ane c ea ion using dissolu ion ules sol es he SAT
p oblem in polynomial (ac ually, linea ) ime acco ding o De ini ion 3. So, we ha e he ollowing esul :
Theo em 4. SAT ∈PMCMC .
Co olla y 5. NP ∪co-NP ⊆PMCMC .
P oo . I su ices o ema k ha he SAT p oblem is NP-comple e, SAT ∈PMCMC , and ha his complexi y class is
closed unde polynomial ime educ ion and unde complemen . 
Rema k 6. No e ha in he amily o ecognise P sys ems gi en in Sec ion 4, memb ane c ea ion ules a e used
o p oduce an exponen ial wo kspace whe e all possible assignmen s o he a iables o he o mula a e gene a ed,
whe eas he p ocess o checking whe he o no he o mula e alua es o ue on any o hem is done using dissolu ion
ules.
I we deno e by MC+d( espec i ely, MC−d) he class o ecognise P sys ems wi h memb ane c ea ion and wi h
dissolu ion ules ( espec i ely, wi hou dissolu ion ules), hen we ha e jus p o ed ha NP ∪co-NP ⊆PMCMC+d.
In [3], he au ho s showed ha he gene a ion in polynomial ime o an exponen ial wo kspace (numbe o
memb anes) using memb ane c ea ion ules, is no enough o sol e NP-comple e p oblems in polynomial ime (unless
P=NP). Mo e p ecisely, he au ho s p o ed ha P=PMCMC−d.
Summing up, in he amewo k o ecognise P sys ems wi h memb ane c ea ion, we ha e p o ed he ollowing:
(a) he class o p oblems which can be sol ed in a polynomial ime by a amily o such P sys ems wi hou dissolu ion
is equal o class P; and (b) he class o p oblems which can be sol ed in a polynomial ime by a amily o such P
sys ems wi h dissolu ion con ains he class NP ∪co-NP.
6. Conclusions
Memb ane compu ing is a new c oss-disciplina y ield o na u al compu ing, which has eached an impo an
success in i s sho li e.
This pape deals wi h he s udy o e icien solu ions o well-known compu a ionally ha d p oblems, and in his
sense i is placed be ween he heo e ical esul s mainly ela ed o compu a ional comple eness and compu a ional
e iciency, and he eal implemen a ion o he de ices. I exploi s memb ane c ea ion (a poo ly s udied a ian ) o
sol e NP-comple e p oblems, gi ing he i s uni o m solu ion o SAT in polynomial ime ( ecen ly, we ha e p o ed
ha his a ian is PSPACE powe ul [4]).
We s ess he ele an ole played by he ules o dissolu ion in he amewo k o ecognise P sys ems using
memb ane c ea ion, in o de o “sepa a e” hei ac abili y om he (p esumable) in ac abili y o decision p oblems,
pu ing a ba ie be ween he complexi y classes Pand NP (assuming P6= NP).
This pape can be conside ed as a con ibu ion o he in e es ing p oblem o cha ac e ising he ac abili y o ha d
decision p oblems in e ms o he desc ip ional esou ces equi ed in memb ane sys ems.
Acknowledgemen s
This wo k is suppo ed by Minis e io de Ciencia y Tecnolog´
ıa o Spain, by Plan Nacional de I+D+I (2000–
2003) (TIC2002-04220-C03-01), co inanced by FEDER unds, and by a FPI ellowship (o he hi d au ho ) om he
Uni e si y o Se ille.
Re e ences
[1] M.A. Gu i´
e ez-Na anjo, M.J. P´
e ez-Jim´
enez, A. Riscos-N´
u˜
nez, Towa ds a p og amming language in cellula compu ing, Elec onic No es in
Theo e ical Compu e Science 123 (2005) 93–110.
[2] M.A. Gu i´
e ez-Na anjo, M.J. P´
e ez-Jim´
enez, A. Riscos-N´
u˜
nez, A as P sys em o inding a balanced 2-pa i ion, So Compu ing 9 (9)
(2005) 673–678.
[3] M.A. Gu i´
e ez-Na anjo, M.J. P´
e ez-Jim´
enez, A. Riscos-N´
u˜
nez, F.J. Rome o-Campe o, Cha ac e izing ac abili y wi h memb ane c ea ion,
in: 7 h In e na ional Symposium on Symbolic and Nume ic Algo i hms o Scien i ic Compu ing, SYNASC 2005. Wo kshop on Theo y and
Applica ions o P Sys ems, Timisoa a, Romania, 2005, IEEE Compu e Socie y, 2005, pp. 448–457.
[4] M.A. Gu i´
e ez-Na anjo, M.J. P´
e ez-Jim´
enez, F.J. Rome o-Campe o, A linea ime solu ion o QSAT wi h memb ane c ea ion, in: R. F eund,
G. Lojka, M. Oswald, Gh. Paun (Eds.), P e-P oceedings o he Six h In e na ional Wo kshop on Memb ane Compu ing, WMC6, Vienna
Uni e si y o Technology, Vienna, Aus ia, 2005, pp. 395–409.
[5] P.L. Luisi, The chemical implemen a ion o au opoiesis, in: G.R. Fleishake , S. Colonna, P.L. Luisi (Eds.), Sel -P oduc ion o Sup amolecula
S uc u es, Kluwe , Do d ech , 1994.
[6] Gh. P˘
aun, Memb ane Compu ing. An In oduc ion, Sp inge -Ve lag, Be l´
ın, 2002.
[7] M.J. P´
e ez-Jim´
enez, A. Riscos-N´
u˜
nez, Sol ing he Subse -Sum p oblem by ac i e memb anes, New Gene a ion Compu ing 23 (4) (2005)
367–384.
[8] M.J. P´
e ez-Jim´
enez, A. Riscos-N´
u˜
nez, A linea solu ion o he Knapsack p oblem using ac i e memb anes, Lec u e No es in Compu e
Science 2933 (2004) 250–268.
[9] M.J. P´
e ez-Jim´
enez, F.J. Rome o-Campe o, Sol ing he BIN PACKING p oblem by ecognize P sys ems wi h ac i e memb anes,
in: Gh. P˘
aun, A. Riscos, A. Rome o, F. Sancho (Eds.), P oceedings o he Second B ains o ming Week on Memb ane Compu ing, Repo
RGNC 01/04, Uni e si y o Se ille, Se ille, Spain, 2004, pp. 414–430.
[10] M.J. P´
e ez-Jim´
enez, A. Rome o-Jim´
enez, F. Sancho-Capa ini, A polynomial complexi y class in P sys ems using memb ane di ision,
in: E. Csuhaj-Va j´
u, C. Kin ala, D. Wo schke, Gy. Vaszyl (Eds.), P oceedings o he 5 h Wo kshop on Desc ip ional Complexi y o Fo mal
Sys ems, DCFS 2003, 2003, pp. 284–294.
[11] A. P˘
aun, Gh. P˘
aun, The powe o communica ion: P sys ems wi h sympo /an ipo , New Gene a ion Compu ing 20 (3) (2002) 295–305.
[12] Gh. P˘
aun, Compu ing wi h memb anes, Jou nal o Compu e and Sys em Sciences 61 (1) (2000) 108–143.
[13] Gh. P˘
aun, Fu he open p oblems in memb ane compu ing, in: Gh. P˘
aun, A. Riscos, A. Rome o, F. Sancho (Eds.), P oceedings o he Second
B ains o ming Week on Memb ane Compu ing, Repo RGNC 01/04, Uni e si y o Se ille, Se ille, Spain, 2004, pp. 354–365.
[14] ISI web page. h p://esi- opics.com/e /oc obe 2003.h ml.
[15] P sys ems web page. h p://psys ems.disco.unimib.i /.