E ficien solu ions o ha d compu a ional p oblems by P sys ems
wi h sympo /an ipo ules and memb ane di ision
Bosheng Song a,b, Ma io J. Pé ez-Jiménez b, Linqiang Pan a
a Key Labo a o y o Image In o ma ion P ocessing and In elligen Con ol, School o Au oma ion, Huazhong Uni e si y o Science and Technology, Wuhan 430074, Hubei, China
b Resea ch G oup on Na u al Compu ing, Depa men o Compu e Science and A ificial In elligenc, Uni e si y o Se illa, A da. Reina Me cedes s/n, 41012 Se illa, Spain
Keywo ds:
Cell-like P sys em
Sympo /An ipo ule
Memb ane di ision
Subse Sum p oblem
QSAT p oblem
abs ac
P sys ems a e compu ing models inspi ed by some basic ea u es o biological memb anes. In his wo k,
memb ane di ision, which p o ides a way o ob ain an exponen ial wo kspace in linea ime, is
in oduced in o (cell-like) P sys ems wi h communica ion (sympo /an ipo ) ules, whe e objec s a e
ne e modified bu hey jus change hei places. The compu a ional e ficiency o his kind o P sys ems
is s udied. Specifically, we p esen a (uni o m) linea ime solu ion o he NP-comple e p oblem, Subse
Sum by using di ision ules o elemen a y memb anes and communica ion ules o leng h a mos 3. We
u he p o e ha such P sys em allowing di ision ules o non-elemen a y memb anes can e ficien ly
sol e he PSPACE-comple e p oblem, QSAT in a uni o m way.
1. In oduc ion
Memb ane compu ing is a flexible and e sa ile b anch o
na u al compu ing, which a ises as an abs ac ion o he com-
pa men alized s uc u e o li ing cells, and he way biochemical
subs ances a e p ocessed in (o mo ed be ween) memb ane
bounded egions P˘aun (2000). Memb ane compu ing is a pa adigm
p o iding compu ing de ices called P sys ems, which a e pa allel,
non-de e minis ic and dis ibu ed compu a ional models. Inspi ed
by ha s uc u e, wo main classes o P sys ems ha e been in es-
iga ed: (a) a hie a chical a angemen o memb anes as in a cell
P˘aun (2000), p ocessing in o ma ion by mul ise s o symbols; and
(b) a ne o p ocesso uni s placed in he nodes o a di ec ed g aph,
inspi ed by he cell in e communica ion in issues Ma ín-Vide e
al. (2003) o inspi ed by he way neu ons communica e wi h each
o he by means o sho elec ical impulses, iden ical in shape
( ol age), bu emi ed a p ecise momen s o ime Ionescu e al.
(2006). These models ha e wo in e es ing p ope ies: he
capabili y o sol e as many p oblems as a Tu ing machine (com-
pu a ional comple eness) and he abili y o sol e compu a ionally
ha d p oblems in a easible ime, by ading space o ime (compu-
a ional e ficiency). Gene al in o ma ion on memb ane compu ing
can be ound in P˘
aun e al. (2010), F isco (2009), and o he
mos up- o-da e e e ences, one can e e o he P sys ems websi e
h p://ppage.psys ems.eu.
A basic P sys em is based on a cell-like a angemen o mem-
b anes, ha a e placed in a nes ed hie a chical s uc u e; each
memb ane delimi s a compa men (also called egion) whe e mul-
ise s o objec s and ules o e ol ing hese objec s a e placed. A
memb ane wi h no compa men s inside is called elemen a y, o h-
e wise i is called non-elemen a y. The ou mos memb ane is called
askin memb ane, he space ou side he skin memb ane is called
he en i onmen . The e a e wo main ypes o e olu ion ules o
cell-like P sys ems associa ed wi h memb anes: mul ise ew i -
ing ules and communica ion (sympo /an ipo ) ules. The p esen
wo k ocuses on a class o P sys ems wi h sympo /an ipo ules,
which we e p oposed in P˘
aun and P˘
aun (2002). Sympo ules a e
o o m (u,in)o (u,ou ), and mo e objec s o mul ise u h ough a
memb ane; an ipo ules a e o o m (u, ou ; ,in), and mo e he
objec s o mul ise uou side a memb ane while mo ing he objec s
o mul ise inside.
Cell-like P sys ems ha e been s udied widely. Up o now,
esea che s ha e p oposed lo s o classes o cell-like P sys ems,
and many o hem ha e been p o ed o be compu a ionally com-
ple e (see, e.g., Alhazo and F eund (2005), Alhazo e al. (2006),
Be na dini and Gheo ghe (2003), Ciobanu e al. (2007), P˘
aun and
P˘
aun (2002), P˘
aun e al. (2005)). The compu a ional e ficiency o
cell-like P sys ems has also been in es iga ed P˘
aun e al. (2010).
A pa icula ly in e es ing class o cell-like P sys ems is ha o P
sys ems wi h ac i e memb anes P˘
aun (2000), which con ain objec
e olu ion ules, in communica ion ules, ou communica ion ules,
dissol ing ules and memb ane di ision ules. Memb ane di i-
sion ules can gene a e an exponen ial wo kspace in polynomial
ime (e en in linea ime). The e o e, P sys ems wi h ac i e mem-
b anes can be used o sol e compu a ionally ha d p oblems by a
ime-space ade-o P˘
aun (2001), Pé ez-Jiménez and Riscos-Nú˜
nez
(2004), Pé ez-Jiménez and Riscos-Nú˜
nez (2005).
In his wo k, memb ane di ision is in oduced in o cell-like P
sys ems, and hey e ol e by means o sympo /an ipo o di ision
ules, ha is, we p esen a class o P sys ems wi h sympo /an ipo
ules and memb ane di ision, whe e objec s a e ne e modified bu
hey jus change hei places, mo eo e , objec s can be commu-
nica ed wi h he en i onmen only h ough he skin memb ane.
The compu a ional e ficiency o such kind o P sys ems is s udied.
Specifically, we p esen polynomial ime solu ions o he Subse
Sum p oblem by using di ision ules o elemen a y memb anes and
o he QSAT p oblem by using di ision ules o non-elemen a y
memb anes. In bo h cases, he solu ions a e uni o m and hey a e
ob ained by using communica ion ules o leng h a mos 3.
2. P elimina ies
In his Sec ion, we only in oduce some basic no ions and no a-
ions om o mal languages heo y. Reade s can e e o Rozenbe g
and Salomaa (1997) o de ails.
An alphabe is a non-emp y se and hei elemen s a e called
symbols. An o de ed fini e sequence o symbols o e  o ms a
s ing. The leng h o a s ing u, deno ed by |u|, is he numbe o
occu ences o symbols i con ains. We deno e by ∗ he se o all
s ings o e . The emp y s ing (wi h leng h 0) is deno ed by ,
and by +=∗ {}we deno e he se o non-emp y s ings.
Fo an alphabe ,amul ise o e is a pai (, ) whe e
:→Nis a mapping, Nis he se o na u al numbe s. I m=(, )
is a mul ise , hen i s suppo is defined as supp(m)={x∈| (x)>0}.
I supp(m)={a1,...,ak} hen we deno e m={a (a1)
1,...,a
(ak)
k}.A
mul ise is fini e i i s suppo is a fini e se . We deno e by ∅
he emp y mul ise and by M () he se o all fini e mul ise s
o e .I m1=(, 1), m2=(, 2) a e mul ise s o e , hen he
union o m1and m2, deno ed by m1+m2, is he mul ise (,g),
whe e g(x)= 1(x)+ 2(x) o each x∈; he ela i e complemen
o m2in m1, deno ed by m1 m2, is he mul ise (,g), whe e
g(x)= 1(x)− 2(x)i 1(x)≥ 2(x), and g(x) = 0 o he wise.
3. P sys ems wi h sympo /an ipo ules and memb ane
di ision
In his Sec ion, we s udy P sys ems wi h sympo /an ipo ules,
a class o compu ing de ices aiming o abs ac he ac i e ans-
po o molecules ac oss he memb anes. In his kind o P sys ems,
objec s a e p ocessed in a pu e communica i e way, ha is, objec s
do no e ol e and only change hei places du ing he compu a ion
p ocess. Memb ane di ision ules a e allowed in such P sys ems.
Defini ion 1. A P sys em wi h sympo /an ipo ules
and memb ane di ision o deg ee q≥1 is a uple =
(, E,,M1,...,Mq,R1,...,Rq,i
ou ), whe e:
•is an alphabe ( he wo king alphabe ) and E⊆;
•is a oo ed ee wi h qnodes labeled by 1, ...,q;
•Mi,1≤i≤q, a e fini e mul ise s o e ;
•Ri,1≤i≤q, a e fini e se s o ules o he ollowing o ms:
(a1) Sympo ules: (u,ou )o (u,in), o u∈M (), |u|>0;
(a2) An ipo ules: (u, ou ; ,in), o u, ∈M (), |u|>0,| |>0;
(b) Di ision ules: [a]i→[b]i[c]i, o i∈{2, ...,q},i/=iou ,a,b,
c∈;
•iou ∈{0, 1, ...,q}.
A P sys em wi h sympo /an ipo ules and memb ane di i-
sion o deg ee q≥1 can be iewed as a se o qmemb anes labeled
by 1, ...,q, a anged in a hie a chical s uc u e o a oo ed ee
( he oo labeled by 1 is called he skin memb ane), such ha : (a)
M1,...,Mq ep esen he fini e mul ise s o objec s ini ially placed
in he qmemb anes o he sys em; (b) Eis he se o objec s ini ially
loca ed in he en i onmen o he sys em, all o hem a ailable in
an a bi a y numbe o copies; (c) R1,...,Rqa e fini e se s o ules
(Rico esponds o he memb ane io ); (d) iou is a dis inguished
egion which will encode he ou pu o he sys em. We use he e m
egion i(0 ≤i≤q) o e e o memb ane iin case 1 ≤i≤qand o e e
o he en i onmen in case i= 0. The leng h o a sympo ule (u,ou )
o (u,in) (an an ipo ule (u, ou ; ,in), espec i ely) is defined as
|u|(|u|+|
|, espec i ely).
Fo each memb ane i∈{2, ...,q}, we deno e by p(i) he pa en o
memb ane iin he oo ed ee , he “pa en ” o he skin memb ane
is he en i onmen , deno ed by p(1)=0.
Aconfigu a ion o such a P sys em a any momen is desc ibed
by he cu en memb ane s uc u e ( he oo ed ee), oge he wi h
all mul ise s o objec s o e associa ed wi h he egions o his
memb ane s uc u e and he mul ise o objec s o e  Eassoci-
a ed wi h he en i onmen a ha momen . The ini ial configu a ion
o (, E,,M1,...,Mq,R1,...,Rq,i
ou )is(, M1,...,Mq;∅).
A sympo ule (u, ou )∈Riis applicable o a configu a ion a a
momen i memb ane icon ains mul ise ua ha momen . When
such a ule is applied, mul ise uis sen o he pa en o memb ane
i. A sympo ule (u, in)∈Riis applicable o a configu a ion a a
momen i he pa en o memb ane icon ains mul ise ua ha
momen . When such a ule is applied, mul ise uen e s memb ane
i om he pa en o i.
An an ipo ule (u, ou ; ,in)∈Riis applicable o a configu a-
ion a a momen i memb ane icon ains mul ise uand i s pa en
con ains mul ise a ha momen . When such a ule is applied,
mul ise u om memb ane iis sen ou o memb ane i, and simul-
aneously, mul ise en e s egion i om he pa en o i.
A di ision ule [a]i→[b]i[c]iis applicable o a configu a ion a
a momen i he ollowing condi ions hold a ha momen : (1)
memb ane icon ains objec a; (2) memb ane iis nei he he skin
memb ane no he ou pu memb ane. When applying such a ule,
memb ane iis di ided in o wo memb anes wi h he same label:
in he fi s copy, objec ais eplaced by objec b, in he second
one objec ais eplaced by objec c, and all he objec s in he o ig-
inal memb ane, di e en om he objec igge ing he ule, a e
eplica ed in he wo new memb anes. Besides, i memb ane iis a
non-elemen a y memb ane, hen all memb anes inside memb ane
ias well as objec s con ained in hem, will be eplica ed in each o
he new memb anes.
The ules o a P sys em wi h sympo /an ipo ules and mem-
b ane di ision a e used in a maximally pa allel way. A each s ep, a
maximal mul ise o ules is applied (no u he ule can be added
being applicable) wi h he ollowing es ic ion: when a memb ane
is di ided, he di ision ule is he only one which is applied o
ha memb ane a ha s ep, he objec s inside ha memb ane do
no e ol e by means o communica ion ules. The objec s in he
new memb anes esul ing om di ision could pa icipa e in he
in e ac ion wi h he objec s in he (uppe o lowe ) neighbo o
memb anes by means o communica ion ules a he nex s ep i
hese new memb anes a e no di ided once again.
S a ing om he ini ial configu a ion and applying ules
as desc ibed abo e, one ob ains a sequence o consecu i e
configu a ions. Each passage om a configu a ion C o a nex
configu a ion Cis called a ansi ion and deno ed by C⇒C.A
configu a ion is a hal ing configu a ion i no ule o he sys em is
applicable o i . A compu a ion o such a P sys em is a (fini e o
infini e) sequence o ansi ions be ween configu a ions such ha :
(1) he fi s e m o he sequence is he ini ial configu a ion; (2)
each non-fi s e m o he sequence is ob ained om he p e ious
configu a ion by applying ules in a maximally pa allel way wi h
he abo e men ioned es ic ion; (3) i he sequence is fini e,
hen he las e m o he sequence is a hal ing configu a ion, and
such a compu a ion is called a hal ing compu a ion. Only hal ing
compu a ions gi e a esul , encoded by he mul ise o objec s
p esen in he ou pu egion iou .
3.1. Recognize P sys ems wi h sympo /an ipo ules and
memb ane di ision
Recognize P sys ems we e in oduced in Pé ez-Jiménez e al.
(2006), as a na u al amewo k o sol e decision p oblems.
Defini ion 2. A ecognize P sys em wi h sympo /an ipo ules
and memb ane di ision o deg ee q≥1 is a uple
=(, E,,,M1,...,Mq,R1,...,Rq,i
in,i
ou ),
such ha :
•(, E,,M1,...,Mq,R1,...,Rq,i
ou ) is a P sys em wi h sym-
po /an ipo ules and memb ane di ision o deg ee q≥1;
•has wo dis inguished objec s yes and no, wi h a leas one
copy o hem p esen in some mul ise s M1,...,Mq, bu none o
hem p esen in E;
•is an (inpu ) alphabe s ic ly con ained in , and such ha
E⊆ ;
•M1,...,Mqa e fini e mul ise s o e  ;
•iin ∈{1, ...,q}is he inpu memb ane, and iou =0;
•all compu a ions hal ;
•i Cis a compu a ion o , hen ei he objec yes o objec no
(bu no bo h) mus ha e been eleased in o he en i onmen ,
and only a he las s ep o he compu a ion.
Fo each fini e mul ise w∈M (), he compu a ion o a P sys-
em wi h sympo /an ipo ules and memb ane di ision wi h
inpu ws a s om a configu a ion o he o m (, M1,...,Miin +
w,...,Mq,∅), whe e he inpu mul ise wis added o he con en s
o he inpu memb ane iin.
We deno e by CDeC(k)(CDneC(k), espec i ely) he class
o ecognize P sys ems wi h di ision ules o elemen a y
memb anes (non-elemen a y memb anes, espec i ely) whose
sympo /an ipo ules ha e leng h a mos k.
3.2. Polynomial complexi y classes o ecognize P sys ems
Nex , we define he concep o polynomial ime sol abili y (in a
uni o m way) by means o amily o P sys ems (see Pé ez-Jiménez
(2005) o de ails).
Defini ion 3. A decision p oblem X=(IX,X) is sol able in poly-
nomial ime by a amily ={(n)|n∈N}o ecognize P sys ems
om CDeC(k)o CDneC(k), in a uni o m way, i he ollowing condi-
ions hold:
1. The amily is polynomially uni o m by Tu ing machines.
2. The e exis s a pai (cod,s) o polynomial- ime compu able unc-
ions o e IXsuch ha : (a) o 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));
(b) o each n∈N,s−1(n) is a fini e se ; and (c) he amily 
is polynomially bounded, sound and comple e wi h ega d o
(X,cod,s).
We deno e by PMCCDeC(k)(PMCCDneC(k), espec i ely) he se o
all decision p oblems which can be sol ed in a uni o m way and
polynomial ime by means o ecognize P sys ems om CDeC(k)
(CDneC(k), espec i ely).
4. Sol ing he Subse Sum p oblem by using CDeC(3)
Subse Sum p oblem is a nume ical NP-comple e p oblem,
which has been in es iga ed widely in memb ane compu -
ing. Specifically, di e en (uni o m) polynomial ime solu ions
ha e been p o ided by using amilies o P sys ems wi h ac i e
memb anes Pé ez-Jiménez and Riscos-Nú˜
nez (2005), P sys ems
wi h memb ane c ea ion Gu ié ez-Na anjo e al. (2005), and
issue P sys ems wi h cell di ision Díaz-Pe nil e al. (2007).
Nex , we p esen a solu ion o he Subse Sum p oblem by
combining he sympo /an ipo ules used in issue-like P sys-
ems and he memb ane di ision o P sys ems wi h ac i e
memb anes.
The Subse Sum p oblem is desc ibed as ollows: Gi en a fini e
se A, a weigh unc ion,w:A→N, and a cons an k∈N,de e mine
whe he o no he e exis s a subse B ⊆A, such ha w(B)=k.
Le g:N×N→Nbe he unc ion defined by g(n,
k)=((n+k)(n+k+ 1)/2) + n. I is a p imi i e ecu si e and bijec i e
unc ion. We deno e g(n,k)=n,k.
Fo each (n, k)∈N×N, we conside he ecognize P sys em
om CDeC(3)
(n, k)=(, E,,,M1,M2,R1,R2,i
in,i
ou ),
defined as ollows:
•={q}∪{
i|1≤i≤n};
•E={˛i|1≤i≤n+logn+log(k+1)+7}∪{ai|1≤i≤
n+logn+log(k+1)+1}∪{bi|1≤i≤n+logn+log(k+
1)+2}∪{ci|1≤i≤n+logn+log(k+1)+4}∪{di,j,l |1≤
i≤n, 1≤j≤log(k+1),1≤l≤n+j+1}∪{e, p};
•=∪E∪{Ai,B
i|1≤i≤n}∪{g, h, m, n, z, yes, no};
•=[[]2]1;
•M1={d1,1,1,...,d
1,log(k+1),1,d
2,1,1,...,d
2,log(k+1),1,...,
dn,1,1,..., dn,log(k+1),1,a1,b1,c1,n,˛1,yes,no}; and
M2={g, h, m, A1,...,A
n};
•iin = 2is heinpu memb ane; and iou = 0is heou pu egion;
•The se R1consis s o he ollowing ules:
1,i≡(˛i,ou ;˛i+1,in), 1 ≤i≤n+logn+log(k+1)+6.
2,i ≡(ai, ou ;a2
i+1,in), 1≤i≤n+logn+log(k+1).
3,i ≡(bi, ou ;b2
i+1,in), 1 ≤i≤n.
4,i≡(bi,ou ;bi+1,in), n+1≤i≤n+logn+log(k+1)+1.
5,i ≡(ci, ou ;c2
i+1,in), 1 ≤i≤n.
6,i≡(ci,ou ;ci+1,in), n+1≤i≤n+logn+log(k+1)+3.
7,i,j,l ≡(di,j,l, ou ;d2
i,j,l+1,in)1≤i≤n, 1≤j≤log(k+1)
1≤l≤n+j
8≡(an+logn+log(k+1)+1,ou ;p,in).
9≡(bn+logn+log(k+1)+2,ou ;e,in).
10 ≡(m n yes ,ou ).
11 ≡(n˛n+logn+log(k+1)+7 no,ou ).
•The se R2consis s o he ollowing ules:
12,i ≡[Ai]2→[Bi]2[z]2,1≤i≤n.
13,i ≡(Bi, ou ;d2
i,1,n+2,in), 1 ≤i≤n.
14,i,j,l ≡(di,j,l, ou ;d2
i,j+1,l+1,in)1≤i≤n, 1≤j≤log(k+1)−1
n+2≤l≤n+log(k+1)
15,i ≡(di,log(k+1),n+log(k+1)+1 i, ou ;p, in), 1 ≤i≤n.
16 ≡(pq,ou ).
17 ≡(g,ou ;e,in).
18 ≡(ep,ou ).
19 ≡(eq,ou ).
20 ≡(h,ou ;cn+logn+log(k+1)+4,in).
21 ≡(emc
n+logn+log(k+1)+4,ou ).
The compu a ion p ocess can be di ided in he ollowing phases.
•Gene a ion phase: a he fi s ns eps, all possible subse s o Aa e
gene a ed by applying memb ane di ision ules o memb anes
wi h label 2. Simul aneously, 2ncopies o objec s di,j,n+1,an+1,bn+1,
cn+1 a e p oduced in memb ane 1, and he coun e ˛ie ol es in
memb ane 1.
•P e-checking phase: a e he gene a ion phase, he e a e 2ncopies
o memb ane 2, each o hem con aining a subse o A. Then as
many copies o objec pas he weigh o he co esponding subse
a e in oduced in memb ane 2. To his aim, we should in oduce
enough copies o aiin memb ane 1 fi s , hen as many copies o
pas objec an+logn+log(k+1)+1 will be in oduced in memb ane 1.
•Checking phase: in each memb ane wi h label 2, he numbe o
copies o objec s pand qa e compa ed by sending all possible
pai s (p,q) o memb ane 1. A e doing ha , a memb ane wi h
label 2 will encode a subse o Awhose weigh is equal o ki and
only i no objec po q emains in ha memb ane.
•Ou pu phase: a e he checking phase, he sys em sends an a fi -
ma i e answe o he en i onmen i he e exis s a leas one
memb ane wi h label 2 wi hou objec s po q;o anega i e
answe i each memb ane wi h label 2 con ains some objec (s)
po q.
4.1. An o e iew o he compu a ion
Fi s , we conside a pai (cod,s) o polynomial ime unc ions
o e he se o ins ances o he Subse Sum p oblem. Fo ha , le
u=(A, w, k) be an ins ance o he p oblem and A={z1,z2,...,zn}.
Then,
•cod(u)={
j
i|w(zi)=j∧1≤i≤n}∪{qk}„ whe e j
i(jcopies o
objec i) ep esen s ha jis he weigh o elemen zi.
•s(u)=n,k.
In his si ua ion, ins ance u=(A, w, k) will be p ocessed by
sys em (s(u)) wi h inpu mul ise cod(u). In wha ollows, we
desc ibe in o mally how he ecognizing P sys em (s(u)) om
CDeC(3) wi h inpu cod(u) wo ks.
A he ini ial configu a ion, we ha e objec s a1,b1,c1,n,˛1,d1,1,1,
...,d1,log(k+1),1,d2,1,1,...,d2,log(k+1),1,...,dn,1,1,...,dn,log(k+1),1,
yes,no in memb ane 1, objec s A1,...,An,g,h,m,cod(u)inmem-
b ane 2.
The gene a ion phase spends ns eps and he di ision ules 12,i
a e applied in memb ane 2 p oducing 2ncopies o memb ane 2,
each o hem con ains a subse o A; simul aneously, in memb ane
1, by using ules 2,i, 3,i, 5,i, 7,i,j,l, objec s ai,bi,ci,di,j,lwill be dupli-
ca ed un il ge ing 2ncopies in exac ly ns eps; besides, by applying
ule 1,i, he coun e objec ˛iinc eases i s subsc ip by 1 a each
s ep. Rule 1,iwill be applied in he whole compu a ion p ocess
excep o he las s ep in he case ha he answe is nega i e. No e
ha objec zis an idle objec in cells wi h label 2.
The p e-checking phase s a s a s ep n+ 1. In his phase, we
should in oduce enough copies o objec pin each memb ane 2,
bu hose objec s a e fi s in oduced in memb ane 1. Specifically,
a s ep n+1, 2
n+1 copies o objec s di,j,n+2 a e p oduced in mem-
b ane 1 by applying ules 7,i,j,n+1 (1≤i≤n,1≤j≤log(k+1)). A
nex s ep, by using ules 13,i, one copy o objec Biin each mem-
b ane 2 is exchanged wi h wo copies o objec di,1,n+2 in memb ane
1 (a ha s ep, in all memb anes 2 he e a e a mos 2ncopies o
objec Bi, and in memb ane 1, he e a e 2n+1 copies o objec di,1,n+2).
Besides, a s ep n+ 2, objec s di,j,n+2 (1≤i≤n,2≤j≤log(k+1))
a e duplica ed by using ules 7,i,j,n+2, and 2n+2 copies o objec s
di,j,n+3 a e p oduced in memb ane 1. A s ep n+ 3, objec s di,j,n+3
(1≤i≤n,3≤j≤log(k+1)) a e duplica ed by using ules 7,i,j,n+3,
and 2n+3 copies o objec s di,j,n+4 a e p oduced in memb ane 1.
Simul aneously, each copy o objec di,1,n+2 in all memb anes 2 is
exchanged wi h wo copies o objec di,2,n+3 in memb ane 1 (a ha
s ep, in all memb anes 2 he e a e a mos 2n+1 copies o objec
di,1,n+2, and in memb ane 1, he e a e 2n+2 copies o objec di,2,n+3).
By applying ules 7,i,j,land 14,i,j,las many imes as possible, a s ep
n+log(k+1)+1, in each memb ane 2 ha con ains objec Bi,we
ob ain 2log(k+1)copies o objec di,log(k+1),n+log(k+1)+1, so a leas
k+ 1 copies will be a ailable.
F om s ep n+ 1 o s ep n+logn+log(k+1), objec aiwill be
duplica ed by using ule 2,i, ha is, a s ep n+logn+log(k+1),
he e a e 2n+logn+log(k+1)copies o objec an+logn+log(k+1)+1 in
memb ane 1. In his p ocess, coun e s bi,ciinc ease hei subsc ip s
by applying 4,i, 6,i.
A s ep n+logn+log(k+1)+1, objec an+logn+log(k+1)+1 in
memb ane 1 is exchanged wi h objec p om he en i onmen by
using ule 8. All copies o objec s bi,ciinc ease hei subsc ip s a
his s ep.
A s ep n+logn+log(k+1)+2, objec bn+logn+log(k+1)+2 has
2ncopies in memb ane 1 and each such copy is exchanged wi h
objec e om he en i onmen ( ule 9). By using ule 6,i,2
ncopies
o objec cn+logn+log(k+1)+3 will p esen in memb ane 1. Simul-
aneously, by applying ules 15,iin all memb anes 2, o each
elemen Biin he subse associa ed wi h he memb ane we ge
min{2log(k+1),w(si)}copies o objec p.
The checking phase s a s a s ep n+logn+log(k+1)+3. In
his s ep, by using ule 16, all pai s o objec s pand qp esen in
any memb ane wi h label 2 a e sen o memb ane 1. In his way,
i he weigh o he subse associa ed wi h a memb ane 2 is equal
o k, hen no objec po q emains in his memb ane a he nex
s ep. O he wise, a leas one copy o objec po qwill emain in
he memb ane. Simul aneously, in e e y memb ane 2 objec gis
exchanged wi h objec ein memb ane 1 ( ule 17), ha is, each
memb ane 2 will con ain one copy o objec e; objec ciinc eases
i s subsc ip , and 2ncopies o objec cn+logn+log(k+1)+4 appea in
memb ane 1.
When he checking phase finishes, he ou pu phase s a s a
s ep n+logn+log(k+1)+4. The e a e wo cases.
•The e exis s a leas one memb ane 2 wi h a subse whose weigh
is equal o k. In his case, a s ep n+logn+log(k+1)+4, i a
memb ane 2 con ains a leas one copy o objec po q, hen objec
ewill be sen o memb ane 1 by using ule 18 o 19; o he wise,
objec ewill emain in ha memb ane. Simul aneously, objec h
in all memb anes 2 is exchanged wi h objec cn+logn+log(k+1)+4
by using ule 20 (each memb ane 2 will con ain one copy o
objec cn+logn+log(k+1)+4). A he nex s ep, by applying ule 21,
objec s e,m,cn+logn+log(k+1)+4 a e sen o memb ane 1 in case
he weigh o he subse in ha memb ane 2 is equal o k. A s ep
n+logn+log(k+1)+6, by using ule 10, objec s m,n,yes a e
sen o he en i onmen and he compu a ion hal s. Thus, he
answe o he sys em is a fi ma i e.
•The e is no memb ane 2 wi h a subse whose weigh is equal
o k. In his case, a s ep n+logn+log(k+1)+4, objec e
is sen o memb ane 1 om each memb anes 2 by using ule
18 o 19. Simul aneously, by applying ule 20, each mem-
b ane 2 will con ain one copy o objec cn+logn+log(k+1)+4.A
he nex wo s eps, only he coun e objec ˛ie ol es by apply-
ing ule 1,i. A s ep n+logn+log(k+1)+7, by using ule 11,
objec s n,˛n+logn+log(k+1)+7,no a e sen o he en i onmen
and he compu a ion hal s. Thus, he answe o he sys em is
nega i e.
4.2. Some o mal de ails
Family ={(n, k)|n, k ∈N}is polynomially uni o m by
Tu ing machines, because he ules o a sys em (n,k)o he
amily a e defined ecu si ely om he alues nand k. Besides, he
necessa y esou ces o defining each such sys em a e o polyno-
mial o de .
•size o he alphabe : ((2n2+3n+8)·log(k+1)+n·log(k+1)2
+12n+8logn+46)/2 ∈O(n2·logk+n·logk2);
•ini ial numbe o memb anes: 2 ∈O(1);
•ini ial numbe o objec s: n·log(k+1)+n+10∈O(n·logk);
•numbe o ules: ((2n2−3n+8)·log(k+1)+3n·log(k+1)2
+8logn+20n+ 40)/2 ∈O(n2·logk+n·logk2);
•maximum leng h o a ule: 3 ∈O(1).
Hence, he e exis s a de e minis ic Tu ing machine ha builds
he sys em (n,k) in a polynomial ime wi h espec o nand k.
Acco ding o he abo e men ioned compu a ion p ocess,
i is clea ha P sys em (n,k) wi h inpu mul ise
cod(u) always hal s and sends o he en i onmen objec
yes (a s ep n+logn+log(k+1)+6) o objec no (a s ep
n+logn+log(k+1)+7). The e o e, he e exis s a polynomial
bound o he numbe o s eps o he compu a ion.
Hence, he amily o ecognize P sys ems wi h sym-
po /an ipo ules and memb ane di ision sol es he Subse Sum
p oblem in polynomial ime acco ding o Defini ion 3. So, he ol-
lowing esul is ob ained.
Theo em 1. Subse Sum ∈PMCCDeC(3).
Co ola y 1. NP ∪co −NP ⊆PMCCDeC(3).
P oo 1. I su fices o make he ollowing obse a ions: heSubse
Sum p oblem is NP-comple e, Subse Sum ∈PMCCDeC(3) and he class
PMCCDeC(3) is closed unde polynomial ime educ ion, and is also
closed unde complemen . 
5. Sol ing he QSAT p oblem by using CDneC(3)
In his Sec ion, we p o ide a (uni o m) polynomial ime solu-
ion o he QSAT p oblem (quan ified sa isfiabili y p oblem), a
well-known PSPACE-comple e p oblem Papadimi iou (1994),by
a amily o P sys ems wi h di ision ules o non-elemen a y mem-
b anes and sympo /an ipo o leng h a mos 3.
Gi en a Boolean o mula ϕ(x1,...,xn) in conjunc i e no -
mal o m, wi h Boolean a iables x1,...,xn, he sen ence
ϕ*=∃x1∀x2...Qnxnϕ(x1,...,xn) (whe e Qnis ∃i nis odd, and Qn
is ∀o he wise) is said o be he (exis en ial) ully quan ified o mula
associa ed wi h ϕ(x1,...,xn). We say ha ϕ*is sa isfiable i he e
exis s a u h assignmen , , o e {i:1≤i≤n∧iodd}such ha
each ex ension, *,o o e {1, ...,n} e ifies *(ϕ(x1,...,xn)) = 1.
The QSAT p oblem is he ollowing one: Gi en he (exis en ial)
ully quan ified o mula ϕ∗associa ed wi h a Boolean o mula ϕ(x1,
...,x
n) in conjunc i e no mal o m, de e mine whe he o no ␸*is
sa isfiable.
The solu ion p oposed ollows a b u e o ce algo i hm in he
amewo k o ecognize P sys ems wi h sympo /an ipo ules
and memb ane di ision, and i consis s o he ollowing phases:
•Gene a ion phase: using memb ane di ision o non-elemen a y
memb anes, all u h assignmen s o he a iables associa ed
wi h he Boolean o mula a e p oduced.
•Checking phase: checking whe he o no he o mula ϕ(x1,...,xn)
is sa isfied.
•Quan ifie phase: checking whe he he whole o mula ϕ*wi h
quan ifie s is sa isfied.
Fig. 1. The ini ial memb ane s uc u e o he P sys em.
•Ou pu phase: he sys em sends o he en i onmen he igh
answe acco ding o he esul s o he p e ious phase.
We define a amily ={( )| ∈N}o ecognize P sys ems
om CDneC(3) such ha each sys em ( ) will p ocess all ins ances
o he QSAT p oblem wi h n a iables and mclauses, whe e =m,
n, p o ided ha he app op ia e inpu mul ise is supplied o he
sys em.
Fo each (m, n)∈N×N, we conside he ecognize P sys em
om CDneC(3),
(m, n)=(, E,,,M1,...,M2n+3,R1,...,R2n+3,i
in,i
ou ),
defined as ollows:
•={xi,j, xi,j |1≤i≤n, 1≤j≤m}.
•E={di,g
i|0≤i≤n2+3n+2m+3−k}∪{gn2+3n+2m+4−k}
(whe e k=n
2is he numbe o uni e sal quan ifie s in ϕ*).
•=∪E∪{ai,b
i,
i,
i|1≤i≤n}∪{Ei|0≤i≤m+1}∪
{ , yes, no}.
•=[[[[...[[[]2n+1]n[]2n−1]n−1...]2[]n+1]1[]2n]2n+2]2n+3( he oo
is he memb ane wi h label 2n+ 3 whose child is labeled by
2n+ 2; his memb ane has wo child en labeled by 2nand 1,
espec i ely; each memb ane wi h label i,1≤i≤n−1, con ains
a non-elemen a y memb ane wi h label i+ 1 and an elemen a y
memb ane wi h label n+i, see Fig. 1).
•M1={a1},Mn+i={bi},1≤i≤n,M2n+2=Mi=∅,2≤i≤n.
•M2n+1={ , a2,...,a
n,E
0,E
1,...,E
m+1},M2n+3=
{d0,g
0, yes, no}.
•iin =2n+ 1is heinpu memb ane, and iou = 0is heou pu egion.
•The se s o ules a e defined below:
•Rules in Ri(1 ≤i≤n): 1,i ≡[ai]i→[ i]i[ i]i.
•Rules in Ri(2 ≤i≤n): 2,i,j≡( j,in) and 3,i,j≡( j,in), 1 ≤j≤i−1.
•Rules in Ri(3 ≤i≤n): 4,i,j≡(aj,ou ), 2 ≤j≤i−1.
•Rules in R2n+1:
5,i≡(ai+1,ou ; i,in), 1 ≤i≤n−1.
6,i≡(ai+1,ou ; i,in), 1 ≤i≤n−1.
7≡(E0E1,ou ; n,in).
8≡(E0E1,ou ; n,in).
9,i,j≡( ixi,j,ou ;Ej,in), 1 ≤i≤n,1≤j≤m.
10,i,j ≡( ixi,j, ou ;Ej,in), 1 ≤i≤n,1≤j≤m.
11,i,j≡(Ej+1,ou ; ixi,j,in), 1 ≤i≤n,1≤j≤m.

12,i,j ≡(Ej+1, ou ; ixi,j,in), 1 ≤i≤n,1≤j≤m.
13 ≡( ,ou ;Em+1,in).
•Rules in Rn: 14 ≡( ,ou ).
•I Qi+1 =∀(1 ≤i≤n−1):
() Rules in Rn+i: 15,i≡(bi,ou ; ,in).
() Rules in Ri: 16,i≡(bi ,ou ).
•I Qi+1 =∃(1 ≤i≤n−1):
() Rules in Rn+i: 17,i≡( ,in) and 18,i≡(bi ,ou ).
() Rules in Ri: 19,i≡(bi ,ou ).
•Rules in R2n: 20 ≡( ,in) and 21 ≡(bn ,ou ).
•Rules in R2n+2: 22 ≡(bn ,ou ).
•Rules in R2n+3:
23 ≡(dn2+3n+2m+3−k yes, ou ).
24,i≡(di,ou ;di+1,in), 0 ≤i≤n2+3n+2m+2−k.
25,i≡(gi,ou ;gi+1,in), 0 ≤i≤n2+3n+2m+3−k.
26 ≡(dn2+3n+2m+3−kgn2+3n+2m+4−kno, ou ).
5.1. An o e iew o he compu a ion
In wha ollows, we in o mally desc ibe how P sys em (s(ϕ*))
wi h inpu mul ise cod(ϕ*) wo ks. Le us ecall ha kdeno es he
numbe o uni e sal quan ifie s in ϕ*, ha is, k=n
2.
A he ini ial configu a ion, we ha e objec a1in memb ane 1,
objec bi(1 ≤i≤n) in memb ane n+i, objec s a2,...,an,E1,...,Em+1,
,cod(ϕ*) in memb ane 2n+ 1, objec s g0,yes, no in memb ane
2n+3.
Le us s a wi h he gene a ion phase. This phase has wo
pa allel p ocesses. On he one hand, he sys em assigns u h-
assignmen s o all a iables xi(1 ≤i≤n). When gene a ion phase
comple es, we p oduce 2ncopies o memb ane 2n+ 1, each o hem
con ains a di e en u h assignmen s o he a iable se {x1,...,
xn}associa ed wi h he Boolean o mula. On he o he hand, he
coun e objec s di,giin memb ane 2n+ 3 g ow hei subsc ip s by
using ules 26,i, 27,i. We desc ibe he p ocess o gene a ion phase
as ollows.
Wi h he appea ance o objec aiin each memb ane ia he same
s ep, he sys em s a s o assign u h-assignmen o a iable xi
(1 ≤i≤n−1). Specifically, by using ule 1,iin all memb anes i, each
non-elemen a y memb ane iis di ided in o wo copies wi h he
same label, which con ain objec s i( ep esen ing he u h alue
ue) and i( ep esen ing he u h alue alse), espec i ely. No e
ha all he memb anes and objec s placed inside he memb ane
ia e eplica ed in he new copies. A nex s eps, all objec i( i,
espec i ely) in memb anes wi h label iwill be sen o memb anes
nby using ules 2,j,i( 3,j,i, espec i ely) (i+1≤j≤n) one by one.
When objec i( i, espec i ely) appea s in each memb ane na he
same s ep, ule 5,i( 6,i, espec i ely) is enabled and applied, objec
ai+1 in memb ane 2n+ 1 is exchanged wi h objec i( i, espec i ely)
in memb ane n. When objec ai+1 appea s in memb anes n, by using
ules 4,j,i+1 (i+2≤j≤n) one by one, objec ai+1 will be p esen ed in
each memb ane i+ 1 a he same s ep. Simila o he case o a iable
xi, he sys em con inues o assign a u h-assignmen o a iable
xi+1. I is easy o see ha he p ocess o assigning u h-assignmen
o a iable xi(1 ≤i≤n−1) akes 2n−2i+ 1 s eps. Wi h he appea -
ance o objec anin memb anes na he same s ep, he sys em
s a s o assign u h-assignmen o a iable xn. By using ule 1,n,
each non-elemen a y memb ane nis di ided in o wo copies a
he same s ep, which con ain objec s n( ep esen ing he u h
alue ue) and n( ep esen ing he u h alue alse), espec i ely.
A he nex s ep, ule 7( 8, espec i ely) is enabled and applied,
objec s E0,E1in memb anes 2n+ 1 a e exchanged wi h objec n
( n, espec i ely) in memb anes n. The p ocess o assigning a u h-
assignmen o a iable xn akes wo s eps. Hence, he gene a ion
phase akes n2+ 1 s eps. The memb ane s uc u e o he sys em a
ha momen when he gene a ion phase comple es is shown in
Fig. 2.
Fig. 2. The memb ane s uc u e o he sys em when he gene a ion phase com-
ple es. Numbe s a nodes indica e labels o memb anes.
The checking phase akes 2ms eps and consis s o mloops (each
loop akes 2 s eps). In pa allel wi h checking whe he he e is a
u h assignmen ha makes he o mula ϕe alua e o be ue, he
coun e objec s di,gialso g ow hei subsc ip s by one o each s ep
in memb ane 2n+3.
A he fi s s ep o he j- h loop (1 ≤j≤m) o checking
phase, objec s i,xi,j( i, xi,j, espec i ely) in memb ane 2n+ 1 a e
exchanged wi h objec Ejin memb ane nby using ule 9,i,j( 10,i,j,
espec i ely), in case memb ane 2n+ 3 encodes a u h assignmen
making clauses C1,...,Cj ue. No e ha o any memb ane 2n+1,
which con ains a u h assignmen ha does no make he clause
Cj ue, he compu a ion in ha memb ane s ops a he ime when
9,i,jo 10,i,jis applied. A he second s ep o he j- h loop (1 ≤j≤m)
o checking phase, wi h he appea ance o objec s i,xi,j( i, xi,j,
espec i ely) in memb ane n, by using ule 11,i,j( 12,i,j, espec-
i ely), objec Ej+1 in memb ane 2n+ 1 is exchanged wi h he objec s
i,xi,j( i, xi,j, espec i ely) in memb ane n.
A e n2+2m+ 1 s eps, we ha e checked whe he o no o mula
ϕissa isfied by he co esponding u h assignmen .Fo eachclause
Cjwhich is sa isfied, he subsc ip jo Eis inc eased by one; hence
objec Em+1 will appea in memb ane ni and only i i s lowe neigh-
bo memb ane 2n+ 1 encodes he u h assignmen ha sa isfies
all clauses. A s ep n2+2m+ 2, i memb ane ncon ains Em+1 hen
by using ule 13, objec in memb ane 2n+ 1 is exchanged wi h
objec Em+1 in memb ane n. A he nex s ep, i objec appea s in
memb ane n, by applying ule 14, hen i will be sen o memb ane
n−1.
The quan ifie phase s a s a he (n2+2m+ 4)- h s ep. In mem-
b ane 2n+ 3 he coun e objec s di,gig ow hei subsc ip s by one
o each s ep. A memb ane wi h label ico esponds o he quan i-
fie Qj, whe e 1 ≤i≤n−1, j=i+ 1, and a memb ane wi h label 2n+2
co esponds o he quan ifie Q1.I Qj=∀, objec is passed o he
uppe le el only i i comes om bo h lowe le el memb anes, ha
is, he espec i e clauses a e sa isfied o bo h u h alues o xj.I
Qj=∃, hen a single objec coming om lowe le el is enough. In
wha ollows, we desc ibe how he sys em simula es quan ifie s ∀
and ∃.
Fo quan ifie Qi+1 =∀(1 ≤i≤n−1 and iis odd), one copy o
objec can be sen o he uppe le el memb ane i and only i he e
a e wo copies o objec in a memb ane i, whe e each lowe le el
memb ane p o ides one copy o objec . Specifically, by using ule
15,i, objec biin memb anes n+iis exchanged wi h objec in hei
uppe le el memb anes i. No e ha he e is one copy o objec biin a
memb ane n+i, hus, only one copy o objec is sen o memb ane
n+i om a memb ane i. A he nex s ep, objec s bi, in memb anes
ia e sen o hei uppe le el memb anes by applying ule 16,i.
In case Qi+1 =∃(1 ≤i≤n−1 and iis e en), by using he ule 17,i
in all memb anes n+i, all copies o objec will be sen o hei
lowe le el memb anes n+i. A he nex s ep, objec s bi, a e sen
o memb ane iby using ule 18,i. I he e a e wo copies o objec in
memb ane n+i, hen only one copy o objec is sen o memb ane
ibecause he e is only one copy o objec biin a memb ane n+i.A
he nex s ep, objec s bi, in memb anes ia e sen o hei uppe
le el memb anes by using ule 19,i.AsQ1=∃, by using he ules 20,
21, 22 one by one, one copy o objec is sen o he memb ane
2n+3.
Hence, he simula ion o all uni e sal quan ifie s akes 2ks eps,
and he simula ion o all exis en ial quan ifie s akes 3(n−k) s eps
( he numbe o such quan ifie s is n−k). Thus, he quan ifie phase
akes 3n−ks eps.
The ou pu phase s a s a he (n2+3n+2m+4−k)- h s ep, and
i akes 1 s ep (a fi ma i e answe ) o 2 s eps (nega i e answe ).
Le us ecall ha memb ane 2n+ 3 a configu a ion Cn2+3n+2m+3−k
con ains objec s dn2+3n+2m+3−k,gn2+3n+2m+3−k,yes and no. The e
a e wo cases.
–A fi ma i e answe : i objec appea s in memb ane 2n+ 3 a con-
figu a ion Cn2+3n+2m+3−k, hen ules 23 and 25,n2+3n+2m+3−ka e
applicable and objec s dn2+3n+2m+3−k, and yes a e sen o he
en i onmen . Memb ane 2n+ 3 a configu a ion Cn2+3n+2m+4−k
only con ains objec s gn2+3n+2m+4−kand no. The e o e, he com-
pu a ion hal s.
–Nega i e answe : i objec does no appea in memb ane 2n+3
a configu a ion Cn2+3n+2m+3−k, hen only ule 25,n2+3n+2m+3−kis
applicable. Thus, ha memb ane a configu a ion Cn2+3n+2m+4−k
con ains objec s yes, no,gn2+3n+2m+4−k,d
n2+3n+2m+3−k. A he
nex s ep, by using ule 26, objec s gn2+3n+2m+4−k,d
n2+3n+2m+3−k
and no a e sen o he en i onmen and memb ane 2n+ 3 a con-
figu a ionCn2+3n+2m+5−konly con ains objec yes, so i isa hal ing
configu a ion.
5.2. Some o mal de ails
In o de o show ha he amily ={(m, n)|m, n ∈N}
defined abo e is polynomially uni o m by Tu ing machines we need
o p o e ha (m,n) is buil in polynomial ime wi h espec o
he size pa ame e m,no ins ances o he QSAT p oblem ( ecalling
ha k≤n).
I is easy o show ha he ules o a sys em (m,n) o he amily
a e defined ecu si ely om he alues m,n, and he necessa y
esou ces o cons uc (m,n) a e as ollows:
•size o he alphabe : 2n2+2nm +10n+5m−2k+12∈O(n2+nm);
•ini ial numbe o memb anes: 2n+3∈O(n);
•ini ial numbe o objec s: 2n+m+7∈O(n+m);
•numbe o ules: (7n2+8nm +23n+8m−4k+ 20)/2 ∈O(n2+nm);
•maximum leng h o a ule: 3 ∈O(1).
Thus, he e exis s a de e minis ic Tu ing machine ha builds he
sys em (m,n) in a polynomial ime wi h espec o mand n.
By he abo e checking o he compu a ion p ocess, we can p o e
ha he P sys em (m,n) wi h inpu mul ise cod(ϕ*) always hal s
and sends o he en i onmen objec yes o no in he las s ep, ha
is, a s ep n2+3n+2m+4−k, objec yes is sen o he en i onmen
and he sys em hal s; objec no is sen o he en i onmen a s ep
n2+3n+2m+5−kand he sys em hal s. The e o e, he e exis s a
polynomial bound o he numbe o s eps o he compu a ion.
Hence, he amily o ecognize P sys ems wi h sym-
po /an ipo ules and memb ane di ision sol es he QSAT
p oblem in polynomial ime acco ding o Defini ion 3. So, he ol-
lowing esul is ob ained.
Theo em 2. QSAT ∈PMCCDneC(3).
Since he complexi y class PMCCDneC(3) is closed unde polyno-
mial ime educ ions, we ha e he ollowing esul .
Co ola y 2. PSPACE ⊆PMCCDneC(3).
6. Conclusions and discussion
The compu a ional e ficiency o di e en compu ing de ices in
memb ane compu ing has been es ablished. Wi h ega d o cell-
like compu ing de ices, e ficien solu ions o ha d p oblems ha e
been gi en in he amewo k o P sys ems wi h ac i e memb anes
ha use e olu ion, send-in, send-ou , dissolu ion and di ision ules.
Specifically, polynomial ime solu ions o he SAT p oblem Pé ez-
Jiménez e al. (2003) (in a uni o m way by using elec ical cha ges)
and he QSAT p oblem Alhazo and Pé ez-Jiménez (2007) (in a
semi-uni o m way, wi hou elec ical cha ges and allowing di ision
o non-elemen a y memb anes) ha e been p oposed. Wi h ega d
o issue-like compu ing de ices, an e ficien (uni o m) solu ion o
he HAM-CYCLE p oblem by a amily o issue P sys ems wi h cell
di ision and sympo /an ipo ules o leng h a mos 2, has been
gi en Po eca e al. (2012).
In his wo k, he compu a ional e ficiency o cell-like pola -
iza ionless P sys ems wi h sympo /an ipo ules and memb ane
di ision has been in es iga ed. Specifically, a (uni o m) linea ime
solu ion o he NP-comple e p oblem Subse Sum by using di i-
sion ules o elemen a y memb anes and communica ion ules o
leng h a mos 3, has been gi en. We u he p o ed ha such P
sys em can e ficien ly sol e he PSPACE-comple e p oblem QSAT
p oblem, in a uni o m way, when di ision ules o non-elemen a y
memb anes a e allowed. I is wo h no ing ha he solu ion o QSAT
gi en in he pape can be adap ed o a uni o m solu ion bea ing in
mind ha o (exis en ial) ully quan ified o mula associa ed wi h
ϕ(x1,...,xn), he numbe o uni e sal quan ifie s is n
2.
We p opose some open p oblems ela ed o he ole o commu-
nica ion ules in cell-like P sys ems wi h memb ane di ision om
a compu a ional complexi y poin o iew.
(a) In he solu ion o QSAT p oposed in his pape , di ision ules o
non-elemen a y memb anes ha e been conside ed. Is i pos-
sible o p o ide an e ficien solu ion o QSAT by using only
di ision ules o elemen a y memb anes?
(b) The P sys ems cons uc ed in Sec ion 4and in Sec ion 5ha e
bo h sympo ules and an ipo ules. Wha abou he compu-
a ional e ficiency o P sys ems wi h memb ane di ision ha
use only ei he sympo o an ipo ules?
(c) I is known ha NP ∪co −NP ⊆PMCTDC(2) Po eca e al. (2012).
Wha abou he compu a ional e ficiency o CDeC(2)?
(d) The en i onmen is no ele an o issue P sys ems wi h sym-
po /an ipo ules and cell di ision om a complexi y poin
o iew Pé ez-Jiménez e al. (2013). Wha abou he e ficiency
o ecognize P sys ems om CDC(k) when he alphabe o he
en i onmen is an emp y se ?
P sys ems cap u e he inhe en deg ee o eedom p esen in
biological sys ems h ough he non-de e minism. Wi h he inclu-
sion o his ing edien , P sys ems a e able o sol e ha d p oblems in
an “e ficien ” way a he heo e ical le el by ading ime o space.
New bounda ies be ween ac abili y and NP-ha dness, in e ms o
syn ac ical ing edien s o P sys ems, p o ide new ools o ackle he
P e sus NP p oblem.
Di e en simula o s o P sys ems unning on con en ional
compu e s ha e been de eloped du ing he las decade. The addi-
ion o pa allel compu ing echniques, like hose based on GPU, is
accele a ing hese simula o s. Wi h he aid o P sys ems simula o s,
esea che s aim o sol e la ge ins ances o NP ha d p oblems han
he bes ones p o ided so a , unning on elec onic compu e s.
Howe e , we would like o s ess ha such simula o s a e no eal
implemen a ion o P sys ems. Ob iously, an e ficien eal imple-
men a ion o P sys ems would p o ide a “cons uc i e” p oo o
he esul P=NP, ha is, simila ly o wha would happen wi h a
p ac ical implemen a ion o non-de e minis ic Tu ing machines.
Acknowledgemen s
The wo k o B. Song and L. Pan was suppo ed by Na ional
Na u al Science Founda ion o China (61033003, 91130034, and
61320106005), Ph.D. P og ams Founda ion o Minis y o Educa-
ion o China (2012014213008), and Na u al Science Founda ion o
Hubei P o ince (2011CDA027). The wo k o M.J. Pé ez-Jiménez was
suppo ed by “Minis e io de Economía y Compe i i idad” o Spain
(TIN2012-37434), co unded by FEDER unds.
Re e ences
Alhazo , A., F eund, R., 2005. P sys ems wi h one memb ane and sympo /an ipo
ules o fi e symbols a e compu a ionally comple e. In: P oceedings o Thi d
B ains o ming Week On Memb ane Compu ing, Se illa, Spain, pp. 19–28.
Alhazo , A., Rogozhin, Yu., 2006. Towa ds a cha ac e iza ion o P sys ems wi h min-
imal sympo /an ipo and wo memb anes. In: Vol. 4361 o Lec u e No es in
Compu e Science. Sp inge , Be lin/Heidelbe g, pp. 135–153.
Alhazo , A., Pé ez-Jiménez, M.J., 2007. Uni o m solu ion o QSAT using pola iza-
ionless ac i e memb anes. In: Vol. 4664 o Lec u e No es in Compu e Science.
Sp inge , Be lin/Heidelbe g, pp. 122–133.
Be na dini, F., Gheo ghe, M., 2003. On he powe o minimal sympo /an ipo . In:
P oceedings o he 3 d Wo kshop on Memb ane Compu ing, Ta agona, pp.
72–83.
Ciobanu, G., Pan, L., P˘
aun, Gh., Pé ez-Jiménez, M.J., 2007. P sys ems wi h minimal
pa allelism. Theo . Compu . Sci. 378, 117–130.
Díaz-Pe nil, D., Gu ié ez-Na anjo, M.A., Pé ez-Jiménez, M.J., Riscos-Nú˜
nez, A., 2007.
A linea solu ion o Subse Sum p oblem wi h issue P sys ems wi h cell di ision.
In: Vol. 4527 o Lec u e No es in Compu e Science. Sp inge , Be lin/Heidelbe g,
pp. 170–179.
F isco, P., 2009. Compu ing wi h Cells: Ad ances in Memb ane Compu ing. Ox o d
Uni e si y P ess, Ox o d.
Gu ié ez-Na anjo, M.A., Pé ez-Jiménez, M.J., Rome o-Campe o, F.J., 2005. A linea
solu ion o subse sum p oblem by using memb ane c ea ion. In: Vol. 3561 o
Lec u e No es in Compu e Science. Sp inge , Be lin/Heidelbe g, pp. 258–267.
Ionescu, M., P˘
aun, Gh., Yokomo i, T., 2006. Spiking neu al P sys ems. Fund. In o m.
71 (2–3), 279–308.
Ma ín-Vide, C., Pazos, J., P˘
aun, Gh., Rod iguez-Pa on, A., 2003. Tissue P sys ems.
Theo . Compu . Sci. 296 (2), 295–326.
Papadimi iou, C.H., 1994. Compu a ional Complexi y. Addison-Wesley, Reading,
Mass.
P˘
aun, A., 2000. On P sys ems wi h ac i e memb anes. In: P oceedings o he Second
In e na ional Con e ence on Uncon en ional Models o Compu a ion, UMC’2K,
B ussels, Belgium, pp. 187–201.
P˘
aun, A., P˘
aun, Gh., 2002. The powe o communica ion: P sys ems wi h sym-
po /an ipo . New Gene . Compu . 20 (3), 295–305.
P˘
aun, Gh., 2000. Compu ing wi h memb anes. J. Compu . Sys . Sci. 61 (1), 108–143.
P˘
aun, Gh., 2001. P sys ems wi h ac i e memb anes: a acking NP-comple e p ob-
lems. J. Au o. Lang. Comb. 6, 75–90.
P˘
aun, Gh., Pazos, J., Pé ez-Jiménez, M.J., Rod íguez-Pa ón, A., 2005. Sympo /an ipo
P sys ems wi h h ee objec s a e uni e sal. Fund. In o m. 64, 1–4.
P˘
aun, Gh., Rozenbe g, G., Salomaa, A., 2010. The Ox o d Handbook o Memb ane
Compu ing. Ox o d Uni e si y P ess, Ox o d.
Pé ez-Jiménez, M.J., Rome o-Jiménez, A., Sancho-Capa ini, F., 2003. Complexi y
classes in models o cellula compu ing wi h memb anes. Na . Compu . 2 (3),
265–285.
Pé ez-Jiménez, M.J., Riscos-Nú˜
nez, A., 2004. A linea ime solu ion o he Knapsack
p oblem using P sys ems wi h ac i e memb anes. In: Vol. 2933 o Lec u e No es
in Compu e Science. Sp inge , Be lin/Heidelbe g, pp. 250–268.
Pé ez-Jiménez, M.J., Riscos-Nú˜
nez, A., 2005. Sol ing he Subse -Sum p oblem by
ac i e memb anes. New Gene . Compu 23, 367–384.
Pé ez-Jiménez, M.J., 2005. An app oach o compu a ional complexi y in mem-
b ane compu ing. In: Vol. 3365 o Lec u e No es in Compu e Science. Sp inge ,
Be lin/Heidelbe g, pp. 85–109.
Pé ez-Jiménez, M.J., Rome o-Jiménez, A., Sancho-Capa ini, F., 2006. A polynomial
complexi y class in P sys ems using memb ane di ision. J. Au o. Lang. Comb. 11
(4), 423–434.
Pé ez-Jiménez, M.J., Riscos-Nú˜
nez, A., Rius-Fon , M., Rome o-Campe o, F.J., 2013. A
polynomial al e na i e o unbounded en i onmen o issue P sys ems wi h
cell di ision. In . J. Compu . Ma h. 90 (4), 760–775.
Po eca, A.E., Mu phy, N., Pé ez-Jiménez, M.J., 2012. An op imal on ie o he
e ficiency o issue P sys ems wi h cell di ision. In: P oceedings o he Ten h
B ains o ming Week on Memb ane Compu ing, Volume II, Se illa, Spain, pp.
141–166.
Rozenbe g, G., Salomaa, A., 1997. Handbook o Fo mal Languages, ol. 3. Sp inge -
Ve lag, Be lin.