Con e ing In ege Numbe s om Bina y o Una y
No a ion wi h P Sys ems
Miguel A. GUTI´
ERREZ NARANJO1, Albe o LEPORATI2
and Claudio ZANDRON2
1Resea 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
E-mail: magu ie @us.es
2Dipa 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
E-mail: {lepo a i,zand on}@disco.unimib.i
Abs ac . 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 gen-
e 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.
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 ioning 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 o-
lu 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 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 ems1.
1A 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 [?].
1
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 amming
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 sis 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 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.
2
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 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)
3
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 esen 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 x
copies 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, 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 Π.
4
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 n
and 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 x
copies 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 .
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 Conclusions and di ec ions o u u e wo k
When sol ing nume ical NP–comple e p oblems using P sys ems, in ege numbe s a e
usually ep esen ed in una y no a ion. Howe e , in classical complexi y heo y such num-
be s a e assumed o be ep esen ed in bina y no a ion, which is an exponen ially mo e
compac encoding wi h espec o una y no a ion.
Swi ching om bina y o una y no a ion simpli ies NP–comple e nume ical p oblems,
because i modi ies he way me measu e he size o ins ances, as well as he ela ion
be ween ins ance size and he unning ime o algo i hms which sol e he p oblem.
The e en ual composi ion be ween ou sys ems and he ones exposed in li e a u e
allows o sol e NP–comple e nume ical p oblems wo king on ins ances whose numbe s a e
encoded in bina y o m. Mo eo e , since he ins ances mus be injec ed in o he sys ems
be o e s a ing compu a ions, wo king wi h bina y no a ion allows o p epa e such sys ems
wi h a polynomially bounded e o . The p epa a ion o hese sys ems equi es ins ead an
exponen ial amoun o wo k when dealing wi h ins ances whose numbe s a e encoded in
una y o m.
Howe e , his pape does no ully conclude he wo k on P sys ems which sol e NP–
comple e nume ical p oblems. In [?,?,?,?], a uni o m amily o P sys ems is designed
o sol e he p oblem and he same P sys em o he amily sol es e e y ins ance o he
p oblem wi h he same size. As we ha e seen, he P sys ems which a e able o ans o m
an in ege om bina y o una y ep esen a ion depends on he leng h o he numbe in
bina y ep esen a ion. In his way, i we wan o sol e an ins ance o he Pa i ion p oblem
5

wi h nin ege s, he P sys em ha we need do no depend only on n, bu on he conc e e
numbe s o he se , which can be a bi a ily la ge.
The wo k p esen ed in his pape opens a esea ch line in he ield o complexi y o P
sys ems which should be deepe s udied in he u u e.
Acknowledgmen s
The p esen pape has been inspi ed by join wo k wi h Se ille esea ch g oup du ing
he Thi d B ains o ming Week held in Se ille om Janua y 31s o Feb ua y 4 h, 2005.
The i s au ho acknowledges he suppo o his esea ch h ough he p ojec TIC2002-
04220-C03-01 o he Minis e io de Ciencia y Tecnolog´ıa o Spain, co inanced by FEDER
unds.
Re e ences
[1] G. Ausiello, P. C escenzi, G. Gambosi, V. Kann, A. Ma che i–Spaccamela, M. P o-
asi. Complexi y and App oxima ion. Combina o ial Op imiza ion P oblems and Thei
App oximabili y P ope ies. Sp inge –Ve lag, Be lin, 1999.
[2] T. H. Co men, C. H. Leise son, R. L. Ri es . In oduc ion o Algo i hms. MIT P ess,
1990.
[3] M. R. Ga ey, D. S. Johnson. Compu e s and In ac abili y. A Guide o he Theo y on
NP–Comple eness. W. H. F eeman and Company, 1979.
[4] Gu i´e ez-Na anjo, M.A.; P´e ez-Jim´enez, M.J.; Rome o-Campe o, F.J.: Sol ing SAT
wi h Memb ane C ea ion. Accep ed pape o CiE 2005.
[5] Gu i´e ez-Na anjo, M.A.; P´e ez-Jim´enez, M.J.; Rome o-Campe o, F.J.: A linea so-
lu ion o QSAT wi h Memb ane C ea ion. Submi ed, 2005.
[6] Gu i´e ez-Na anjo, M.A.; P´e ez-Jim´enez, M.J.; Riscos-N´u˜nez, A.: A as
P sys em o inding a balanced 2-pa i ion, DOI: 10.1007/s00500-004-0397-0
So Compu ing, in p ess. See also M. A. Gu i´e ez-Na anjo, M. J. P´e ez-
Jim´enez, A. Riscos-N´u˜nez. An E icien Cellula Solu ion o he Pa i ion P ob-
lem. In P oceedings o he Second B ains o ming Week on Memb ane Com-
pu ing, Uni e si y o Se ille, Feb ua y 2–7, 2004, pp. 237–246. A ailable a :
h p://www.gcn.us.es/B ain/b a olpd /AGPART.pd
[7] G. P˘aun. Compu ing wi h memb anes. Jou nal o Compu e and Sys em Sciences,
1(61):108–143, 2000. See also Tu ku Cen e o Compu e Science — TUCS Repo
No. 208, 1998. A ailable a : h p://www. ucs. i/Publica ions/ ech epo s/TR208.php
[8] G. P˘aun. Compu ing wi h Memb anes. An In oduc ion. Bulle in o he EATCS,
67:139–152, Feb ua y 1999.
[9] G. P˘aun. Compu ing wi h Memb anes. A a ian : P Sys ems wi h Pola ized Mem-
b anes. In e na ional Jou nal on Founda ions o Compu e Science, 11(1):167–182,
2000. See also CDMTCS Technical Repo 098, Uni e si y o Auckland, 1999. A ail-
able a : h p://www.cs.auckland.ac.nz/CDMTCS
6
[10] G. P˘aun. Memb ane Compu ing. An In oduc ion. Sp inge –Ve lag, Be lin, 2002.
[11] P˘aun, Gh.; P´e ez-Jim´enez, M.J.: Recen compu ing models inspi ed om biology:
DNA and memb ane compu ing, Theo ia,18, 46 (2003), 72–84.
[12] G. P˘aun, G. Rozenbe g. A Guide o Memb ane Compu ing. Theo e ical Compu e
Science, 287(1):73–100, 2002.
[13] M. J. P´e ez-Jim´enez, A. Riscos-N´u˜nez. A linea solu ion o he Knapsack p oblem
using ac i e memb anes. In C. Ma ´ın-Vide, G. Mau i, G. P˘aun, G. Rozenbe g and
A. Salomaa (eds.), Memb ane Compu ing, Lec u e No es in Compu e Science, ol.
2933, Sp inge -Ve lag, Be lin, 2004, pp. 250–268.
[14] M. J. P´e ez-Jim´enez, A. Riscos-N´u˜nez. Sol ing he Subse -Sum p oblem by ac i e
memb anes. New Gene a ion Compu ing, o appea .
[15] P´e ez-Jim´enez, M.J.; Rome o-Campe o, F.J.: Sol ing he BIN PACKING p oblem by
ecognize P sys ems wi h ac i e memb anes, P oceedings o he Second B ains o ming
Week on Memb ane Compu ing, Gh. P˘aun, A. Riscos, A. Rome o and F. Sancho
(eds.), Repo RGNC 01/04, Uni e si y o Se ille, 2004, 414–430.
[16] P´e ez-Jim´enez, M.J.; Rome o-Jim´enez, A.; Sancho-Capa ini, F.: A polynomial com-
plexi y class in P sys ems using memb ane di ision,P oceedings o he 5 h Wo kshop
on Desc ip ional Complexi y o Fo mal Sys ems, DCFS 2003, E. Csuhaj-Va j´u, C.
Kin ala, D. Wo schke and Gy. Vaszyl (eds.), 2003, 284-294.
[17] A. Riscos-N´u˜nez. Cellula p og amming: e icien esolu ion o NP–comple e nume -
ical p oblems. Ph. D. Thesis, Uni e si y o Se ille, Depa men o Compu e Science
and A i icial In elligence, 2004.
[18] R. L. Ri es , A. Shami , L. M. Adleman. A Me hod o Ob aining Digi al Signa-
u es and Public–Key C yp osys ems. Communica ions o he ACM, 21(2):120–126,
Feb ua y 1978.
[19] P sys ems web page h p://psys ems.disco.unimib.i /
7