On he E iciency o Cell-Like and Tissue-Like
Recognizing Memb ane Sys ems
Miguel A. Gu i´e ez-Na anjo, Ma io J. P´e ez-Jim´enez,
Agus ´ın Riscos-N´u˜nez, 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, ETS Ingenie ´ıa In o m´a ica, Uni e si y o Se illa, A da. Reina
Me cedes s/n, Se illa, Spain
Cell-like ecognizing memb ane sys ems a e compu a ional de ices in he amewo k o memb ane
compu ing inspi ed om he s uc u e o li ing cells, whe e biological memb anes a e a anged
hie a chically. In his pape issue-like ecognizing memb ane sys ems a e p esen ed. The idea is o
conside ha memb anes a e placed in he nodes o a g aph, mimicking he cell in e communica ion in
issues.
In his con ex , polynomial complexi y classes associa ed wi h ecognizing memb ane sys ems can be
de ined. We ecall he de ini ion o cell-like sys ems, and we in oduce he co esponding complexi y
classes o he issue-like case. Mo eo e , in his pape wo e icien solu ions o he sa is iabili y
p oblem a e analyzed and compa ed om a complexi y poin o iew.
1. INTRODUCTION
Memb ane compu ing is a young b anch o na u al compu ing p o iding dis-
ibu ed pa allel compu a ional de ices called memb ane sys ems, which a e inspi ed
om some basic biological ea u es o li ing cells, as well as om he coope a ion o
cells in issues, o gans, and o ganisms.
In his a ea, he e a e basically wo ways o conside compu a ional de ices: cell-
like memb ane sys ems and issue-like memb ane sys ems. The i s one uses
memb anes a anged hie a chically, inspi ed om he s uc u e o he cell, and he
second one uses memb anes placed in he nodes o a g aph, inspi ed om he cell
in e communica ion in issues.
In he pas yea s, se e al compu ing models using powe ul ools om na u e
ha e been de eloped (because o his, hey a e known as bioinspi ed models) and
se e al solu ions in polynomial ime o NP-comple e p oblems ha e been p esen ed,
making use o nonde e minism and/o o an exponen ial amoun o space. This is he
eason why a p ac ical implemen a ion o such models (in biological, elec onic, o
o he media) could p o ide a signi ican ad ance in he esolu ion o compu a ionally
ha d p oblems.
In his pape , we p esen ecognizing memb ane sys ems (bo h cell-like and
issue-like a ian s) as a amewo k o add ess ways o e icien ly sol e compu a ion-
ally ha d p oblems, cap u ing he ue concep o algo i hm ins ead o p o iding a
(classical) nonde e minis ic solu ion. Also, we p esen a solu ion o he sa is iabili y
p oblem in bo h a ian s.
The pape is s uc u ed as ollows. Fi s , in Sec ion 2, cell-like ecognizing
memb ane sys ems a e de ined, oge he wi h he complexi y classes associa ed
wi h hem. In his con ex , Sec ion 3 discusses he P e sus NP p oblem, and
Sec ion 4 shows how memb ane di ision ules in he ac i e memb anes model allow
o polynomial- ime solu ions o NP-comple e p oblems. We conclude he cell-like
app oach by sol ing he sa is iabili y p oblem in a linea ime, using pola iza ion-
less ac i e memb anes. Then, in Sec ion 5 we in oduce pola iza ionless issue-like
ecognizing memb ane sys ems wi h ac i e memb anes (adap ing he gene al de i-
ni ion o ecognizing sys ems), and we also in oduce he co esponding complexi y
classes (analogously as o he cell-like case). We also p esen a quad a ic solu ion
o he sa is iabili y p oblem in his amewo k. Finally, conclusions a e p esen ed in
he las sec ion.
2. CELL-LIKE RECOGNIZING MEMBRANE SYSTEMS
In he s uc u e and unc ioning o a cell, biological memb anes play an essen ial
ole. The cell is sepa a ed om i s en i onmen by means o a skin memb ane, and
i is in e nally compa men alized by means o in e nal memb anes.
The main syn ac ic componen s o a cell-like memb ane sys em (also called P
sys em, see Re . 1 o de ails) a e a memb ane s uc u e,mul ise s, and e olu ion
ules.Amemb ane s uc u e consis s o se e al memb anes a anged in a hie -
a chical s uc u e inside a main memb ane ( he skin), and delimi ing egions ( he
space in-be ween a memb ane and he immedia ely inne memb anes, i any). Each
memb ane iden i ies a egion inside he sys em. A memb ane s uc u e can be con-
side ed as a oo ed ee. Regions de ined by a memb ane s uc u e con ain objec s
co esponding o chemical subs ances p esen in he compa men s o a cell. The
objec s can be desc ibed by symbols o by s ings o symbols, in such a way ha
mul ise o objec s a e placed in egions o he memb ane s uc u e. The objec s can
e ol e acco ding o gi en e olu ion ules, associa ed wi h he egions (hence, wi h
he memb anes).
The seman ics o he cell-like memb ane sys ems is de ined h ough a
nonde e minis ic and synch onous model (in he sense ha a global clock is as-
sumed) as ollows: A con igu a ion o a cell-like memb ane sys em consis s o a
memb ane s uc u e and a amily o mul ise s o objec s associa ed wi h each egion
o he s uc u e. A he beginning, he e is a con igu a ion called he ini ial con ig-
u a ion o he sys em. In each ime uni , we can ans o m a gi en con igu a ion in
ano he con igu a ion by applying he e olu ion ules o he objec s placed inside he
egions o he con igu a ions, in a nonde e minis ic and maximally pa allel manne
( he ules a e chosen in a nonde e minis ic way, and in each egion all objec s ha
can e ol e mus do i ). In his way, we ge ansi ions om one con igu a ion o
he sys em o he nex one. A compu a ion o he sys em is a ( ini e o in ini e)
sequence o con igu a ions such ha each one is ob ained om he p e ious one by
a ansi ion, and shows how he sys em is e ol ing. A compu a ion ha eaches a
con igu a ion whe e no mo e ules can be applied o he exis ing objec s is called a
hal ing compu a ion. The esul o a hal ing compu a ion is usually de ined h ough
he mul ise associa ed wi h a speci ic ou pu memb ane (o he en i onmen ) in he
inal con igu a ion.
In he basic de ini ion, cell-like memb ane sys ems can be seen as gene a i e
de ices, wo king in a nonde e minis ic and maximally pa allel manne , wi h ou pu
memb ane, and wi hou inpu memb ane. Howe e , as we a e in e es ed in using cell-
like memb ane sys ems o sol ing decision p oblems, we can adap he de ini ion
as ollows:
DEFINITION 2.1. A cell-like memb ane sys em wi h ex e nal ou pu is said o be a
ecognizing sys em i : (a) The wo king alphabe con ains wo dis inguished elemen s
yes and no; (b) all compu a ions hal , and i Cis a compu a ion o he sys em, 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 in he las s ep o he compu a ion.
A compu a ion o a ecognizing sys em is said o be 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 en i onmen associa ed wi h he co esponding hal ing con igu a ion.
We wan hese kinds o sys ems (which a e nonde e minis ic de ices) o p op-
e ly sol ed decision p oblems acco ding o he ue algo i hmic concep . Wi h his
aim, ins ead o using classical nonde e minis ic accep ance (i is enough ha one
compu a ion gi es an a i ma i e answe ), i is necessa y o equi e a condi ion o
con luence; ha is, he sys em p ocessing an ins ance o he p oblem mus always
gi e he same answe in all compu a ions. This idea leads us o he concep s o
soundness and comple eness.
2.1. Soundness and Comple eness
A amily o cell-like ecognizing P sys ems will p o ide a solu ion o a deci-
sion p oblem i o each ins ance o he p oblem: (a) i he e exis s an accep ing
compu a ion o he memb ane sys em p ocessing i , hen he ins ance o he p oblem
has an a i ma i e answe (soundness); and (b) i he ins ance o he p oblem has an
a i ma i e answe , hen any compu a ion o he sys em p ocessing ha ins ance is
an accep ing compu a ion (comple eness).
Nex , we o malize hese ideas in he ollowing de ini ion:
DEFINITION 2.2. Le X=(IX,θ
X)be a decision p oblem. Le =((w))w∈IXbe
a amily o ecognizing memb ane sys ems wi hou inpu .
•The amily is sound wi h ega d o Xi o each ins ance w∈IXsuch ha he e exis s
an accep ing compu a ion o (w), we ha e θX(w)=1.
•The amily is comple e wi h ega d o Xi o each ins ance w∈IXsuch ha θX(w)=1,
we ha e e e y compu a ion o (w)is an accep ing compu a ion.
These concep s can be ex ended o amilies o cell-like ecognizing memb anes
wi h inpu memb ane in a na u al way, bu in his case a P sys em belonging o he
amily can p ocess se e al ins ances o he p oblem, p o ided ha an app op ia e
inpu is supplied o he sys em.
DEFINITION 2.3. 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 labeled by 1,...,p, and ini ial
mul ise s M1,...,Mpassocia ed wi h hem; (b) is an (inpu ) alphabe s ic ly
con ained in , and he ini ial mul ise s a e o e −; and (c) iis he label o a
dis inguished (inpu ) memb ane.
I mis a mul ise o e , hen he ini ial con igu a ion o (, , i)wi h inpu
mis (μ, M1,...,Mi∪m,...,Mp).
DEFINITION 2.4. Le X=(IX,θ
X)be a decision p oblem. Le =((n))n∈Nbe a
amily o cell-like ecognizing P sys ems wi h inpu .Apolynomial encoding o Xin
is a pai (cod, s)o polynomial ime compu able unc ions o e IXsuch ha o
each ins ance w∈IX,s(w)is a na u al numbe and cod(w)is an inpu mul ise o
he sys em (s(w)).
DEFINITION 2.5. Le X=(IX,θ
X)be a decision p oblem. Le =((n))n∈Nbe
a amily o cell-like ecognizing memb ane sys ems wi h inpu .Le (cod, s)be a
polynomial encoding o Xin .
•The amily is sound wi h ega d o (X, cod, s)i o each ins ance w∈IXsuch ha
he e exis s an accep ing compu a ion o (s(w)) wi h inpu cod(w), we ha e θX(w)=1.
•The amily is comple e wi h ega d o (X, cod, s)i o each ins ance w∈IXsuch ha
θX(w)=1, we ha e e e y compu a ion o (s(w)) wi h inpu cod(w)is an accep ing
compu a ion.
Nex , we conside di e en complexi y classes in he amewo k o cell-like
ecognizing memb ane sys ems.
2.2. Polynomial Semiuni o m Solu ions
The i s esul s abou sol abili y o NP-comple e p oblems in polynomial ime
by memb ane sys ems we e gi en by P˘
aun,2Zand on e al.,3K ishna and Rama,4and
Ob ulowicz,5in he amewo k o memb ane sys ems ha lack an inpu memb ane.
Thus, he cons uc i e p oo s o such esul s design one sys em o each ins ance o
he p oblem.
In his con ex , le us de ine polynomial complexi y classes in cell-like ec-
ognizing P sys ems wi hou inpu . To sol e a decision p oblem we need, hen, o
associa e wi h each ins ance o he p oblem a sys em which decides he ins ance.
DEFINITION 2.6. Le Rbe a class o cell-like ecognizing P sys ems wi hou inpu
memb ane. A decision p oblem X=(IX,θ
X)is sol able in polynomial ime by a
amily =((w))w∈IX, o P sys ems o R, and we deno e i by X∈PMC∗
R, 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 wo king in polynomial ime which cons uc s he sys em (w)
om he ins ance w∈IX.
•The amily is polynomially bounded; ha is, he e exis s a polynomial unc ion p(n)
such ha o each w∈IX, e e y compu a ion o (w)hal in, a mos , p(|w|)s eps.
•The amily is sound and comple e wi h ega d o X.
We say ha he amily is a semiuni o m solu ion o he p oblem X.
As a di ec consequence o wo king wi h ecognizing memb ane sys ems we
ha e hese complexi y classes a e closed unde complemen . Mo eo e , hey a e
closed unde polynomial ime educ ion.
2.3. Polynomial Uni o m Solu ions
Nex , we deal wi h cell-like ecognizing P sys ems wi h inpu memb ane and we
p opose o sol e p oblems in an uni o m way in he ollowing sense: All ins ances o
a decision p oblem ha ha e he same size (acco ding o a p e ixed polynomial ime
compu able c i e ion) a e p ocessed by he same sys em, on which an app op ia e
inpu is supplied.
Le us o malize hese ideas in he ollowing de ini ion:
DEFINITION 2.7. A decision p oblem X=(IX,θ
X)is sol able in polynomial ime
by a amily o cell-like ecognizing P sys ems wi h inpu =((n))n∈N, and we
deno e i by X∈PMCR, 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 ha cons uc s in polynomial ime he sys em (n) om n∈N.
•The e exis s a polynomial encoding (cod, s)o Xin such ha
–The amily is polynomially bounded wi h ega d o (X, cod, s); ha is, he e
exis s a polynomial unc ion p(n)such ha o each w∈IX, e e y compu a ion
o he sys em (s(w)) wi h inpu cod(w)is hal ing and, mo eo e , i pe o ms a
mos p(|w|)s eps.
–The amily is sound and comple e wi h ega d (X, cod, s).
These complexi y classes a e closed unde complemen . Mo eo e , hey a e closed
unde polynomial ime educ ion.

3. P VERSUS NP PROBLEM IN THE CONTEXT OF CELL-LIKE
RECOGNIZING MEMBRANE SYSTEMS
We conside de e minis ic Tu ing machines as language ecognizing de ices.
Then, we can associa e wi h each de e minis ic Tu ing machine a decision p oblem,
which will allow us o de ine when such a machine is simula ed by a amily o P
sys ems ( his issue was also add essed, e.g., in Re s. 6 and 7).
DEFINITION 3.1. Le Mbe a Tu ing machine wi h inpu alphabe M.Thedecision
p oblem associa ed wi h Mis he p oblem XM=(I,θ), whe e I=∗
M, and o
e e y w∈∗
M,θ(w)=1i and only i Maccep s w.
Ob iously, he decision p oblem XMis sol able by he Tu ing machine M.
DEFINITION 3.2. We say ha a Tu ing machine, M, is simula ed in polynomial ime
by a amily o cell-like ecognizing P sys ems o he class R,i XM∈PMCR.
In cell-like memb ane sys ems, e olu ion ules, communica ion ules, and ules
in ol ing dissolu ion a e called basic ules. No e ha by applying his kind o ules
he size o he memb ane s uc u e does no inc ease. Hence, i is no possible o
cons uc an exponen ial numbe o memb anes in polynomial ime using only basic
ules in a cell-like memb ane sys em.
We ecall he e a esul om Chap e 9 o Re . 8.
PROPOSITION 3.1. Le Mbe a de e minis ic Tu ing machine wo king in polynomial
ime. Then Mcan be simula ed in polynomial ime by a amily o cell-like ecognizing
P sys ems using only basic ules.
Recip ocally, in Re . 7 he ollowing esul was p o ed:
PROPOSITION 3.2. Fo e e y decision p oblem sol able in polynomial ime by a
amily o cell-like ecognizing P sys ems using only basic ules, he e exis s a Tu ing
machine sol ing i in polynomial ime.
Unde he hypo hesis P= NP, Zand on e al.3es ablished he limi a ions o
cell-like memb ane sys ems, which use only basic ules conce ning he e icien
solu ion o NP-comple e p oblems. This esul was gene alized by P´
e ez-Jim´
enez
e al.7ob aining he ollowing wo cha ac e iza ions o he P= NP ela ion by
means o unsol abili y esul s in polynomial ime o NP-comple e p oblems by
amilies o cell-like ecognizing memb ane sys ems using only basic ules.
THEOREM 3.1. The ollowing asse ions a e equi alen :
1. P= NP.
2. The e exis s an NP-comple e decision p oblem unsol able in polynomial ime by a amily
cell-like ecognizing memb ane sys ems using only basic ules.
3. Each NP-comple e decision p oblem is unsol able in polynomial ime by a amily o
cell-like ecognizing memb ane sys ems using only basic ules.
Le us deno e by RB he class o cell-like ecognizing memb ane sys ems
using only basic ules. In Re . 9 he complexi y class Phas been cha ac e ized in
e ms o cell-like ecognizing P sys ems, by p o ing he ollowing heo em.
THEOREM 3.2. P=PMCRB.
4. RECOGNIZING CELL-LIKE P SYSTEMS WITH
ACTIVE MEMBRANES
A pa icula ly in e es ing class o cell-like memb ane sys ems is he sys ems
wi h ac i e memb anes, whe e he memb ane di ision can be used o sol e compu-
a ionally ha d p oblems, e.g., NP-comple e p oblems, in polynomial o e en linea
ime, by a space- ime ade-o .
DEFINITION 4.1. A ecognizing cell-like P sys em (, , i)is called wi h ac i e
memb anes, i he ules o a e o he ollowing o ms (being he wo king
alphabe , and H he se o labels o ):
(a) [ a→ω]α
h o h∈H,α∈{+,−,0},a∈,ω∈∗: An objec awi hin a memb ane
labeled wi h hand pola i y αe ol es o a mul ise ω.
(b) a[]
α1
h→[b]α2
h o h∈H,α1,α
2∈{+,−,0},a,b ∈: An objec om he egion
immedia ely ou side a memb ane labeled wi h his in oduced in his memb ane, possibly
ans o med in o ano he objec , and simul aneously, he pola i y o he memb ane can
be changed.
(c) [ a]α1
h→b[]
α2
h o h∈H,α1,α
2∈{+,−,0},a,b ∈: An objec is sen ou om
memb ane labeled wi h h o he egion immedia ely ou side, possibly ans o med in o
ano he objec , and simul aneously, he pola i y o he memb ane can be changed.
(d) [ a]α
h→b o h∈H,α∈{+,−,0},a,b ∈: A memb ane labeled wi h his dissol ed
in eac ion wi h an objec . The skin is ne e dissol ed.
(e) [ a]α1
h→[b]α2
h[c]α3
h o h∈H,α1,α
2,α
3∈{+,−,0},a,b,c ∈: A memb ane can
be di ided in o wo memb anes wi h he same label, possibly ans o ming some objec s
and hei pola i ies.
These ules a e applied acco ding o he ollowing p inciples:
•All he ules a e applied in pa allel and in a maximal manne . In one s ep, one objec o
a memb ane can be used by only one ule (chosen in a nonde e minis ic way), bu any
objec which can e ol e by one ule o any o m, mus e ol e.
•I a memb ane is dissol ed, i s con en (mul ise and in e nal memb anes) is le ee in
he su ounding egion.
•I a he same ime a memb ane labeled by his di ided by a ule o ype (e) and he e a e
objec s in his memb ane which e ol e by means o ules o ype (a), hen we suppose
ha i s he e olu ion ules o ype (a) a e used, and hen he di ision is p oduced. O
cou se, his p ocess akes only one s ep.
•The ules associa ed wi h memb anes labeled by ha e used o all copies o his memb ane.
A one s ep, a memb ane can be he subjec o only one ule o ypes (b)–(e).
Le us deno e by AM he class o ecognizing P sys ems wi h ac i e memb anes
using 2-di ision. Di e en polynomial ime solu ions o NP-comple e p oblems
ha e been ob ained using his class o cell-like ecognizing memb ane sys ems:
Knapsack,10 SAT,11 Clique,12 and Bin Packing.13 Hence, he ollowing p oposi ion
holds:
PROPOSITION 4.1. NP ⊆PMCAM, and co-NP ⊆PMCAM.
Mo eo e , Sos´
ık14 p o ed ha PSPACE ⊆PMC∗
AM0(+d,+ne), whe e
AM0(+d,+ne) is he class o ecognizing P sys ems wi h ac i e memb anes al-
lowing di ision o nonelemen a y memb anes.
The e o e, he complexi y class PMCAM does no seem p ecise enough o
desc ibe classical complexi y classes below NP. Consequen ly, i is challenging
o in es iga e weake models o cell-like memb ane sys ems able o cha ac e ize
classical complexi y classes.
Following his line, se e al e icien solu ions o NP-comple e p oblems ha e
been ob ained wi hin he ollowing a ian s o cell-like P sys ems wi h ac i e
memb anes:
•P sys ems wi h ac i e memb anes bu using only wo elec ical cha ges (Alhazo ,15
Riscos16;
•P sys ems wi h ac i e memb anes wi hou pola iza ions, bu using bis able ca alys s (P´
e ez
and Rome o17);
•P sys ems wi hou pola iza ions, wi hou coope a ion, wi hou p io i ies, wi hou label
changing, wi hou di ision, bu using h ee ypes o memb ane ules: sepa a ion, me ging,
and elease (Pan e al.18);
•P sys ems wi h sepa a ion ules ins ead o di ision ules, in wo di e en cases: in he
i s , using pola iza ions and sepa a ion ules; and in he second one, wi hou pola iza ions
bu using sepa a ion ules ha can change memb ane labels (Pan and
Ishdo j19).
We can de ine pola iza ionless cell-like P sys ems wi h ac i e memb anes in a
simila manne by emo ing elec ical cha ges, ha is, conside ing only ules o he
ollowing ypes:
(a) [ a→u]h o h∈H,a∈,u∈∗.
(b) a[]
h→[b]h o h∈H,a,b ∈.
(c) [ a]h→b[]
h o h∈H,a,b ∈.
(d) [ a]h→b o h∈H,a, b ∈.
(e) [ a]h→[b]h[c]h o h∈H,a, b,c ∈.
We deno e by AM0 he class o pola iza ionless cell-like ecognizing P sys ems
wi h ac i e memb anes.
A he beginning o 2005, P˘
aun (p oblem F om Re . 20) w o e: “My a o i e
ques ion ( ela ed o complexi y aspec s in P sys ems wi h ac i e memb anes and wi h
elec ical cha ges) is ha abou he numbe o pola iza ions. Can he pola iza ions
be comple ely a oided? The eeling is ha his is no possible—and such a esul
would be a he sound: passing om no pola iza ion o wo pola iza ions amoun s
o passing om non-e iciency o e iciency.”
Tha is, o mally we can o mula e he so-called P˘
aun’s conjec u e as ollows:
“The class o decision p oblems sol able in polynomial ime by amilies o cell-like
ecognizing P sys ems belonging o AM0is he s anda d complexi y class P.”
We deno e by AM0(α, β), whe e α∈{−d,+d}and β∈{−ne, +ne}, he
class o all pola iza ionless cell-like ecognizing P sys ems wi h ac i e memb anes
such ha (a) i α=+d( esp. α=−d) hen dissolu ion ules a e pe mi ed ( esp.
o bidden); and (b) i β=+ne ( esp. β=−ne) hen di ision ules o elemen-
a y and non-elemen a y ( esp. only di ision ules o elemen a y) memb anes a e
pe mi ed.
In he amewo k o pola iza ionless cell-like ecognizing P sys ems wi h ac i e
memb anes, i u ns ou ha dissolu ion ules play a su p ising ole, as hey make
he di e ence be ween e iciency and none iciency. Mo e p ecisely, he ollowing
esul is p esen ed in Re . 21:
THEOREM 4.1. We ha e he ollowing:
(1) P=PMCAM0(−d,β)=PMC∗
AM0(−d,β), o each β∈{−ne, +ne}.
(2) NP ∪co −NP ⊆PMC∗
AM0(+d,+ne).
Tha is, P˘
aun’s conjec u e has a nega i e answe i dissolu ion ules a e allowed
(assuming ha P= NP), and an a i ma i e answe o he wise.
The inclusion shown in (2) was imp o ed in Re . 22, whe e PSPACE ⊆
PMCAM0(+d,+ne)is p o ed.
The inclusion ela ions be ween complexi y classes can be summa ized g aph-
ically in Figu e 1.
4.1. Sol ing he SAT P oblem by Using Pola iza ionless Cell-Like
P Sys ems wi h Ac i e Memb anes
The i s e icien semiuni o m solu ion o SAT (sa is iabili y p oblem) was
gi en by P˘
aun,2using di ision o nonelemen a y memb anes. This esul was
imp o ed by P˘
aun e al. in Re . 23 using only di ision o elemen a y memb anes (in
ha pape a semiuni o m solu ion o he Hamil onian pa h p oblem using memb ane
c ea ion is also p esen ed).
In his sec ion, we p esen a semiuni o m solu ion o he SAT p oblem in
linea ime by using pola iza ionless cell-like ecognizing P sys ems wi h ac i e
memb anes.
THEOREM 4.2. The sa is iabili y o any p oposi ional o mula in he conjunc i e
no mal o m, using n a iables and mclauses, can be decided in a linea ime
wi h espec o nby a pola iza ionless cell-like ecognizing P sys em wi h ac i e
memb anes, cons uc ed in linea ime wi h espec o nand m.
5.1.1. An O e iew o he Compu a ions
Memb ane 2 is epea edly di ided, each ime expanding one objec ai, co e-
sponding o a a iable xi, in o Ti,1and Fi,1, co esponding o he alues ue and alse
which his a iable may assume. In his way, in ns eps, we ge 2ncells wi h label
2, each one con aining one o he 2npossible u h assignmen s o he n a iables.
The objec s , g a e duplica ed, hence a copy o each o hem will appea in each
cell.
In pa allel wi h he ope a ion o di iding cell 2, he coun e s bi,c
i,d
i,e
i om
cell 1 g ow hei subsc ip s. In each s ep, he numbe o copies o objec s o he i s
h ee ypes is doubled, hence a e ns eps we ge 2ncopies o bn+1,c
n+1, and dn+1.
Objec s biwill check which clauses a e sa is ied by a gi en u h assignmen , objec s
cia e used o mul iply he numbe o copies o i,
ias we will see immedia ely, di
a e used o check whe he he e is a leas one u h assignmen which sa is ies all
clauses, and i such an assignmen does no exis , hen eiwill be used in o de o
p oduce he objec no a he end o he compu a ion.
In s ep n+1, he coun e s bn+1,c
n+1,d
n+1a e b ough in cells wi h label 2,
in exchange o and g. Because we ha e 2ncopies o each objec o hese ypes
and 2ncells 2, each one con aining exac ly one copy o and one o g, due o he
maximal pa allel use o he ules, each cell 2 ge s p ecisely one copy o each o
bn+1,c
n+1,d
n+1. No e ha cells 2 canno di ide anymo e, because he objec s ai
we e exhaus ed.
In he p esence o cn+1, he objec s Ti,1,F
i,1ge p imed, which ini ia es he
possibili y o in oducing mcopies o each iand iin each cell 2. As we ha e m
clauses, hen o check hei alues o a gi en u h assignmen , we need o each
clause one se o objec s encoding he alues o all a iables. No e ha his phase
needs 2ns eps o p iming he objec s Ti,1,F
i,1— o each objec we need one s ep,
because we ha e only one copy o cn+1a ailable— hen m u he s eps o each
T
i,1,F
i,1; all hese s eps a e done in pa allel, bu o he las p imed Ti,1,F
i,1we
ha e o con inue ms eps a e he 2nnecessa y o p iming. Thus, he o al numbe
o s eps pe o med in his p ocess is 2n+m.
In pa allel wi h he p e ious ope a ions, he coun e s biand diinc ease hei
subsc ip s, un il eaching he alue 3n+m+1. This is done in all cells 2 a he
same ime. Simul aneously, eiinc eases i s subsc ip in cell 1.
In he p esence o b3n+m+1—and no be o e—we check he alues assumed
by clauses o he u h assignmen s om each cell 2. We ha e only one copy o
b3n+m+1in each cell, hence we need a mos nm s eps o his: each clause con ains
a mos nli e als, and we ha e mclauses. In pa allel, dinc eases he subsc ip , un il
eaching he alue 3n+nm +m+1.
In each cell wi h label 2 we check whe he o no all clauses a e sa is ied by
he co esponding u h assignmen . Fo each clause which is sa is ied, we inc ease
by one he subsc ip o d, hence he subsc ip eaches he alue 3n+nm +2m+1
i and only i all clauses a e sa is ied.
I one o he u h assignmen s om a cell 2 has sa is ied all clauses, hen
we each d3n+nm+2m+1, which is sen o cell 1 in exchange o he objec s yes
and .

In he nex s ep, he objec yes lea es he sys em, signaling he ac ha he
o mula is sa is iable. In cell 1, he coun e ewill inc ease one mo e s ep i s subsc ip ,
bu a e ha i will emain unchanged—i can lea e cell 1 only in he p esence o
, bu his objec was al eady mo ed o cell 2.
I he coun e e eaches he subsc ip 3n+nm +2m+2 and he objec is
s ill in cell 1, hen he objec no can be mo ed o a cell 2, andomly chosen, and
om he e i exi s he sys em, signaling ha he o mula is no sa is iable.
Nex , we jus i y ha he solu ion p o ided is an uni o m solu ion.
We conside he polynomial encoding (cod, s)o ISAT in , de ined as ollows:
I he o mula ϕis an ins ance o SAT wi h size pa ame e s n(numbe o a iables)
and m(numbe o clauses), hen s(ϕ)=n, mand cod(ϕ) is he se

1≤i≤n,1≤j≤m,1≤ ≤kj
{si,j |yj, =xi}∪{s
i,j |yj, =¬xi,}
Tha is, in he mul ise cod(ϕ) we eplace each a iable xi om each clause Cjwi h
si,j and each nega ed a iable ¬xi om each clause Cjwi h s
i,j , hen we emo e
all pa en heses and connec i es. In his way we pass om ϕ o cod(ϕ) in a numbe
o s eps which is linea wi h espec o n·m.
The p esen ed amily o issue-like ecognizing memb ane sys ems is polyno-
mially uni o m by Tu ing machines, because he de ini ion o he amily is done in
a ecu si e manne om a gi en ins ance o SAT, in pa icula om he cons an s n
(numbe o a iables) and m(numbe o clauses). Fu he mo e he issue P sys em
(n, m) uses an alphabe o 5nm +17n+4m+12 objec s, 2 ini ial cells con ain-
ing n+8 objec s in all, and n ules. The leng h o any ule is bounded by 3. Clea ly,
all compu a ions hal , and he numbe o s eps is bounded by 3n+nm +2m+4
(when he answe is nega i e; i he answe is a i ma i e, hen he numbe o s eps
is 3n+nm +2m+2).
F om he abo e we deduce he ollowing esul s:
THEOREM 5.2.
1. SAT ∈PMCTR
.
2. NP ⊆PMCTR
,andNP ∪co −NP ⊆PMCTR
.
Rema ks. We ha e p esen ed wo solu ions o he SAT p oblem by using pola iza-
ionless ecognizing memb ane sys ems wi h ac i e memb anes. The i s one, in
he cell-like amewo k is semiuni o m, does no use coope a ion (i.e., he le -hand
sides o he ules only ha e one objec ), and i is linea in ime and in ( he ini ial)
space. The second one, in he issue-like amewo k is a uni o m solu ion, uses coop-
e a ion, and i is quad a ic in ime and in ( he ini ial) space. Bo h solu ions cons uc
an exponen ial wo king space (in e ms o memb anes o cells) in linea ime.
6. CONCLUSIONS
In his pape , we ha e p esen ed cell-like (inspi ed om he s uc u e o he cell)
and issue-like (inspi ed om he cell in e -communica ion in issues) ecognizing
memb ane sys ems as compu a ional de ices specially sui able o a ack he e icien
sol abili y o compu a ionally ha d p oblems.
In ha new amewo k, wo cha ac e iza ions o he ela ion P=NP ha e been
desc ibed h ough he sol abili y o NP-comple e p oblems by a amily o cell-like
ecognizing memb ane sys ems using only basic ules.
The main con ibu ion o his pape is o o malize he concep o issue-
like memb ane sys ems, and o p esen , in he amewo k o issue-like ecognizing
memb ane sys ems, a o mal de ini ion o he polynomial complexi y class PMCTR
.
Besides, wo polynomial ime solu ions o he sa is iabili y p oblem by using po-
la iza ionless (cell-like and issue-like) ecognizing memb ane sys ems wi h ac i e
memb anes a e p esen ed.
Finally, we would like o men ion wo open ques ions o u u e esea ch.
Wha happens i in issue-like P sys ems di ision ules a e o bidden? Wha i
communica ion ules a e es ic ed o (i, a/b, j), whe e i, j a e labels and a,b a e
objec s (ins ead o mul ise s)?
Acknowledgmen s
The au ho s acknowledge he suppo o he p ojec TIN2005-09345-C04-01 o he Minis e-
io de Educaci´
on y Ciencia o Spain, co inanced by FEDER unds and o he p ojec o Excellence
TIC 581 o he Jun a de Andaluc´
ıa.
Re e ences
1. P˘
aun Gh. Memb ane compu ing. An in oduc ion. Be lin: Sp inge -Ve lag; 2002.
2. P˘
aun Gh. P sys ems wi h ac i e memb anes: a acking NP–comple e p oblems. J Au oma a,
Lang Comb 2001;6(1):75–90.
3. 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
memb anes. In: An oniou I, Calude CS, Dinneen MJ, edi o s. Uncon en ional models o
compu a ion, UMC’2K, Be lin: Sp inge -Ve lag; 2000. pp 289–301.
4. K ishna SN, Rama R. A a ian o P sys ems wi h ac i e memb anes: sol ing NP–comple e
p oblems. Romanian J In o m Sci Technol 1999;2(4):357–367.
5. Ob ulowicz A. De e minis ic P sys ems o sol ing SAT p oblem. Romanian J In o m Sci
Technol 2001;4(1–2):551–558.
6. P´
e ez–Jim´
enez MJ. An app oach o compu a ional complexi y in Memb ane Com-
pu ing. In: Mau i G, P˘
aun, Gh, P´
e ez–Jim´
enez MJ, Rozenbe g G , Salomaa A,
edi o s. Memb ane Compu ing, 5 h In e na ional Wo kshop, WMC5, Lec u e No es in Com-
pu e Science, Vol. 3365. Be lin: Sp inge ; 2005. pp 85–109.
7. P´
e ez–Jim´
enez MJ, Rome o–Jim´
enez A, Sancho–Capa ini F. The P e sus NP p oblem
h ough cellula compu ing wi h memb anes. In: Jonoska N., P˘
aun Gh, Rozenbe g G, edi o s.
Aspec s o molecula compu ing. Lec u e No es in Compu e Science, Vol 2950. Be lin:
Sp inge ; 2004. pp 338–352.
8. Rome o–Jim´
enez A. Complexi y and uni e sali y in cellula compu ing models. PhD.
Thesis, Uni e si y o Se ille, Spain, 2003.
9. Gu i´
e ez–Na anjo MA, P´
e ez–Jim´
enez MJ, Riscos–N´
u˜
nez A, Rome o–Campe o FJ,
Rome o–Jim´
enez A. Cha ac e izing ac abili y by cell-like memb ane sys ems. In: K.G.
Sub amanian, K. Ranga ajan, M. Mukund, edi o s. Fo mal models, languages and applica-
ions. MPAI Se ies, Vol 66. Singapo e: Wo ld Scien i ic; 2006. pp 137–154.
10. P´
e ez–Jim´
enez MJ, 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. In: Ma ´
ın-Vide C, P˘
aun Gh, Rozenbe g G, Salomaa A,
edi o s. Memb ane compu ing, Lec u e No es in Compu e Science, Vol 2933. Be lin:
Sp inge ; 2004. pp. 248–266.
11. P´
e ez–Jim´
enez MJ, Rome o–Jim´
enez A, Sancho–Capa ini F. Complexi y classes in cellula
compu ing wi h memb anes. Na Compu 2003;2(3):265–285.
12. Alhazo A, Ma ´
ın–Vide C, Pan L. Sol ing g aph p oblems by P sys ems wi h es ic ed
elemen a y ac i e memb anes. In: Jonoska N, P˘
aun Gh, Rozenbe g G, edi o s. Aspec s o
molecula compu ing, Lec u e No es in Compu e Science, Vol 2950. Be lin: Sp inge ; 2004.
pp 1–22.
13. P´
e ez–Jim´
enez MJ, Rome o–Campe o FJ. An e icien amily o P sys ems o packing
i ems in o bins. J Uni e sal Compu Sci 2004; 10(5):650–670.
14. Sosik P. The compu a ional powe o cell di ision in P sys ems: Bea ing down pa allel
compu e s? Na Compu 2003;2(3):287–298.
15. Alhazo A, Pan L, P˘
aun Gh. T ading pola iza ions o labels in P sys ems wi h ac i e
memb anes. Ac a In o m 2004;41(2–3):111–144.
16. Riscos–N´
u˜
nez A. Cellula p og amming: e icien esolu ion o NP–comple e nume ical
p oblems. Ph.D. Thesis, Uni e si y o Se ille, Spain; 2004.
17. P´
e ez–Jim´
enez MJ, Rome o–Campe o FJ. T ading pola iza ions o bi-s able ca alys s in P
sys ems wi h ac i e memb anes. In: Mau i G, P˘
aun Gh, P´
e ez–Jim´
enez MJ, Rozenbe g G ,
Salomaa A, edi o s. Memb ane Compu ing, 5 h In e na ional Wo kshop, WMC5, Lec u e
No es in Compu e Science, Vol. 3365. Be lin: Sp inge ; 2005. pp. 373–388.
18. Pan L, Alhazo A, Ishdo j T-O. Fu he ema ks on P sys ems wi h ac i e memb anes,
sepa a ion, me ging, and elease ules. So Comp—A Fusion Found Me hodol Appl
2005;9(9):686–690.
19. Pan L, Ishdo j T-O. P Sys ems wi h ac i e memb anes and sepa a ion ules. J Uni e sal
Compu Sci 2004;10(5):630–649.
20. P˘
aun Gh. Fu he wen y six open p oblems in memb ane compu ing. In: Gu i´
e ez-Na anjo
MA, Riscos-N´
u˜
nez A, Rome o-Campe o FJ, Sbu lan D, edi o s. P oceedings o he Thi d
B ains o ming Week on Memb ane Compu ing; 2005. pp 249–262.
21. Gu i´
e ez–Na anjo MA, P´
e ez–Jim´
enez MJ, Riscos–N´
u˜
nez A, Rome o–Campe o FJ. On he
powe o dissolu ion in P sys ems wi h ac i e memb anes. In: Lec u e No es in Compu e
Science. Be lin: Sp inge ; Vol. 3850. 2006; pp 224–240.
22. Alhazo A, P´
e ez-Jim´
enez MJ. Uni o m solu ion o QSAT using pola iza ionless ac i e
memb anes. In: Du and-Lose J and Ma gens e n M, edi o s. Machines, Compu a ions, and
Uni e sali y, Lec u e No es in Compu e Science, Vol. 4664. Be lin: Sp inge ; 2007. pp 122–
133.
23. P˘
aun Gh, Suzuki Y, Tanaka H, Yokomo i T. On he powe o memb ane di ision in P sys ems.
Theo Compu Sci 2004;324(1):61–85.