Monodi ec ional P Sys ems?
Albe o Lepo a i, Luca Manzoni, Gianca lo Mau i,
An onio E. Po eca, Claudio Zand on
Dipa imen o di In o ma ica, Sis emis ica e Comunicazione
Uni e si `a degli S udi di Milano-Bicocca
Viale Sa ca 336/14, 20126 Milano, I aly
{lepo a i,luca.manzoni,mau i,po eca,zand on}@disco.unimib.i
Summa y.
We in es iga e he in luence ha he low o in o ma ion in memb ane sys ems
has on hei compu a ional complexi y. In pa icula , we analyse he beha iou o P sys ems
wi h ac i e memb anes whe e communica ion only happens om a memb ane owa ds
i s pa en , and ne e in he opposi e di ec ion. We p o e ha hese “monodi ec ional
P sys ems” a e, when wo king in polynomial ime and unde s anda d complexi y- heo e ic
assump ions, much less powe ul han un es ic ed ones: indeed, hey cha ac e ise classes
o p oblems de ined by polynomial- ime Tu ing machines wi h
NP
o acles, a he han
he whole class PSPACE o p oblems sol able in polynomial space.
1 In oduc ion
P sys ems wi h ac i e memb anes wo king in polynomial ime a e known o be able
o sol e all
PSPACE
-comple e p oblems [
1
]; his exploi s memb ane s uc u es
o polynomial dep h and a bidi ec ional low o in o ma ion (in e ms o mo ing
objec s o changing cha ges), bo h om a pa en memb ane o i s child en, and
he in opposi e di ec ion.
When es ic ing he dep h o he memb ane s uc u es o a amily o P sys ems
o a cons an amoun , i is s ill possible o sol e p oblems in he coun ing hie -
a chy
CH
, de ined in e ms o polynomial- ime Tu ing machines wi h o acles o
coun ing p oblems [
4
]. In he p oo o his esul , i has been no iced ha send-in
communica ion ules o he o m
a
[ ]
α
h→
[
b
]
β
h
allow us o check whe he he amoun
o objec s loca ed in a memb ane exceeds a (possibly exponen ial) h eshold in
polynomial ime.
I is hen na u al o ask whe he ha ea u e is ac ually necessa y in o de o
ob ain he powe o coun ing in polynomial ime. In his pape we p o e (unde he
s anda d complexi y- heo e ic assump ion ha
PNP 6
=
P#P
) ha his is ac ually
?
This wo k was pa ially suppo ed by Uni e si `a degli S udi di Milano-Bicocca, FA 2013:
“Complessi `a compu azionale in modelli di calcolo bioispi a i: Sis emi a memb ane e
sis emi di eazioni”.
208 A. Lepo a i e al.
he case: P sys ems wi h monodi ec ional communica ion, whe e he in o ma ion
lows only owa ds he ou e mos memb ane, a e limi ed o
PNP
, he class o
p oblems e icien ly sol ed by Tu ing machines wi h
NP
o acles. This happens
e en when allowing polynomially deep memb ane s uc u es, a weak o m o non-
elemen a y memb ane di ision, o dissolu ion (which, in his case, u ns ou o be
as powe ul as weak non-elemen a y di ision). The
PNP
uppe bound is ac ually
eached when dissolu ion o weak non-elemen a y di ision a e allowed; i nei he is
a ailable, hen he compu a ion powe dec eases o
PNP
k
, whe e he que ies mus
all be ixed in ad ance, a he han asked adap i ely. Chap e 17 o Papadimi iou’s
book [
7
] p o ides mo e de ails on complexi y classes de ined in e ms o Tu ing
machines wi h NP o acles.
Fo an in oduc ion o P sys ems wi h ac i e memb anes (
AM
), we e e he
eade o he o iginal pape by Gh. P˘aun [
8
], supplemen ed by he de ini ions
o complexi y classes
PMCAM
( esp.,
PMC?
AM
) o p oblems sol ed by uni o m
( esp., semi-uni o m) amilies o con luen P sys ems in polynomial ime [
5
]. De-
ine
M
=
AM(−i,−n,+wn)
o be he class o monodi ec ional P sys ems wi h
ac i e memb anes, wi hou send-in ules; we also emo e he usual (“s ong”)
non-elemen a y di ision ules, o he o m
[ ]+
h1· · · [ ]+
hm[ ]−
hm+1 · · · [ ]−
hnα
h→[ ]δ
h1· · · [ ]δ
hmβ
h[ ]ζ
hm+1 · · · [ ]ζ
hnγ
h
since hey also p o ide a way o memb ane
h
o sha e in o ma ion wi h i s child en
by changing hei cha ge. We eplace hese ules by “weak” non-elemen a y di ision
ules [
11
] o he o m [
a
]
α
h→
[
b
]
β
h
[
c
]
γ
h
, which allow he c ea ion o complex memb ane
s uc u es (such as comple e bina y ees) wi hou exchanging in o ma ion wi h
he child en memb anes.
Le
M(−d)
,
M(−wn)
, and
M(−d,−wn)
deno e monodi ec ional P sys ems
wi hou dissolu ion, wi hou weak non-elemen a y di ision, and wi hou bo h kinds
o ules, espec i ely. Fo each class
D
o P sys ems, le
PMCD
and
PMC?
D
be he
classes o p oblems sol able by uni o m and semi-uni o m amilies o P sys ems o
class D. Then, he main esul s o his pape can be summa ised as ollows:
•
The whole class
PMC[?]
M
, as well as
PMC[?]
M(−d)
and
PMC[?]
M(−wn)
, a e equi a-
len o PNP. He e [?] deno es op ional semi-uni o mi y.
•The class PMC[?]
M(−d,−wn) is equi alen o PNP
k.
The es o he pape is s uc u ed as ollows: in Sec ion 2 we p o e some basic
limi a ions o monodi ec ional P sys ems; in Sec ion 3 we exploi hese esul s
o p o e uppe bounds o he complexi y classes o monodi ec ional P sys ems;
in Sec ion 4 we p o ide he co esponding lowe bounds by simula ing Tu ing
machines wi h
NP
o acles; in Sec ion 5 some esul s o he p eceding sec ions a e
imp o ed; inally, in Sec ion 6 we p esen some open p oblems and di ec ions o
u u e esea ch.
Monodi ec ional P Sys ems 209
2 P ope ies o monodi ec ional P sys ems
We begin by p o ing some p ope ies o monodi ec ional P sys ems ha show how
he lack o inbound communica ion subs an ially es ic s he ange o beha iou s
exhibi ed du ing he compu a ions.
De ini ion 1.
Le
Π
be a P sys em, and le
C
and
D
be con igu a ions o
Π
. We
say ha
C
is a es ic ion o
D
, in symbols
C D
, i he memb ane s uc u es o
he wo con igu a ions a e iden ical (i.e., hey ha e he same shape, labelling, and
cha ges) and each mul ise o objec s o
C
is a submul ise o ha loca ed in he
co esponding egion o D.
The ollowing p oposi ion shows ha , while a ecognise P sys em wo king in
ime
migh c ea e exponen ially many objec s pe egion du ing i s compu a ion,
only a polynomial amoun (wi h espec o
) o hem in each egion does ac ually
play a use ul ole i he sys em is monodi ec ional: indeed, he inal esul o he
compu a ion can be iden i ied by jus keeping ack o a numbe o objec s pe
egion equal o he numbe o s eps ye o be ca ied ou .
Lemma 1.
Le
Π
be a monodi ec ional ecognise P sys em, and le
C
= (
C0,...,C
),
wi h
≥
1, be a hal ing compu a ion o
Π
. Then, he e exis s a sequence o con igu-
a ions (D0,...,D )such ha
(i)
we ha e
Di Ci
o 0
≤i≤
, and each mul ise o
Di
has a mos
−i
objec s;
(ii)
o all
i<
he e exis s a con igu a ion
Ei+1
such ha
Ei+1
is eachable in
one s ep om Di(Di→ Ei+1 o b e i y) and Di+1 Ei+1;
(iii)
a send-ou ule o he o m [
a
]
α
h→
[ ]
β
hyes
( esp., [
a
]
α
h→
[ ]
β
hno
) is applied
o he ou e mos memb ane du ing he ansi ion s ep
D −1→ E
i and only
i Cis an accep ing ( esp., ejec ing) compu a ion.
P oo .
By induc ion on
. I
= 1, hen he en i onmen o
C1
con ains
yes
o
no
, which ha e been sen ou du ing he compu a ion s ep
C0→ C1
by a
ule [
a
]
α
h→
[ ]
β
hyes
o [
a
]
α
h→
[ ]
β
hno
. Le
D0 C0
be ob ained by keeping only he
objec s on he le -hand side o send-ou , dissolu ion, and di ision ules applied
du ing
C0→ C1
(we call hese ules “blocking”, since a mos one o hem can be
applied inside each memb ane a each s ep). A mos one objec pe egion is kep ,
gi en he lack o send-in ules. Le
D1 C1
be ob ained by dele ing all objec s.
Then:
(i)
we ha e
D0 C0
and
D1 C1
by cons uc ion, and all mul ise s o
D0
and
D1
ha e a mos 1 and exac ly 0 objec s, espec i ely;
(ii)
le he ansi ion
D0→ E1
be compu ed by applying all blocking ules applied
du ing he s ep
C0→ C1
, which a e all enabled by cons uc ion; hen
E1 C1
and, since D1 C1and D1con ains no objec s, necessa ily D1 E1;
(iii)
he compu a ion
C
is accep ing i and only i he ule [
a
]
α
h→
[ ]
β
hyes
is
applied om
C0
, and he la e is equi alen by cons uc ion o ha ule
being applicable om D0( he easoning is simila i Cis ejec ing).
210 A. Lepo a i e al.
This p o es he base case. Now le
C
= (
C−1,C0,...,C
) be a hal ing compu a ion
o leng h
+ 1. The sub-compu a ion (
C0,...,C
) is also hal ing, and by induc ion
hypo hesis he e exis s a sequence o con igu a ions (
D0,...,D
) sa is ying (i)–(iii).
Cons uc he con igu a ion
D−1
as ollows: i s o all, keep all objec s om
C−1
ha appea on he le -hand side o blocking ules applied du ing he compu a ion
s ep
C−1→ C0
; his equi es a mos one objec pe egion, and gua an ees ha
he memb ane s uc u e’s shape and cha ges can be upda ed co ec ly (i.e., he
same as C0and D0).
We mus also ensu e ha all objec s o
D0
can be gene a ed om
D−1
du ing
he ansi ion
D−1→ E0
. Once he blocking ules o be applied ha e been chosen,
any objec
a
loca ed inside a memb ane o
D0
can be aced back o a single objec
in
D−1
. Ei he
a
appea s on he igh -hand side o one o hose blocking ules,
o i appea s on he igh -hand side o an objec e olu ion ule applied in he
s ep
C−1→ C0
, o i does no appea explici ly in any ule applied in ha s ep; in
he la e case, i is ei he ca ied on unchanged om
D−1
(possibly om ano he
egion, i memb ane dissolu ion occu ed), o is c ea ed by duplica ing he con en
o a memb ane by applying a di ision ule ( igge ed by a di e en objec ). As a
consequence, a mos
objec s pe egion o
D−1
, possibly in conjunc ion wi h a
single objec pe egion in ol ed in blocking ules, su ice in o de o gene a e he
objec s pe egion o D0. As a consequence,
(i)
we ha e
D−1 C−1
by cons uc ion, and
D−1
con ains a mos
+ 1 objec s
pe egion;
(ii)
by applying all blocking ules and as many e olu ion ules as possible om
he compu a ion s ep
C−1→ C0
in
D−1
, we ob ain a con igu a ion
E0
wi h
he same memb ane s uc u e as
D0
and, as men ioned abo e, con aining all
objec s om D0(and possibly o he objec s gene a ed by e olu ion ules).
Since (iii) holds by induc ion hypo hesis, his comple es he p oo . u
No ice ha his lemma does no gi e us an e icien algo i hm o choosing
which objec s a e impo an o each s ep o he compu a ion; i only p o es ha
a small (i.e., polynomial-sized) mul ise pe egion exis s. Howe e , i is easy o
ind such an algo i hm by sligh ly elaxing he condi ions: ins ead o limi ing he
ca dinali y o he mul ise s o
−i
, we limi he numbe o occu ences o each
symbol o ha alue, and simply dele e he occu ences in excess sepa a ely o
each symbol. This gi es us he la ge ca dinali y bound
|Γ| ×
(
−i
) pe egion,
which is polynomial whene e he numbe o compu a ion s eps o he sys em is,
and s ill allows us o simula e he o e all beha iou o he P sys em.
Lemma 1 ails o P sys ems wi h send-in ules because some con igu a ions
whe e each mul ise is small none heless equi e a p e ious con igu a ion wi h a
egion con aining exponen ially many objec s. This is he case, o ins ance, o
P sys ems sol ing coun ing p oblems, whe e he numbe o assignmen s sa is ying a
Boolean o mula is checked agains a h eshold by means o send-in ules [
4
]. Those
assignmen s a e ep esen ed in he P sys em by a po en ially exponen ial numbe o
objec s loca ed in he same egion, which a e sen in o exponen ially many child en
Monodi ec ional P Sys ems 211
memb anes in pa allel (i.e., a mos one objec en e s each child memb ane), and
canno always be educed o a polynomial amoun wi hou changing he accep ing
beha iou o he P sys em.
Ano he p ope y o monodi ec ional P sys ems is he exis ence o compu a ions
whe e memb anes ha ing he same labels always ha e child en (and, ecu si ely, all
he descenden s) wi h he same con igu a ion. This p ope y will be use ul when
simula ing con luen ecognise monodi ec ional P sys ems in Sec ion 3.
Lemma 2.
Le
Π
be a monodi ec ional P sys em. Then he e exis s a compu a-
ion
C
= (
C0,...,C
)o
Π
whe e, in each con igu a ion
Ci
, he ollowing holds:
any wo subcon igu a ions
2
o
Ci
ha ing memb anes wi h he same label as oo s
a e iden ical, excep possibly o he mul ise and cha ge o he oo memb anes
hemsel es.
P oo .
By induc ion on
i
. The s a emen i ially holds o he ini ial con igu a ion
o Π, since he memb anes a e injec i ely labelled.
When a di ision ule is applied o a memb ane
h
, wo subcon igu a ions wi h
oo
h
a e c ea ed; his is he only way o gene a e mul iple memb anes sha ing
he same label. The wo esul ing subcon igu a ions may only di e wi h espec
o he con en s and cha ges o he oo memb anes, since he in e nal memb anes
ha e e ol ed be o e he di ision o
h
occu s ( ecall ha he ules a e applied, om
a logical s andpoin , in a bo om-up way [8]).
On he o he hand, i wo subcon igu a ions wi h iden ically labelled oo
memb anes al eady exis in a con igu a ion
Ci
, hen we can assume ha he
p ope y holds by induc ion hypo hesis. We can hen nonde e minis ically choose
which ules o apply in he subcon igu a ion ha ing he i s memb ane as oo ,
excluding he oo i sel ; since he o he subcon igu a ion is iden ical (excep
possibly o he oo ), he same mul ise o ules can also be applied o i , hus
p ese ing he p ope y in he nex con igu a ion o he sys em. u
While Lemma 2 somehow “comp esses” each le el o he con igu a ion o
monodi ec ional P sys ems, i does no , howe e , educe he numbe o dis inc
memb anes pe le el o a polynomial numbe . Indeed, he s anda d memb ane
compu ing echnique o gene a ing all (exponen ially many) possible assignmen s
o a se o a iables does no equi e send-in ules [
10
], and can be ca ied ou in
pa allel on all le els o he memb ane s uc u e.
Lemma 2 also ails o P sys ems wi h send-in ules. The eason is ha wo
iden ical subcon igu a ions can be made di e en by ha ing a single objec loca ed
immedia ely ou side, and nonde e minis ically sending i in o one o he oo
memb anes o he wo sub ees; he e olu ion o he wo b anches o he sys em
migh hen di e ge comple ely.
2
We de ine a subcon igu a ion o
Ci
as a sub ee (a oo node oge he wi h all i s
descenden s) o he memb ane s uc u e o
Ci
, including labels, mul ise s, and cha ges
o he memb anes.

212 A. Lepo a i e al.
3 Simula ion o monodi ec ional P sys ems
I is a well-known esul in memb ane compu ing ha P sys ems wi h ac i e
memb anes can be simula ed in polynomial ime by de e minis ic Tu ing machines
i no memb ane di ision ules a e allowed [
10
]. Mo e speci ically, he po ion o he
sys em ha is no subjec o memb ane di ision can be simula ed de e minis ically
wi h a polynomial slowdown, while he ou pu o he di iding memb anes can
be ob ained by que ying an app op ia e o acle. I was ecen ly p o ed ha , o
s anda d (bidi ec ional) P sys ems whe e only elemen a y memb anes can di ide,
an o acle o a #P unc ion is necessa y and su icien [5].
In wha ollows we p o e ha an
NP
-o acle is su icien o he simula ion
o monodi ec ional P sys ems. In pa icula , he o acle will sol e he ollowing
p oblem.
Lemma 3.
Gi en he ini ial con igu a ion o an elemen a y memb ane wi h label
h
o a monodi ec ional P sys em, an objec ype
a∈Γ
, and wo in ege s
k, ∈N
in
una y no a ion, i is
NP
-comple e o decide whe he he se o memb anes wi h
label
h
exis ing a ime
emi s ( ia send-ou o dissolu ion ules) a leas
k
copies
o objec aa ha ime s ep.
P oo .
The p oblem is
NP
-ha d, since one can simula e an a bi a y polynomial-
ime, nonde e minis ic Tu ing machine
M
by using a single memb ane wi h ele-
men a y di ision (wi hou using send-in ules) and ob ain he same esul as
M
by checking i he esul ing memb anes send ou a leas one (
k
= 1) “accep ance
objec ” a a speci ic ime s ep [4].
Con e sely, he p oblem can be sol ed by a nonde e minis ic, polynomial- ime
Tu ing machine
M
as ollows. Simula e
compu a ion s eps o he memb ane explic-
i ly, by keeping ack o i s cha ge and mul ise , as in any s anda d simula ion [
10
].
I he memb ane di ides, hen
M
keeps ack o all he esul ing memb anes, un il
he numbe exceeds
k
. I ha happens, hen
k
copies o he memb ane a e chosen
nonde e minis ically among hose being simula ed (which a e a mos 2
k
a e any
simula ed s ep, i all memb anes di ide), and he emaining ones a e disca ded.
Since he e is no incoming communica ion, any ins ance o he memb ane can
be simula ed co ec ly, as i s beha iou does no depend on he beha iou o i s
siblings. I one o he simula ed memb anes dissol es be o e
s eps, one o he
k
“slo s” is eleased and can be eused in case o a u he memb ane di ision.
A e ha ing simula ed
s eps as desc ibed, he machine
M
accep s i and only
i a leas
k
copies o
a
a e emi ed (sen ou , o eleased by dissolu ion) in he
las s ep by he memb anes being simula ed. A mos
k
memb anes need o be
simula ed in o de o check whe he a leas
k
copies o he objec a e emi ed
and, by exploi ing nonde e minism, we a e gua an eed ha he co ec subse
o memb anes is chosen by a leas one compu a ion o
M
. Since
k
and
a e
polynomial wi h espec o he size o he inpu , he esul ollows. u
Monodi ec ional P Sys ems 213
The alues o
and
k
a e gi en in una y since, o he wise, he numbe o s eps
o he numbe o memb anes o simula e could be exponen ial wi h espec o he
size o he inpu , and he p oblem would no be sol able in polynomial ime.
As a consequence o Lemma 3, monodi ec ional P sys ems wi hou non-
elemen a y di ision can be simula ed in polynomial ime wi h access o an
NP
o acle.
Theo em 1. PMC?
M(−wn) ⊆PNP.
P oo .
The ules applied o non-elemen a y memb anes can be simula ed di ec ly
in de e minis ic polynomial ime by a Tu ing machine
M
[
5
]; his includes he
ou e mos memb ane, which ul ima ely sends ou he esul objec . In o de o
upda e he con igu a ions o he non-elemen a y memb anes co ec ly, he objec s
emi ed om elemen a y memb anes (which po en ially di ide) ha e o be added
o hei mul ise s.
Suppose he P sys ems o he amily being simula ed wo k in polynomial
ime
p
(
n
). By Lemma 1, he inal esul o he compu a ion can be co ec ly
de e mined by keeping ack o a mos
p
(
n
) copies o each objec pe egion.
Hence, we can upda e he con igu a ions by using an o acle o he p oblem o
Lemma 3. A ime s ep
, we make mul iple que ies o each label
h
o an elemen a y
memb ane and o each objec ype
a∈Γ
: by pe o ming a bina y sea ch on
k
o e he ange [0
, p
(
n
)], we can ind he exac numbe o copies o
a
emi ed by
memb anes wi h label
h
a ime
, o disco e ha his numbe is a leas
p
(
n
)
(and, in ha case, we only add
p
(
n
) objec s o he mul ise ). This comple es he
p oo . u
Monodi ec ional P sys ems wi hou non-elemen a y di ision become weake i
dissolu ion is also disallowed: now a memb ane canno become elemen a y du ing
he compu a ion, and hus he e olu ion o each di iding memb ane is always
independen o he es o he sys em. This allows us o pe o m all que ies in
pa allel, a he han sequen ially (in an adap i e way).
Theo em 2. PMC?
M(−d,−wn) ⊆PNP
k.
P oo .
I dissolu ion ules a e no allowed, being elemen a y is a s a ic p ope y
o he memb anes, i.e., a memb ane is elemen a y o he whole compu a ion i
and only i i is elemen a y in he ini ial con igu a ion. By obse ing ha each
que y is comple ely independen o he o he s (i.e., each que y in ol es a di e en
memb ane, ime s ep and objec ) and also independen o he con igu a ions o he
non-di iding memb anes (due o he lack o send-in ules), we can pe o m hem
in pa allel e en be o e s a ing o simula e he P sys em. This p o es he inclusion
in PNP
k.u
Now conside monodi ec ional P sys ems wi h non-elemen a y memb ane di i-
sion. Fo his kind o sys ems, he beha iou o a di iding memb ane is, o cou se,
dependen on he beha iou o i s child en and, ecu si ely, o all i s descendan s.
214 A. Lepo a i e al.
In o de o simula e he beha iou o he child en by using o acles, we de ine a mo e
gene al que y p oblem, whe e we assume ha he beha iou o he descenden s o
he memb ane men ioned in he que y has al eady been es ablished.
Fi s o all, no ice ha he lack o send-in ules allows us o ex end he no ion
o ansi ion s ep
C → D
be ween con igu a ions o labelled sub o es s
3E
o
C
and
F
o
D
as
E → F
; he only di e ences om he s anda d de ini ion a e ha
E
is no necessa ily a single ee, and ha i s ou e mos memb anes may di ide and
dissol e.
De ini ion 2.
Le
Π
be a monodi ec ional P sys em, le
C
be a con igu a ion o
Π
,
and le
h∈Λ
be a memb ane label. A sub o es
S
o
C
is called a label-sub o es
induced by h, o h-sub o es o b e i y, i one o he ollowing condi ions hold:
• C
is he ini ial con igu a ion o
Π
, and
S
consis s o a single ee oo ed in he
(unique) memb ane h,
• C
is a possible con igu a ion o
Π
a ime
+ 1 wi h
C0→ C
, and he e exis s
an h-sub o es S0in C0such ha S0→ S.
The no ion o
h
-sub o es can be iewed as a gene alisa ion o he equi alence classes
o memb anes in P sys ems wi hou cha ges de ined by Mu phy and Woods [6].
Lemma 4.
Le
Π
be a monodi ec ional P sys em. Then he e exis s a compu a ion
o
Π
whe e, a each ime s ep and o each memb ane label
h∈Λ
, all
h
-sub o es s
a e iden ical.
P oo .
Mul iple
h
-sub o es s can only be c ea ed by di ision o an ances o o
h
; bu
hen, by Lemma 2, he e exis s a compu a ion o
Π
whe e he esul ing
h
-sub o es s
a e iden ical. u
Example 1.
Figu e 1 shows he e olu ion o he memb ane s uc u e o a monodi-
ec ional P sys em and i s label-sub o es s. The label-sub o es s in he ini ial
con igu a ion
C0
coincide wi h all downwa d-closed sub ees. In he compu a ion
s ep
C0→ C1
bo h
h2
and
h3
di ide; he di ision o he la e causes he duplica ion
o he
h3
- and
h4
-sub o es s (and, indi ec ly, o he
h5
-sub o es ); he di ision o
an ances o memb ane is he only way o ha e mo e han one label-sub o es . By
Lemma 4, we can always assume ha mul iple label-sub o es s induced by he same
label a e iden ical. In he compu a ion s ep
C1→ C2
, he igh mos memb ane
ha ing label
h2
and bo h ins ances o
h4
dissol e. No ice ha his does no cause
he disappea ance o he wo
h4
-sub o es s: in he gene al case, he memb anes
h4
migh con ain label-sub o es s induced by di e en labels, and we s ill need o e e
o hem as a single en i y ( he
h4
-sub o es ), wi hou he need o desc ibe he
in e nal s uc u e, e en when h4ceases o exis .
As can be obse ed om Figu e 1, a sub o es can be iden i ied as an
h
-sub o es
by checking whe he i can be gene a ed om he downwa d-closed sub ee oo ed
in hin he ini ial con igu a ion.
3
We de ine a sub o es
F0
o a o es
F
o be any subg aph such ha , whene e
F0
includes a e ex , i also includes all he descenden s o .
Monodi ec ional P Sys ems 215
h1
h2
h4
h5
h2
h4
h5
h1
h2
h3
h4
h5
h3
h3h3
h3
h1
h2
h3
h3h3
h3
h4
h5
h4
h5
C0C1
C2
Fig. 1.
E olu ion o a memb ane s uc u e and i s label-sub o es s, which a e enclosed
by dashed ec angles.
A compu a ion ha ensu es ha all
h
-sub o es s a e iden ical o all
h∈Λ
can be ob ained by imposing a o al o de ing (a p io i y) on he se o ules o
he P sys em, and applying inside each memb ane he ules wi h highe p io i y
whene e possible. In he ollowing, we assume ha a p io i y o de (e.g., he
lexicog aphic o de ) has been ixed; he e is no loss o gene ali y in doing ha ,
since we only ocus on con luen P sys ems in his pape . We de ine he mul ise o
objec s emi ed by a label-sub o es as he union o he mul ise s emi ed by i s
ou e mos memb anes.
Lemma 5.
Gi en he ini ial con igu a ion o a memb ane wi h label
h
o a monodi-
ec ional P sys em, an objec
a∈Γ
, wo in ege s
k, ∈N
in una y no a ion, and a
able
T
o he objec s emi ed du ing compu a ion s eps 1
, . . . ,
by he label-sub o es s
immedia ely con ained in
h
, i is
NP
-comple e o decide whe he each
h
-sub o es
emi s a leas kcopies o objec aa ime .
222 A. Lepo a i e al.
Theo em 4.
A de e minis ic polynomial- ime Tu ing machine which asks
p
(
n
)
que ies o an
NP
o acle on inpu s o leng h
n
can be simula ed by a uni o m amily
o monodi ec ional P sys ems o dep h
p
(
n
)wi hou non-elemen a y di ision ules.
P oo .
The amily o P sys ems
Π
=
{Πx
:
x∈ {
0
,
1
}?}
simula ing
M
on inpu
x
can be cons uc ed uni o mly in polynomial ime, since only he ini ial mul ise
depends on he ac ual s ing
x
, while he se o ules and he memb ane s uc u e
only depend on
|x|
. We only need o make su e ha he indices o he ape-objec s
a e la ge enough o ensu e ha bo h he ape o
M
and he ape o
M0
can be
ep esen ed a he same ime. u
Co olla y 1. PNP ⊆PMCM(−wn).u
Ins ead o using memb ane dissolu ion as in ule
(23)
, we can use he objec
ˆq0
!
o p oduce ⊕:
[ˆq0
!→ ⊕]α
h o α∈ {+,−} (26)
which ensu es ha he cha ge o
h
is posi i e ins ead o nega i e wo s eps la e .
The ape-objec s a e hen sen ou , one a a ime, by using he ollowing ules:
[1i]+
h→[ ]+
h1i o −(m−1) ≤i≤m−1 (27)
The ime
o he objec
˜q!,
has o be inc eased app op ia ely, in o de o ake
in o accoun he ime needed o send ou all he ape-objec s. Howe e , since
he memb ane whe e he simula ion o
M
is non-elemen a y a e he i s que y,
ule (20) is now a weak non-elemen a y di ision ule. As a consequence, we ha e:
Theo em 5.
A de e minis ic polynomial- ime Tu ing machine which asks
p
(
n
)
que ies o an
NP
o acle on inpu s o leng h
n
can be simula ed by a uni o m amily
o monodi ec ional P sys ems o dep h p(n)wi hou dissolu ion ules. u
Co olla y 2. PNP ⊆PMCM(−d).u
In o de o p o e he con e se o Theo em 2, we in oduce an auxilia y com-
plexi y class (a a ian o he class o op imisa ion p oblems Op P [3]).
De ini ion 3.
De ine
O P
o be he class o unc ions
:{
0
,
1
}?→ {
0
,
1
}?
ha ing a
polynomial- ime nonde e minis ic Tu ing machine
M
such ha , o all
x∈ {
0
,
1
}?
,
we ha e
(
x
) =
WM
(
x
), whe e
M
(
x
)deno es he se o possible ou pu s ings
o
M
on inpu
x
, and
W
deno es bi wise disjunc ion o s ings; he e we assume
ha he bi wise disjunc ion o s ings o di e en leng hs is pe o med by padding
he sho es ones wi h ze os.
The pu pose o he class
O P
is o cap u e a polynomial numbe o pa allel
NP
que ies wi h a single que y o a unc ion o e bina y s ings.
P oposi ion 1. PNP
k=PO P[1].

Monodi ec ional P Sys ems 223
P oo .
A polynomial numbe o pa allel que ies
y1, . . . , ym
o an o acle o
L∈NP
can be eplaced by a single que y o an o acle o he unc ion
(
y1, . . . , ym
) =
z1· · · zm
, whe e
zi
= 1 i and only i
yi∈L
. Le
M
be an
NP
machine decid-
ing
L
, and le
M0
be he ollowing nonde e minis ic machine: on inpu
y1, . . . , ym
simula e
M
on each
yi
and eco d he co esponding ou pu bi
zi
; inally, ou -
pu
z1· · · zm
. Fo all 1
≤i≤m
, i
yi
is accep ed by he o acle, hen he e exis s a
compu a ion o
M0
such ha
zi
= 1: hus, by aking he bi wise disjunc ion o all
possible ou pu s ings o
M0
, we ob ain he
i
- h bi o
(
y1, . . . , ym
); his p o es
ha
∈O P
. No ice ha his p oo equi es he que y s ings
y1, . . . , ym
o be
ixed in ad ance, i.e., he que ies canno be pe o med adap i ely.
Vice e sa, a single que y o an o acle o
∈O P
wi h que y s ing
y
can be eplaced by he ollowing polynomial numbe o pa allel que ies, one o
each 1
≤i≤ |
(
y
)
|
: “is he
i
- h bi o
(
y
) a 1?”. These que ies a e in
NP
,
since hey can be answe ed by simula ing an
O P
machine
M
o
and selec ing
only i s
i
- h ou pu bi ; he answe will be posi i e i and only i he e exis s a
compu a ion o
M
ha ing a 1 as he
i
- h ou pu bi , which (by de ini ion o
O P
)
is equi alen o he i- h bi o (y) being 1. u
Simula ing an
O P
que y by means o a P sys em is comple ely analogous o
simula ing an
NP
que y, excep ha , ins ead o a single ou pu bi , we ha e a
polynomial numbe o hem. These bina y s ings a e au oma ically combined by
bi wise disjunc ion when he ape-objec s a e sen ou o he memb ane simula ing
he nonde e minis ic Tu ing machine. Fu he mo e, since a single
O P
que y su ices
o cap u e PNP
k, we ob ain he ollowing esul s:
Theo em 6.
A de e minis ic polynomial- ime Tu ing machine which asks a poly-
nomial numbe o pa allel que ies o an
NP
o acle on inpu s o leng h
n
can be
simula ed by a uni o m amily o monodi ec ional P sys ems o dep h 1 wi hou
dissolu ion (and, necessa ily, wi hou non-elemen a y di ision). u
Co olla y 3. PNP
k⊆PMCM(−d,−wn).u
5 Fu he esul s
The dep h o he P sys ems o Theo ems 4 and 5 can be asymp o ically educed
by exploi ing he equi alence o a loga i hmic numbe o adap i e que ies and a
polynomial numbe o pa allel que ies [
7
, Theo em 17.7], o mally
PNP
k
=
PNP[log n]
.
Suppose a de e minis ic polynomial- ime Tu ing machine pe o ms
p
(
n
) sequen ial
NP
que ies, and di ide hese que ies in o
Θ
(
p
(
n
)
/log n
) blocks o
Θ
(
log n
) que ies.
Each block can hen be eplaced by a polynomial numbe o pa allel
NP
que ies
o , by P oposi ion 1, by a single
O P
que y. Hence,
p
(
n
) sequen ial
NP
que ies
can be simula ed by
Θ
(
p
(
n
)
/log n
) sequen ial
O P
que ies, and each o he la e
can be simula ed by one le el o dep h in a P sys em:
224 A. Lepo a i e al.
Co olla y 4.
A de e minis ic polynomial- ime Tu ing machine which asks
p
(
n
)
que ies o an
NP
o acle on inpu s o leng h
n
can be simula ed by a uni o m amily o
monodi ec ional P sys ems o dep h
Θ
(
p
(
n
)
/log n
)wi hou non-elemen a y di ision
ules ( esp., wi hou di ision ules). u
Theo em 3 can be sha pened by making he in a-le el que y pa allelism explici
wi h O P que ies:
Co olla y 5.
Le
Π
be a amily o semi-uni o m polynomial- ime monodi ec ional
P sys ems o dep h
(
n
). Then
Π
can be simula ed by a polynomial- ime de e min-
is ic Tu ing machine wi h (n)que ies o an O P o acle. u
We can also p o e ha monodi ec ional amilies o P sys ems o any con-
s an dep h, e en wi h dissolu ion and non-elemen a y di ision ules (in sym-
bols
M(O(1))
), a e always equi alen o amilies o dep h one wi hou dissolu ion
and wi hou non-elemen a y di ision (in symbols
M(1,−d,−wn)
), and hus only
able o simula e pa allel NP que ies.
Theo em 7. PMC[?]
M(O(1)) =PMC[?]
M(1,−d,−wn) =PNP
k.
P oo .
By Theo em 6, we al eady know ha
PNP
k⊆PMCM(O(1))
, e en when
limi ed o dep h 1; he inclusion
PMCM(O(1)) ⊆PMC?
M(O(1))
holds by de ini ion.
The inclusion
PMC?
M(O(1)) ⊆PNP
k
can be p o ed as ollows. By Theo em 3, a
amily o P sys ems o cons an dep h
k
can be simula ed in polynomial ime by
asking
k
se s (one pe le el) o
p
(
n
) pa allel que ies, o some polynomial
p
. Each
se o
p
(
n
) pa allel que ies can be con e ed in o
Θ
(
log n
) sequen ial que ies [
7
,
Theo em 17.7], o a o al o
k×Θ
(
log n
) sequen ial que ies. These can be con e ed
back in o a polynomial numbe o pa allel que ies. u
Finally, obse e ha Theo em 3 also i ially holds o monodi ec ional P sys-
ems wi hou cha ges. This implies a be e uppe bound han p e iously known [
5
]
o a monodi ec ional a ian o he P conjec u e [
9
, P oblem F], which s a es ha
P sys ems wi hou cha ges and wi hou non-elemen a y di ision cha ac e ise P.
6 Conclusions
In his pape we con i med he impo ance o he di ec ion o he in o ma ion low
in P sys ems wi h ac i e memb anes wi h espec o hei compu ing powe . Indeed,
when wo king in polynomial ime and using only ou wa d-bound communica ion,
he co esponding complexi y class dec eases om
PSPACE
o
PNP
, o om
P#P
o
PNP
k
when non-elemen a y di ision and dissolu ion ules a e disallowed. I is
in e es ing o no ice ha , unlike wi h o he es ic ions such as emo ing memb ane
di ision [
10
] o cha ges and dissolu ion [
2
], he esul ing P sys ems a e s ill mo e
powe ul han P(unless, o cou se, P=NP).
Monodi ec ional P Sys ems 225
The ole o s ong non-elemen a y di ision (which is eplaced in his pape
by weak non-elemen a y di ision) in he absence o send-in ules is s ill unclea .
E en i i p o ides a way o con ey in o ma ion om a pa en memb ane o i s
child en, we do no know whe he his is su icien o al oge he eplace send-in
communica ion while main aining a polynomial un- ime.
Finally, i would be in e es ing o in es iga e monodi ec ional P sys ems whe e
he in o ma ion low is e e sed, i.e., send-ou communica ion and dissolu ion ules
(as well as s ong non-elemen a y di ision ules) a e disallowed. A i s issue o
o e come is choosing an app op ia e accep ance condi ion o he P sys ems, o
eplace sending ou
yes
o
no
om he ou e mos memb ane. The accep ance
condi ion mos simila “in spi i ” o he o iginal one is p obably accep ing ( esp.,
ejec ing) by ha ing a leas one
yes
( esp.,
no
) objec appea , ei he anywhe e in
he sys em, o inside a dis inguished (and possibly di iding) memb ane, du ing he
las compu a ion s ep; we also add he es ic ion ha
yes
and
no
can ne e appea
oge he , since gi ing he p io i y o one o hem would allow us o sol e
NP
-
comple e (o
coNP
-comple e) p oblems “ o ee”. Such monodi ec ional P sys ems
appea o be e y weak when wo king in polynomial ime; indeed, e en hough
exponen ially many memb anes can s ill be c ea ed by di ision, hey can ne e
communica e. Is
P
ac ually an uppe bound o he class o p oblems hey can
sol e?
Re e ences
1.
Alhazo , A., Ma ´ın-Vide, C., Pan, L.: Sol ing a PSPACE-comple e p oblem by
ecognizing P sys ems wi h es ic ed ac i e memb anes. Fundamen a In o ma icae
58(2), 67–77 (2003)
2.
Gu i´e ez-Na anjo, M.A., P´e ez-Jim´enez, M.J., Riscos-Nu˜nez, A., Rome o-Campe o,
F.J.: Compu a ional e iciency o dissolu ion ules in memb ane sys ems. In e na ional
Jou nal o Compu e Ma hema ics 83(7), 593–611 (2006)
3.
K en el, M.W.: The complexi y o op imiza ion p oblems. Jou nal o Compu e and
Sys em Sciences 36, 490–509 (1988)
4.
Lepo a i, A., Manzoni, L., Mau i, G., Po eca, A.E., Zand on, C.: Memb ane di ision,
o acles, and he coun ing hie a chy. Fundamen a In o ma icae (2015), in p ess
5.
Lepo a i, A., Manzoni, L., Mau i, G., Po eca, A.E., Zand on, C.: Simula ing elemen-
a y ac i e memb anes, wi h an applica ion o he P conjec u e. In: Gheo ghe, M.,
Rozenbe g, G., Sos´ık, P., Zand on, C. (eds.) Memb ane Compu ing, 15 h In e na ional
Con e ence, CMC 2014, Lec u e No es in Compu e Science, ol. 8961, pp. 284–299.
Sp inge (2015)
6.
Mu phy, N., Woods, D.: Ac i e memb ane sys ems wi hou cha ges and using only
symme ic elemen a y di ision cha ac e ise P. In: Ele he akis, G., Ke alas, P., P˘aun,
Gh., Rozenbe g, G., Salomaa, A. (eds.) Memb ane Compu ing, 8 h In e na ional
Wo kshop, WMC 2007. Lec u e No es in Compu e Science, ol. 4860, pp. 367–384
(2007)
7. Papadimi iou, C.H.: Compu a ional Complexi y. Addison-Wesley (1993)
8.
P˘aun, Gh.: P sys ems wi h ac i e memb anes: A acking NP-comple e p oblems.
Jou nal o Au oma a, Languages and Combina o ics 6(1), 75–90 (2001)
226 A. Lepo a i e al.
9.
P˘aun, Gh.: Fu he wen y six open p oblems in memb ane compu ing. In: Gu ´ıe ez-
Na anjo, M.A., Riscos-Nu˜nez, A., Rome o-Campe o, F.J., Sbu lan, D. (eds.) P oceed-
ings o he Thi d B ains o ming Week on Memb ane Compu ing. pp. 249–262. F´enix
Edi o a (2005)
10.
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, C.S., Dinneen, M.J. (eds.) Uncon-
en ional Models o Compu a ion, UMC’2K, P oceedings o he Second In e na ional
Con e ence, pp. 289–301. Sp inge (2001)
11.
Zand on, C., Lepo a i, A., Fe e i, C., Mau i, G., P´e ez-Jim´enez, M.J.: On he
compu a ional e iciency o pola iza ionless ecognize P sys ems wi h s ong di ision
and dissolu ion. Fundamen a In o ma icae 87, 79–91 (2008)