P SYSTEMS WITH INPUT IN BINARY FORM
ALBERTO LEPORATI∗
CLAUDIO ZANDRON†
Dipa imen o di In o ma ica, Sis emis ica e Comunicazione
Uni e si `a degli S udi di Milano – Bicocca
Via Bicocca degli A cimboldi 8, 20126 Milano, I aly
and
MIGUEL A. GUTI´
ERREZ-NARANJO‡
Resea ch G oup on Na u al Compu ing
Depa men o Compu e Science and A i icial In elligence
Se illa Uni e si y
A da Reina Me cedes s/n, 41012 Se illa, Spain
Recei ed ( ecei ed da e)
Re ised ( e ised da e)
Communica ed by Edi o ’s name
ABSTRACT
Cu en P sys ems which sol e NP–comple e nume ical p oblems ep esen ins ances
in una y no a ion. In classical complexi y heo y, based upon Tu ing machines, swi ching
om bina y o una y encoded ins ances gene ally co esponds o simpli y he p oblem.
In his pape we show ha his does no occu when wo king wi h P sys ems. Namely,
we p opose a simple me hod o encode bina y numbe s using mul ise s, and a amily o
P sys ems which ans o ms such mul ise s in o he usual una y no a ion.a
Keywo ds: Memb ane Compu ing; P sys ems; Bina y da a; Pa i ion
1. In oduc ion
P sys ems (also called memb ane sys ems) we e in oduced in [?] as a new class o
dis ibu ed and pa allel compu ing de ices, inspi ed by he s uc u e and unc ion-
ing o li ing cells. The basic model consis s o a hie a chical s uc u e composed by
se e al memb anes, embedded in o a main memb ane called he skin. Memb anes
di ide he Euclidean space in o egions, ha con ain some objec s ( ep esen ed by
symbols o an alphabe ) and e olu ion ules. Using hese ules, he objec s may
e ol e and/o mo e om a egion o a neighbo ing one. The ules a e applied in a
nonde e minis ic and maximally pa allel way: all he objec s ha may e ol e a e
∗lep[email p o ec ed] .
†[email p o ec ed].
‡[email p o ec ed]
1
o ced o e ol e. A compu a ion s a s om an ini ial con igu a ion o he sys em
and e mina es when no e olu ion ule can be applied. The esul o a compu a ion
is he mul ise o objec s con ained in o an ou pu memb ane o emi ed o he
en i onmen om he skin o he sys em.
In wha ollows we assume he eade is al eady amilia wi h he basic no ions
and he e minology unde lying P sys emsb.
Many P sys ems which sol e NP–comple e decision p oblems ha e appea ed in
he li e a u e du ing he las ew yea s. Bo h in he ield o nume ical p oblems,
ha is, p oblems whose ins ances consis o se s o sequences o in ege numbe s
(see o example Subse Sum [?], Knapsack [?], Bin Packing [?] o Pa i ion [?]
p oblems) o non-nume ical p oblems as SAT [?,?] o QSAT [?].
I is well known [?,?] ha he di icul y o such nume ical p oblems is ied o
he magni ude o he numbe s which appea in o he ins ance. Fo example, le us
conside he Pa i ion p oblem, which can be s a ed as ollows:
P oblem 1.1 Name:Pa i ion.
•Ins ance: a se A={a1, a2,...,an}o posi i e in ege numbe s
•Ques ion: is he e a subse A′⊆Asuch ha P
a′∈A′
a′=P
a∈A A′
a?
The ollowing algo i hm sol es he p oblem using he well known Dynamic P og am-
ming echnique [?]. In pa icula , he algo i hm e u ns 1 on posi i e ins ances, and
0 on nega i e ins ances.
Pa i ion({a1, a2,...,an})
s←Pn
i=1 ai
i smod 2 = 1 hen e u n 0
o j←1 o s/2
do M[1, j]←0
M[1,0] ←M[1, a1]←1
o i←2 o n
do o j←0 o s/2
do M[i, j]←M[i−1, j]
i j≥aiand M[i−1, j −ai]> M[i, j]
hen M[i, j]←M[i−1, j −ai]
e u n M[n, s/2]
Fi s o all, he algo i hm compu es he sum so all elemen s in he ins ance. I s
is odd hen he ins ance is ce ainly nega i e, and hus he algo i hm e u ns 0. I
sis e en hen he algo i hm checks o he exis ence o a subse A′⊆Asuch ha
Pa′∈A′a′=s
2. In o de o look o A′, he algo i hm uses a n×(s
2+ 1) ma ix
Mwhose en ies a e om {0,1}. I ills he ma ix by ows, s a ing om he i s
ow. Each ow is illed om le o igh . The en y M[i, j] is illed wi h 1 i and
bA layman-o ien ed in oduc ion can be ound in [?]; a o mal desc ip ion in [?] and he la es
in o ma ion abou P sys ems can be ound on [?].
2
only i he e exis s a subse o {a1, a2,...,ai}whose elemen s sum up o j. The
gi en ins ance o Pa i ion is hus a posi i e ins ance i and only i M[n, s
2] = 1
a he end o he execu ion.
Since each en y is conside ed exac ly once o de e mine i s alue, he ime
complexi y o he algo i hm is p opo ional o n(s
2+ 1) = Θ(ns). This means ha
he di icul y o he p oblem depends on he alue o s, ha is, on he magni ude
o he alues in A. In ac , le us deno e by K he maximum elemen o A. I
Kis polynomially bounded w. . . n hen also s=Pn
i=1 ai≤Kn is polynomially
bounded w. . . n, and hus he abo e algo i hm wo ks in polynomial ime. On he
o he hand, i Kis exponen ial w. . . n, say K= 2n, hen also sis exponen ial
and he abo e algo i hm wo ks in exponen ial ime and space. This beha io is
usually e e ed o in he li e a u e by elling ha he Pa i ion p oblem is a
pseudo–polynomial NP–comple e p oblem.
The ac ha in gene al he abo e algo i hm is no a polynomial ime algo i hm
o Pa i ion can be immedia ely unde s ood by compa ing i s ime complexi y
wi h he ins ance size. The usual size o he ins ances o Pa i ion is Θ(nlog K)
(also O(nlog s) in [?, page 91]), since o conciseness e e y “ easonable” encoding
is assumed o ep esen each elemen o Ausing a s ing whose leng h is O(log K).
He e all loga i hms a e aken wi h base 2. S a ed di e en ly, he size o he ins ance
is usually conside ed o be he numbe o bi s which mus be used o ep esen in
bina y all he in ege numbe s which occu in A. I we would ep esen such numbe s
using he una y no a ion, hen he size o he ins ance would be Θ(nK). Bu in his
case we could w i e a p og am which i s con e s he ins ance in bina y o m and
hen uses he abo e algo i hm o sol e he p oblem in polynomial ime wi h espec
o he new ins ance size. We can hus conclude ha he di icul y o a nume ical
NP–comple e p oblem depends also on he measu e o he ins ance size we adop .
The ac ha he di icul y o a p oblem gene ally depends upon how we measu e
he ins ance size is e en mo e appa en i we conside he Fac o iza ion p oblem:
P oblem 1.2 Name:Fac o iza ion.
•Ins ance: a posi i e in ege numbe nwhich is he p oduc o wo p ime
numbe s pand q
•Ou pu :p
This p oblem is gene ally conside ed in ac able, which means ha no polynomial
ime algo i hm is known ha sol es i on e e y ins ance. The conjec u ed in-
ac abili y o his p oblem is o en exploi ed in C yp og aphy: a no able example
is he RSA c yp osys em [?]. He e he na u al ins ance size o he p oblem is
Θ(log n), he numbe o bi s which a e needed o ep esen nin bina y o m. Also
o his p oblem, i we le he ins ance size be Θ(n) hen he i ial algo i hm which
ies o di ide nby e e y numbe comp ised be ween 1 and √nis a polynomial
ime algo i hm which sol es he Fac o iza ion p oblem.
Fo hese easons we belie e ha i is impo an o show ha P sys ems which
sol e NP–comple e nume ical p oblems do no ake hei powe om he ac ha
he ins ances a e ep esen ed in una y no a ion. Hence in his pape we i s p opose
3
a simple me hod o ep esen posi i e in ege numbe s in bina y no a ion using
mul ise s o objec s. Then, we p opose a amily o P sys ems which ans o ms his
bina y encoding in o he una y no a ion used in [?,?,?,?].
The pape is o ganized as ollows. In sec ion 2 we in oduce ou encoding o
bina y numbe s using mul ise s. In sec ion 3 we p opose a amily o simple P
sys ems which can be used o ans o m a gi en posi i e in ege numbe om such
encoding o una y no a ion. Sec ion 4 concludes he pape and gi es some di ec ions
o u u e esea ch.
2. Encoding bina y numbe s using mul ise s
Fi s o all le us show how a gi en posi i e in ege numbe xcan be ep esen ed
in bina y no a ion using a mul ise . Le xn, xn−1,...,x1be he bina y ep esen a-
ion o x, so ha x=Pn
i=1 xi2i−1. We use he objec s om he ollowing alphabe :
An={hb, ji|b∈ {0,1}, j ∈ {1,2,...,n}} (1)
Objec hb, jiis used o ep esen bi bin o posi ion jin he bina y encoding o an
in ege numbe . Hence, o ep esen he abo e numbe xwe will use he ollowing
mul ise (ac ually, a se ) o objec s:
hxn, ni,hxn−1, n −1i,...,hx1,1i
Le us ema k ha he alphabe Adepends on he leng h o he bina y ep e-
sen a ion o he numbe x, i.e., wi h he alphabe Anwe can ep esen om 1 o
2n−1.
On he o he hand, he una y ep esen a ion o xis ob ained by choosing a
symbol om an alphabe , say he symbol a om alphabe A′, and pu ing in o he
mul ise xcopies o such symbol: ax. Hence, una y no a ion is exponen ially longe
han bina y no a ion. Ou ans o ma ion hus sol es ano he p oblem aised by
he solu ions exposed in [?,?,?,?]: in o de o p o ide he inpu alues o he
P sys ems, we should inse in o such sys ems an exponen ial (wi h espec o he
ins ance size) numbe o objec s. This means ha an exponen ial amoun o wo k
o p epa e he sys em is equi ed.
Wo king wi h bina y encoded numbe s, ins ead, allows one o p epa e he sys em
by inse ing a polynomially bounded numbe o objec s.
3. Con e ing om bina y o una y no a ion
In his sec ion we p opose a amily o simple P sys ems which allows o con e
a gi en posi i e in ege numbe x, exp essed in bina y no a ion as exposed in he
p e ious sec ion, o he usual una y no a ion.
The objec s used by he P sys ems o m a subse o alphabe Ao equa ion (??).
Namely, in o de o ep esen xin bina y no a ion we will use only he objec s which
co espond o he bi s o xwhich a e equal o 1. Fo example, i x= 25 hen i s
bina y ep esen a ion is 11001, and we will use he objec s h1,5i,h1,4i, and h1,1i
o ep esen i . Since he i s elemen in he pai s o Aused is always equal o 1,
4
we can be mo e concise by omi ing i . Once omi ed he i s elemen o he pai ,
also angula pa en hesis a e supe lous.
The amily o P sys ems which pe o ms he ans o ma ion is o mally de ined
as ollows:
Π(n) = (A(n), µ, w, R(n), iin, iou )
whe e:
•A(n) = {1,2,...,n}∪{a}is he alphabe ;
•µ= [ ]skin is he memb ane s uc u e consis ing o he skin only;
•w=∅is he mul ise o objec s ini ially p esen in egion 1;
•R(n) is he ollowing se o e olu ion ules associa ed wi h egion 1:
[j→(j−1)2]skin o all j∈ {2,3,...,n}
[1 →a]skin
•iin =skin speci ies he inpu memb ane o Π;
•iou =skin speci ies he ou pu memb ane o Π.
The seman ics o he ules is he usual o e olu ion ules. All hey a e applied in
a maximal pa allel mode. The numbe o cellula s eps o he P sys em is bounded
by nand he compu a ion hal s when no mo e ules can be applied. When his
happens, he mul ise placed in he ou pu memb ane ( he only one memb ane) is
he ou pu o he compu a ion.
Compu a ions p oceed as ollows. The objec s which deno e he posi ions o 1’s
in he bina y ep esen a ion o xa e ini ially pu in o he egion enclosed by he
skin. Then he compu a ion s a s, and he ules om Ra e applied. I is easily
seen ha he p esence o objec j, wi h j∈ {1,2,...,n}, will p oduce 2j−1copies o
objec a. Hence a he end o he compu a ion, when no mo e ules om Rcan be
applied, he skin will con ain xcopies o objec a, ha is, he una y ep esen a ion
o x.
We conclude his sec ion wi h an example o compu a ion o he abo e P sys ems.
Le us conside again he alue x= 25; as p e iously said, i will be ep esen ed
by means o objec s 5, 4, and 1 (each in a unique copy). A he i s s ep o
compu a ion, we apply in pa allel he ules 1 →a, 4 →3,3 and 5 →4,4, ob aining
he mul ise a, 3,3,4,4.
Then, we apply in pa allel he ule 3 →2,2 on each copy o he symbol 3, hus
ob aining ou copies o he symbol 2, and he ule 4 →3,3 on each copy o he
symbol 4, hus ob aining ou copies o he symbol 3. The mul ise we ob ain a e
he second s ep o compu a ion will be a, 2,2,2,2,3,3,3,3.
Hence, we apply he ules 2 →1,1 and 3 →2,2 ob aining a, 18,28. By means o
he ules 1 →aand 2 →1,1 we hen ob ain he mul ise a9,116 and inally, applying
again 1 →awe ob ain he mul ise a25 which is exac ly he una y codi ica ion o
he ini ially bina y coded numbe .
5

F om he p e ious de ini ion and example, i is easy o see ha he ca dinali y
o he alphabe and he numbe o compu a ion s eps a e linea wi h espec o he
inpu size.
4. Composi ion o P sys ems
In he p e ious sec ion, a me hod o con e ing na u al numbe om bina y in o
una y no a ion has been desc ibed. In ui i ely, such a P sys em could be composed
wi h a P sys em which sol es an ins ance o a p oblem wi h inpu in una y o m
and o ge a new P sys em which sol es he same p oblem wi h inpu in bina y
o m.
The o maliza ion o such in ui ion has se e al echnical de ails and, o he bes
o ou knowledge, he composi ion o P sys ems has no been de ined.
In his sec ion we p esen a de ini ion o composing P sys ems which i in o
ou pu poses. The gene al de ini ion and he s udy o i s p ope ies lies ou o he
scope o his pape . Fi s we de ine a join o wo P sys ems
Ajoin P1◦P2o P sys ems P1and P2is a new P sys em whe e he skin
memb ane o P2is iden i ied o an elemen a y memb ane o P1. In his way we
ob ain a new labelled memb ane s uc u e. Each labelled memb ane keeps i s ini ial
mul ise and se o ules. In he ini ial con igu a ion, he new memb ane ob ained
by iden i ica ion, he ini ial mul ise and se o ules a e he union o he mul ise s
and se s o ules o he iden i ied memb anes. Nex we gi e a o mal de ini ion.
De ini ion 1 Le P1= (O1, H1, EC1, µ1, w1
1,...,w1
m1, R1)and
P2= (O2, H2, EC2, µ2, w2
1, . . . , w2
m2, R2)be wo P sys ems whe e: m1, m2≥1a e
he ini ial deg ees o he sys ems; O1and O2a e he alphabe s o objec s; H1and H2
a e wo disjoin ini e se o labels o memb anes; EC1=EC2a e he ini e se s
o elec ical cha ges o memb anes; µ1and µ2a e he memb ane s uc u es con-
sis ing ( esp.) o m1and m2memb anes labelled (no necessa ily in a one- o-one
manne ) wi h elemen s o H1and H2;wi
1,...,wi
ma e s ings o e Oi, desc ibing
he mul ise s o objec s placed in he mi egions o µi( o i=1,2); R1and R2a e
he ini e se s o ules associa ed o P1and P2.
Le i1be he label o an elemen a y memb ane o P1and s2 he label o he skin
memb ane o P2. And le µbe he memb ane s uc u e ob ained by iden i ying i1
wi h s2. Since he none i1is a lea e in µ1and he node s2is he oo o µ2 he new
g aph is also a memb ane s uc u e. We keep he same label o all memb anes and
label he join memb anes by α.
We de ine a join P1◦P2as a P sys em
P1◦P2= (O, H, EC, µ, w1,...,wm, R)
whe e m=m1+m2−1is he ini ial deg ee o he sys ems; O=O1∪O2is he
alphabe o objec s; H= (H1−{i1})∪(H2−{s2})∪{α}is he ini e se o labels o
memb anes; EC =EC1=EC2is he ini e se o elec ical cha ges o memb anes;
µand is he memb ane s uc u e labelled wi h elemen s o H;w1,...,wka e s ings
o e O, desc ibing he mul ise s o objec s placed in he m egions o ; R=R1∪R2
is he ini e se o ules.
6
No e ha gi en wo P sys ems wi h he same se o elec ical cha ges (which can
be emp y) he e exis s se e al posibili ies o ge ing a join : One o each elemen a y
memb ane o P1. Nex we de ine he composi ion o wo P sys ems. In o de o
de ine such composi ion we need wo P sys ems wi h inpu and ou pu .
De ini ion 2 Le P1and P2be wo P sys ems wi h inpu and ou pu such ha :
•The inpu memb ane o P1is an elemen a y memb ane. We will deno e by i1
he label o such memb ane.
•The ou pu memb ane o P2is he skin memb ane. We will deno e by s2 he
label o such memb ane.
The composi ion P1◦P2is he join ob ained by iden i ying i1wi h s2.
No e ha i P2sends he ou pu o he en i onmen , we can conside a new ex e nal
memb ane su ounding he whole P sys em which becomes he new skin. Wi h his
new skin we can conside he composi ion wi h ano he P sys em.
5. A Case S udy
In his sec ion we desc ibe wo amiles o P sys ems ΠBans Ppa :
•The amily ΠB={PB(n, d) : n, d ∈N}con e s mul ise s o na u al num-
be s om bina y in o una y no a ion. The P sys em PB(n, d) depends on he
numbe o elemen s ha we wan o con e and on d, whe e dis de ined by
d=En [log2(max A)] + 1 (2)
whe e Ais he se o numbe s o con e .
•The amily Πpa ={Ppa (n) : n, ∈N}is a uni o m amily which sol es he
NP-p oblem Pa i ion. I is based on he solu ion p esen ed in ... bu wi h
small changes. Each P sys em Ppa (n) sol es all ins ances o he p oblem
wi h nelemen s. The solu ion is ob ained in polynomial ime on nand he
inpu has o be p o ided in una y o m.
Bo h amilies a e designed wi h inpu and ou pu and i has sense o conside he
composi ion o P sys ems o bo h amilies. We ob ain he ollowing amily:
Π = {Ppa (n)◦PB(n, d) : n, d ∈N}
whe e each P sys em P(n, d) = Ppa (n)◦PB(n, d) is a cellula de ice which sol es
all he ins ances o he Pa i ion p oblem wi h he same pa ame e s nand d.
5.1. The amily ΠB
The P sys ems o his amily a e adap ed om he model p esen ed in he sec ion
??. The di e ences a e mainly wo: Two memb anes a e conside ed, one as inpu
memb ane and he second one ( he skin) is he ou pu memb ane. In his way we
p epa e he composi ion wi h P sys ems o he second amily.
7
The second di e ence is due o echnical easons. We add new elemen s which
has no meaning in he encoding o he in o ma ion, bu hey make sense a e he
composi ion (objec s e0,zand ) and a coun e 1.
The p oblem can be s a ed as ollows: Gi en a mul ise Ao na u al numbe s
exp essed in bina y o m, o ge a mul ise A′wi h such numbe s exp essed in bina y
o m.
We adap he desc ip ion om sec ion e sec:enc. Ins ead o codi ying a single
na u al numbe , we look o a P sys em which con e a mul ise o numbe s. So,
o each elemen in he mul ise , we conside a ma k {x1, x2,...}, so in his way,
ollowing sec ion ?? he mul ise {3,4,3,11}can be exp essed in bina y o m as he
se o pai s
{(x1,1),(x1,1),(x2,3),(x3,1),(x3,2),(x4,1)(x4,2),(x4,4)}
whe e (xi, j) ep esen s ha he i− h elemen in he enume a ion o he mul ise
has one in he j− h posi ion o he bina y ep esen a ion.
We de ine he amily ΠB={PB(n, d) : n, d ∈N}whe e each PB(n, d) sol es
all he ins ances o he p oblem wi h he same numbe o elemen s nand he same
bound d, de ined in he equa ion ??. (In ac , hese nand da e uppe bounds).
The P sys em PB(n, d) = (O(n, d), H, EC, µ, w , ws,...,R(n, d)) is de ined as
ollows:
•O(n, d) = {e0, z, }∪{y1,...,yn}∪{ 1,..., d+1}
∪ {(xi, j) : 1 ≤i≤n, 1≤j≤d}
•H={ , s}wi h he label o he inpu memb ane and s, he skin he label
o he ou pu memb ane.
•EC =∅(We can also conside he memb anes wi h neu al cha ge along all
he compu a ion)
•µ= [ [ ] ]s
•w ={e0, , 1};ws=∅
•The ollowing se o ules R(n, d):
[(xi, j)→(xi, j −1)] o all i∈ {1,...n}and j∈ {1,...,d}.
[(xi,1) →yi] o all i∈ {1,...n}.
[ j→ j+1] o all j∈ {1,...,d}.
[ d+1] →z.
All he ules a e associa ed o he label and a e objec e olu ion ule. The only
excep ion is he las one, which is a dissolu ion ule.
A he beginning o he compu a ion, he inpu codi ying he mul ise o na u al
numbe s in bina y o m (as desc ibed abo e) is placed in he inpu memb ane. The
P sys em e ol es as desc ibed in sec ion ??. A e ds eps he memb ane con ains
he elemen s e0, , d+1 and a mul ise o elemen s yi, 1 ≤i≤ncodi ying he
inpu . In he nex s ep d+1 dissol es he memb ane and is ans o med in o zin
8
he skin. The emaining objec s also go o he skin. No mo e ules can be applied
and he compu a ion hal s.
The compu a ion is de e minis ic and hal s a e d+ 1 s eps.
5.2. The amily Πpa
This amily is a uni o m amilyco P sys ems in he amewo k o ac i e mem-
b anes (see ...) which sol es he NP-p oblem Pa i ion. I is based on he solu ion
p esen ed in ... bu wi h small changes. Each P sys em Ppa (n) sol es all ins ances
o he p oblem wi h nelemen s. The solu ion is ob ained in polynomial ime on
nand he inpu has o be p o ided in una y o m. Each P syss em o he amily,
Ppa (n), n, ∈Nconsis s on he ollowing elemen s:
•O(n) = {a0, a, b0, b, c, d0, d1, d2, , g, g0, g1, h0, h1, p0, p, q, z, #, yes, no, no0} ∪
{e0,...,en}∪{i1, i2, i3, i4}∪{x1,...,xn}∪{y1,...,yn}∪{z1,...,z2n+1}
•H={e, , s}; he skin s, he label e o he wo king memb anes and a label
o he memb ane o con ol.
•EC ={+,−,0}
•µ= [ [ ] [ ]e]s
•we=∅;ws=∅;w ={b0, h0}
•The se o ules R(n) desc ibed below. We ollow he design o sol ing PAR-
TITION wi h ac i e memb anes p esen ed in ..., wi h small changes due o
echnical easons. A de ailed desc ip ion and mo i a ion o he ules can be
ound he e.
cIn he sense o ...
9