Sol ing Mul idimensional 0-1 Knapsack
P oblem by P Sys ems wi h Inpu
and Ac i e Memb anes
Linqiang PAN1,2, Ca los MARTIN-VIDE2
1Depa men o Con ol Science and Enginee ing
Huazhong Uni e si y o Science and Technology
Wuhan 430074, Hubei, People’s Republic o China
E-mail: [email p o ec ed]
2Resea ch G oup on Ma hema ical Linguis ics
Ro i a i Vi gili Uni e si y
Pl. Impe ial T`a aco 1, 43005 Ta agona, Spain
Abs ac . P sys ems a e pa allel molecula compu ing models based on p o-
cessing mul ise s o objec s in cell-like memb ane s uc u es. In his pape we
gi e a memb ane algo i hm o mul idimensional 0–1 knapsack p oblem in lin-
ea ime by ecognize P sys ems wi h inpu and wi h ac i e memb anes using
2-di ision. This algo i hm can also be modi ied o sol e gene al 0–1 in ege
p og amming p oblem.
1 In oduc ion
The P sys ems a e a class o dis ibu ed pa allel compu ing de ices o a biochemical ype,
in oduced in [4], which can be seen as a gene al compu ing a chi ec u e whe e a ious
ypes o objec s can be p ocessed by a ious ope a ions. I comes om he obse a ion
ha ce ain p ocesses which ake place in he complex s uc u e o li ing o ganisms can
be conside ed as compu a ions. Since Gh. P˘aun in oduced i , compu e scien is s and
biologis s, e al. ha e con ibu ed en iching he ield wi h hei di e en poin s o iew.
Fo a mo i a ion and de ailed desc ip ion o a ious P sys em models, please e e o [4, 6].
Memb ane di ision – inspi ed om cell di ision well-known in biology – is he mos
in es iga ed way o ob aining an exponen ial wo king space in a linea ime, and sol ing
on his basis ha d p oblems, ypically NP-comple e p oblems, in polynomial (o en, linea )
ime. De ails can be ound in [5, 6, 11]. Recen ly, PSPACE-comple e p oblems we e also
a acked in his way (see [13, 1]).
In [8] P´e ez-Jim´enez e al. sol e sa is iabili y p oblem in linea ime wi h espec
o he numbe o a iables and clauses o p oposi ional o mula by ecognize P sys ems
wi h inpu and wi h ac i e memb anes using 2-di ision. Thus he mul idimensional 0–1
knapsack p oblem belonging o he class o NP-comple e p oblems can also be sol ed in a
polynomial ime by P sys ems wi h inpu and wi h ac i e memb anes using 2-di ision. One
can ge his kind o solu ion by he educ ion o mul idimensional 0–1 knapsack p oblem o
342
sa is iabili y p oblem in o de o apply hose P sys ems which sol e sa is iabili y p oblem
in a linea ime. Bu he p ocess o educ ion is usually cumbe some and ime consuming
(polynomial ime). On he o he hand, i s ill emains open ha how one can educe
an NP p oblem o ano he NP-comple e p oblem by P sys ems. So, in his pape , we
di ec ly gi e a memb ane algo i hm o sol e mul idimensional 0–1 knapsack p oblem in
linea ime by ecognize P sys ems wi h inpu and wi h ac i e memb anes using 2-di ision.
He e, we ocus in he design o a amily o P sys ems ha sol es mul idimensional 0–1
knapsack p oblem, no in he o mal e i ica ion o he memb ane algo i hm. As discussed
in sec ion 4, his algo i hm is no di icul o be modi ied o sol e he gene al 0–1 in ege
p og amming p oblem.
The pape is o ganized as ollows: in sec ion 2 he no ion o ecognize P sys em is
in oduced, which is he model o compu a ion o sol e mul idimensional 0–1 knapsack
p oblem, and he polynomial complexi y class in compu ing wi h memb anes is ecalled;
sec ion 3 gi es a memb ane algo i hm o sol e mul idimensional 0–1 knapsack p oblem in
linea ime by ecognize P sys ems wi h ac i e memb anes using 2-di ision; in sec ion 4
some discussion is p esen ed.
2 P Sys ems
We s a by in oducing P sys ems wi h ac i e memb anes due o [5], whe e mo e de ails
can also be ound.
Figu e 1: A memb ane s uc u e and i s associa ed ee
'
&
$
%
'
&
$
%
#
"Ã
!
#
"Ã
!
¾
½
»
¼
'
&
$
%
'
&
$
%
º
¹
·
¸
1
234
5
6
7
8
¶
¶
¶
¶
¶
SSSS
S
¢
¢
¢
¢
¢
AAAA
1
2
3
4
5 6 7
8
Amemb ane s uc u e is ep esen ed by a Venn diag am and is iden i ied by a s ing o
co ec ly ma ching pa en heses, wi h a unique ex e nal pai o pa en heses; his ex e nal
pai o pa en heses co esponds o he ex e nal memb ane, called he skin. A memb ane
wi hou any o he memb ane inside is said o be elemen a y. Fo ins ance, he s uc u e
in Figu e 1 con ains 8 memb anes; memb anes 3, 5, 6 and 8 a e elemen a y. The s ing o
pa en heses iden i ying his s uc u e is
µ= [1[2[5]5[6]6]2[3]3[4[7[8]8]7]4]1.
All memb anes a e labeled; he e we ha e used he numbe s om 1 o 8. We say ha he
numbe o memb anes is he deg ee o he memb ane s uc u e, while he heigh o he
343
ee associa ed in he usual way wi h he s uc u e is i s dep h. In he example abo e we
ha e a memb ane s uc u e o deg ee 8 and o dep h 4.
In wha ollows, he memb anes can be ma ked wi h + o −, and his is in e p e ed
as an “elec ical cha ge”, o wi h 0, and his means “neu al cha ge”. We will w i e
[i]+
i,[i]−
i,[i]0
iin he h ee cases, espec i ely.
The memb anes delimi egions, p ecisely iden i ied by he memb anes ( he egion o a
memb ane is delimi ed by he memb ane and all memb anes placed immedia ely inside i ,
i any such a memb ane exis s). In hese egions we place objec s, which a e ep esen ed
by symbols o an alphabe . Se e al copies o he same objec can be p esen in a egion,
so we wo k wi h mul ise s o objec s. A mul ise o e an alphabe Vis ep esen ed by a
s ing o e V: he numbe o occu ences o a symbol a∈Vin a s ing x∈V∗(V∗is
he se o all s ings o e V; he emp y s ing is deno ed by λ) is deno ed by |x|aand i
ep esen s he mul iplici y o he objec ain he mul ise ep esen ed by x.
AP sys em wi h ac i e memb anes and 2-di ision is a cons uc
Π = (O, H, µ, w1, . . . , wm, R),
whe e:
(i) m≥1 ( he ini ial deg ee o he sys em);
(ii) Ois he alphabe o objec s;
(iii) His a ini e se o labels o memb anes;
(i ) µis a memb ane s uc u e, consis ing o mmemb anes, labelled (no necessa ily in
a one- o-one manne ) wi h elemen s o H;
( ) w1, . . . , wma e s ings o e O, desc ibing he mul ise s o objec s placed in he m
egions o µ;
( i) Ris a ini e se o de elopmen al ules, o he ollowing o ms:
(a) [ha→ ]α
h,
o h∈H, α ∈ {+,−,0}, a ∈O, ∈O∗
(objec e olu ion ules, associa ed wi h memb anes and depending on he label
and he cha ge o he memb anes, bu no di ec ly in ol ing he memb anes,
in he sense ha he memb anes a e nei he aking pa in he applica ion o
hese ules no a e hey modi ied by hem);
(b) a[h]α1
h→[hb]α2
h,
o h∈H, α1, α2∈ {+,−,0}, a, b ∈O
(communica ion ules; an objec is in oduced in he memb ane, possibly modi-
ied du ing his p ocess; also he pola iza ion o he memb ane can be modi ied,
bu no i s label);
(c) [ha]α1
h→[h]α2
hb,
o h∈H, α1, α2∈ {+,−,0}, a, b ∈O
(communica ion ules; an objec is sen ou o he memb ane, possibly modi ied
du ing his p ocess; also he pola iza ion o he memb ane can be modi ied, bu
no i s label);
344
(d) [ha]α
h→b,
o h∈H, α ∈ {+,−,0}, a, b ∈O
(dissol ing ules; in eac ion wi h an objec , a memb ane can be dissol ed,
while he objec speci ied in he ule can be modi ied);
(e) [ha]α1
h→[hb]α2
h[hc]α3
h,
o h∈H, α1, α2, α3∈ {+,−,0}, a, b, c ∈O
(di ision ules o elemen a y memb anes; in eac ion wi h an objec , he mem-
b ane is di ided in o wo memb anes wi h he same label, possibly o di e en
pola iza ions; he objec speci ied in he ule is eplaced in he wo new mem-
b anes by possibly new objec s);
( ) [h0[h1]α1
h1. . . [hk]α1
hk[hk+1 ]α2
hk+1 . . . [hn]α2
hn]α0
h0
→[h0[h1]α3
h1. . . [hk]α3
hk]α5
h0[h0[hk+1 ]α4
hk+1 ...[hn]α4
hn]α6
h0,
o k≥1, n > k, hi∈H, 0≤i≤n, and α0, . . . , α6∈ {+,−,0}wi h
{α1, α2}={+,−}; i he memb ane wi h he label h0con ains o he mem-
b anes han hose wi h he labels h1, . . . , hnspeci ied abo e, hen hey mus
ha e neu al cha ges in o de o make his ule applicable; hese memb anes a e
duplica ed and hen a e pa o he con en s o bo h new copies o he mem-
b ane h0
(di ision o non-elemen a y memb anes; his is possible only i a memb ane
con ains wo immedia ely lowe memb anes o opposi e pola iza ion, + and −;
he memb anes o opposi e pola iza ions a e sepa a ed in he wo new mem-
b anes, bu hei pola iza ion can change; always, all memb anes o opposi e
pola iza ions a e sepa a ed by applying his ule).
Fo a de ailed desc ip ion o using hese ules we e e o [5, 6]. He e we only men ion
ha he ules a e used in he non-de e minis ic maximally pa allel manne cus oma y
in memb ane compu ing in he bo om-up manne : in any gi en s ep, one uses i s he
e olu ion ules o ype (a), hen he o he ules which also in ol e a memb ane; mo eo e ,
one uses i s he ules o ypes (b), (c), (d), (e), and hen hose o ype ( ). I is impo an
o no e ha a one s ep a memb ane hcan be subjec o only one ule o ypes (b)-( ). In
his way, we ge ansi ion om a con igu a ion o he sys em o he nex con igu a ion.
A sequence o ansi ions is a compu a ion. A compu a ion is hal ing i no o he ules can
be applied in i s las con igu a ion.
To unde s and wha i means ha a p oblem can be sol ed in polynomial ime by P
sys ems, i is necessa y o ecall some complexi y measu e o P sys ems as desc ibed in
[9].
Conside a decision p oblem Aand deno e by A(n) an ins ance o Ao size n. Gi en
a class Xo memb ane sys ems and a o al unc ion :N→N( o example, linea and
polynomial unc ions), we say ha p oblem Abelongs o MCX( ) i a amily o memb ane
sys ems ΠA= (ΠA(1),ΠA(2), . . .) o ype Xexis s such ha :
1. ΠAis a uni o m amily: he e is a Tu ing machine which cons uc s ΠA(n) in poly-
nomial ime s a ing om n.
2. Each ΠA(n) is con luen : he e is a dis inguished objec yes such ha ei he in e e y
compu a ion o ΠA(n) he objec yes is send ou om he sys em, o his happens
in no compu a ion.
345
3. ΠA(n) is sound: ha is, ΠA(n) sends ou he objec yes i and only i he answe o
ΠA(n) is “yes”.
4. ΠAis -e icien : ha is, ΠAalways hal s in a mos (n) s eps.
The polynomial complexi y classes associa ed wi h a amily o memb ane sys ems, X,
a e de ined as ollows:
PMCX=[
polynomial
MCX( ).
In [6], he de ini ion o hese complexi y classes is based on a semi-uni o m cons uc ion
o P sys ems sol ing a p oblem A: one s a s no om n, bu om an ins ance A(n). Fo
a clea e desc ip ion o he di e ence be ween uni o m P sys ems and semi-uni o m P
sys ems, please e e o [7].
In wha ollows, we use ecognize P sys ems. Fi s o all, ollowing [7, 9] we conside
P sys ems wi h inpu . Such a de ice is a uple (Π,Σ, i0), whe e:
– Π is a P sys em, wi h he alphabe o objec s Γ and ini ial mul ise s w1,· · · , wm
(associa ed wi h memb anes labelled by 1,···, m, espec i ely).
– Σ is an (inpu ) alphabe s ic ly con ained in Γ and such ha w1,· · · , wma e mul-
ise s o e Γ −Σ.
–i0is he label o a dis inguished memb ane (o inpu ).
I wis a mul ise o e Σ, hen he ini ial con igu a ion o (Π,Σ, i0) wi h inpu wis
(µ, w0
1,· · · , w0
m), whe e w0
i=wi o i6=i0, and w0
i0=wi0∪w.
The compu a ions o a P sys em wi h inpu a e de ined in a na u al way. No e ha
he ini ial con igu a ion is ob ained by adding he inpu mul ise wo e Σ o he ini ial
con igu a ion o he sys em Π.
Now, a ecognize P sys em is a P sys em wi h inpu , (Π,Σ, i0), such ha :
1. The alphabe o objec s con ains wo dis inguished elemen s yes,no.
2. All compu a ions o he sys em hal .
3. I Cis a compu a ion o Π, hen ei he he objec yes o he objec no (bu no bo h)
ha e o be sen ou o he en i onmen , and only in he las s ep o he compu a ion.
We say ha Cis an accep ing ( espec i ely, ejec ing) compu a ion i he objec yes
( espec i ely, no appea s in he en i onmen in he hal ing con igu a ion o C.
3 Sol ing Mul idimensional 0–1 Knapsack P oblem
by Recognize P Sys ems wi h Ac i e Memb anes
3.1 P oblem Fo mula ion
The 0–1 Mul idimensional Knapsack P oblem (MKP) is a well known NP-comple e com-
bina o ial p oblem [2]. The decision MKP can be o mula ed as ollows: gi en an in ege
k, an objec i e unc ion (x1,· · · , xn) =
n
P
j=1
cjxj, and cons ain s
n
P
j=1
wijxj≤bi, o
i= 1,···, m,xj∈ {0,1}, o j= 1,· · · , n, whe e cj,wi,j and bia e nonnega i e in ege s,
346

decide whe he o no he e exis s an assignmen o a iables xjsuch ha i sa is ies he
cons ain s and he objec i e unc ion is g ea e han o equal o k.
MKP is an impo an combina o ial op imiza ion p oblem bo h om a heo e ic and
p ac ical poin o iew, which can o mula e many p ac ical p oblems such as capi al
budge ing whe e p ojec jhas p o i cjand consume (wij) uni s o esou ce i. The goal
is o de e mine a subse o he np ojec s such ha he o al p o i is maximized and all
esou ce cons ains a e sa is ied. O he impo an applica ions include ca go loading [12]
cu ing s ock p oblems, and p ocesso alloca ion in dis ibu ed sys ems [3].
The special case o MKP wi h m= 1 is he classical knapsack p oblem (KP). I is well
known ha he KP is no s ongly NP-ha d because he e a e polynomial app oxima ion
algo i hms o sol e i . This is no he case o he gene al MKP. In he amewo k o
cellula compu ing, a memb ane algo i hm o sol e KP is de eloped [10]. In he nex
subsec ion, we will gi e memb ane algo i hm o he gene al MKP.
3.2 Memb ane Algo i hm o Mul idimensional 0–1 Knapsack P oblem
We p esen a solu ion o MKP ia a b u e o ce algo i hm, in he amewo k o ecognize
P sys ems wi h ac i e memb anes using 2-di ision.
Gi en an ins ance uo MKP as shown in he abo e subsec ion, o con enience, we call
n
P
j=1
wijxj≤bi(1 ≤i≤m) he i h cons ain inequali y, and
n
P
j=1
cjxj≥k he (m+ 1) h
inequali y.
Le us conside a polynomial bijec ion, h i, be ween N∗l(l≥2) and N∗, de ined
as ollows: hy1, y2i= (y1+y2)(y1+y2+ 1)/2 + y1,hy1, y2, y3i=hhy1, y2i, y3i, and
hy1,· · · , yl−1, yli=hhy1,· · · , yl−1i, yli, whe e N∗deno es he se o nonnega i e in ege s.
We de ine he size unc ion h(u) = hn, k, b1,···, bmi, and he inpu unc ion g(u) =
xw11
1,1xw21
2,1· · · xwm1
m,1xc1
m+1,1· · · xw1n
1,n xw2n
2,n · · · xwmn
m,n xcn
m+1,n, whe e he i s subsc ip io xi,j de-
no es he i h inequali y, he second subsc ip jo xi,j co esponds o he a iable xj.
Fo each hn, k, b1,· · · , bmi, we conside he ecognize P sys em (Π(hn, k, b1,· · · ,
bmi),Σ(hn, k, b1,· · · , bmi), i0), whe e Σ(hn, k, b1,· · · , bmi) = {xi,j |1≤i≤m+
1,1≤j≤n},i(hn, k, b1,···, bmi) = 2 and Π(hn, k, b1,· · · , bmi) = (Γ(n, k, b1,· · · ,
bm),{1,2},[1[2]2]1, w1, w2, R), Γ(n, k, b1,···, bm) is de ined as ollows:
Γ(m, n) = Σ(hn, k, b1,· · · , bmi)∪ {di|1≤i≤3n+ 2
m
X
i=1
bi+ 3m+ 2k+ 1}
∪ { i,j, si,j |1≤i≤m, 1≤j≤2n}∪{ai,j, i,j |1≤i≤m, 0≤j≤2n}
∪ {qi,j |0≤i≤2 max{b1,· · · , bm}+ 1,1≤j≤m}
∪ {qi,m+1 |0≤i≤2k+ 1}∪{d+, d−, e0, λ, yes,no}.
The ini ial con en o each memb ane is: w1=∅and w2=d1ab1
1,0ab2
2,0· · · abm
m,0 k
m+1,0. The
se o ules, R, is gi en by (we also gi e explana ion abou he use o hese ules du ing
he compu a ions):
1. [2di]0
2→[2di]+
2[2di]−
2,1≤i≤n.
By using a ule o (1), a memb ane wi h label 2 is di ided in o wo memb anes
wi h he same label, bu wi h di e en pola iza ions. These ules allow us o ha e
exponen ial wo kspace in linea ime.
347
2. [2xi,1→ i,1]+
2, 1 ≤i≤m.
[2xm+1,1→sm+1,1]+
2.
[2xi,1→λ]−
2, 1 ≤i≤m+ 1.
The ules o (2) y o implemen a p ocess allowing memb anes wi h label 2 o
encode he assignmen o he a iable x1, in such a way ha i he a iable x1
akes alue 1, hen he objec s xi,1(1 ≤i≤m) e ol e o objec s i,1, and he
objec s xm+1,1e ol e o objec s sm+1,1, in he co esponding memb anes wi h label
2 and posi i e cha ge; o he wise, he objec s xi,1will disappea in he co esponding
memb anes wi h label 2 and nega i e cha ge.
3. [2xi,j →xi,j−1]+
2, 1 ≤i≤m+ 1, 2 ≤j≤n.
[2xi,j →xi,j−1]−
2, 1 ≤i≤m+ 1, 2 ≤j≤n.
The e ol ing p ocess desc ibed p e iously is always made wi h espec o he a iable
x1. Hence, he ules o (3) ake cha ge o making a cyclic pa h h ough all he
a iables o ge ha , ini ially, he i s a iable is x1, hen x2, and so on.
4. [2di]+
2→[2]0
2di, 1 ≤i≤n.
[2di]−
2→[2]0
2di, 1 ≤i≤n.
di[2]0
2→[2di+1]0
2, 1 ≤i≤n−1.
The ules o (4) a e used as con olle s o he gene a ing p ocess o he assignmen s
o all a iables and he encoding o he coe icien s: he objec s dia e sen o he
memb ane wi h label 1 a he same ime he assignmen s a e made, and hey come
back o he memb anes wi h label 2 o s a he di ision o hese memb anes.
5. [2 i,j → i,j+1]0
2, 1 ≤i≤m, 1 ≤j≤2n−1.
[2sm+1,j →sm+1,j+1]0
2, 1 ≤j≤2n−1.
[2ai,j →ai,j+1]0
2, 1 ≤i≤m, 0 ≤j≤2n−1.
[2 m+1,j → m+1,j+1]0
2, 0 ≤j≤2n−1.
The use o objec s 1,2n, a1,2n, sm+1,2n, m+1,2nin he ules (8), (11) and (14) makes
necessa y o pe o m a o a ion o hese objec s. This is he mission o he ules o
(5).
6. [1di→di+1]0
1,n≤i≤3n−3.
[1d3n−2→d3n−1e0]0
1.
Th ough he coun e -objec s di, he ules o (6) con ol he o a ion o he objec s
i,j,sm+1,j,ai,j and m+1,j in he memb anes wi h label 2, so ha hei second
subsc ip s a e uni ied o 2n.
7. e0[2]0
2→[2q0,1]−
2.
[1d3n−1→d3n]0
1.
The applica ion o he ules o (7) will show ha he sys em is eady o check whe he
he cons ain inequali ies a e sa is ied by he assignmen o a iables encoded by an
in e nal memb ane.
8. [2 1,2n]−
2→[2]0
2λ.
[2a1,2n]0
2→[2]−
2λ.
These ules implemen he compa ison ( ha is, hey check whe he he cons ain
inequali y holds o no ). They wo k as a loop ha e ases objec s 1,2nand a1,2n
one by one al e na i ely, changing he cha ge o he memb ane in each s ep. We
348
will see ha i he checking had an a i ma i e esul , hen he memb ane would ge
posi i ely cha ged, and he checking o he nex inequali y will be ac i a ed.
9. [2q2j,i →q2j+1,i]−
2, o j= 0,· · · ,max{b1,· · · , bm}, 1 ≤i≤m.
[2q2j+1,i →q2j+2,i]0
2, o j= 0,· · · ,max{b1,· · · , bm} − 1, 1 ≤i≤m.
A coun e ha con ols he p e ious loop is desc ibed he e. The subsc ip o qj,i
and he elec ic cha ge o he memb ane gi e enough in o ma ion o poin ou i he
numbe o objec s i,2nis no g ea e han (less han o equal o) he numbe o
objec s ai,2n.
10. [2q2j+1,i]−
2→[2]+
2q0,i+1, o j= 0,· · · ,max{b1,· · · , bm}, 1 ≤i≤m.
I an assignmen e i ies he i h cons ain inequali y, hen inside he co esponding
memb ane ha encodes i he e will no be mo e objec s i,2n han ai,2n. This o ces
he loop desc ibed in (9) o s op: he momen will come when he e a e no objec s
i,2nle , and hen he ule [2q2j,i →q2j+1,i]−
2will be applied bu i will no be
possible o apply he ule [2 1,2n]−
2→[2]0
2# a he same ime. Thus, an objec
q2w(i)+1 will be p esen in he memb ane wi h nega i e cha ge, whe e w(i) =
n
P
j=1
wij,
so he ule (10) will be applied.
11. [2 i,2n→ i−1,2n]+
2, o 2 ≤i≤m.
[2ai,2n→ai−1,2n]+
2, o 2 ≤i≤m.
[2si,2n→si−1,2n]+
2, o 2 ≤i≤m+ 1.
[2 i,2n→ i−1,2n]+
2, o 2 ≤i≤m+ 1.
The compa ison p ocess desc ibed in he ules o (8) is always made wi h espec o
he i s cons ain inequali y. Hence he ules o (11) ake cha ge o making a cyclic
pa h h ough all he cons ain inequali y. ( o he objec i e unc ion inequali y, we
ha e di e en compa ison p ocess, as shown la e in ules o (14), (15) and (16).)
12. q0,i+1[2]+
2→[2q0,i+1]−
2, o 1 ≤i≤m−1.
The memb anes wi h posi i e cha ge mean ha he assignmen s encoded by hem
ha e e i y he i s icons ain inequali y. The objec s q0,i+1 en e he memb anes
wi h he label 2 and posi i e cha ge, changing he cha ge o nega i e o allow he
checking o nex inequali y o begin (using ules o ypes (8), (9), (10)).
13. q0,m+1[2]+
2→[2q0,m+1]+
2.
I he e is a leas one assignmen which e i y all he cons ain inequali ies, hen
objec s q0,m+1 appea in he skin memb ane. In he nex s ep, by he ule o (13),
hese objec s en e he memb anes wi h label 2 and posi i e cha ge. A he same
ime, he objec s s1,2nand 1,2nappea in he memb anes encoding assignmen s
which e i y all he cons ain inequali ies (using ules o (11)). Now he sys em is
eady o checking he objec i e unc ion inequali y.
14. [2s1,2n]+
2→[2]0
2λ.
[2 1,2n]0
2→[2]+
2λ.
The checking loop is designed o objec i e unc ion as ules o (8) o cons ain
inequali ies, bu he elec ic cha ges in ol ed a e now neu al and posi i e.
15. [2q2j,m+1 →q2j+1,m+1]+
2, o j= 0,· · · , k.
[2q2j+1,m+1 →q2j+2,m+1]0
2, o j= 0,· · · , k −1.
The coun e qj,m+1 con ols he p e ious loop desc ibed in he ules o (14).
349
16. [2q2k+1,m+1]+
2→[2]0
2yes.
[2q2k+1,m+1]0
2→[2]0
2yes.
I an assignmen e i ies he objec i e unc ion inequali y, hen in he memb ane
encoding his assignmen he e a e no less objec s s1,2n han objec s 1,2n. This
causes he ules om (15) o apply k imes each, and a e ha he i s subsc ip o
qj,2nwill be j= 2k. Then he ule [2q2j,m+1 →q2j+1,m+1]+
2will be applied (possibly
oge he wi h [2s1,2n]+
2→[2]0
2λ) and one o he ules om (16) will p oduce he
objec yes epo ing ha his assignmen e i ies he objec i e unc ion inequali y.
17. [1di→di+1]0
1, o i= 3n, · · · ,3n+ 2
m
P
i=1
bi+ 3m+ 2k+ 1.
[1dl→d+d−]0
1, whe e l= 3n+ 2
m
P
i=1
bi+ 3m+ 2k+ 1.
Be o e he answe is sen ou o he en i onmen , all o he memb ane should ha e
ei he ended hei checking s age success ully (checking he cons ain inequali ies
and objec i e unc ion inequali y) o go o a blocking s a e o he wise. The coun e
djgi es enough ime o deal wi h he wo s case. The condi ion o wo s case
(i.e. he case ha he checking s age will las longe ) is ha he assignmen wi h
all a iables aking alue 1 is a solu ion (i.e. i e i ies he cons ain inequali ies
and he objec i e unc ion inequali y). The numbe o compu a ional s eps will be
maximum i
n
P
j=1
wij =bi, o i= 1,· · · , n.
18. [1d+]0
1→[1]+
1d+.
[1d−→no]+
1.
[1yes]+
1→[1]0
1yes.
[1no]+
1→[1]0
1no.
The ou pu p ocess is ac i a ed. The skin memb ane needs o be posi i ely cha ged
be o e he answe is send ou o he en i onmen . Objec d+ akes cha ge o his,
and, hen, i he answe is a i ma i e, an objec yes will be sen ou changing he
cha ge o he skin o neu al. O he wise, an objec no will be sen ou changing he
cha ge o he skin o neu al.
F om he p e ious explana ion o he use o ules, one can easily see how his P sys em
wo ks. I is easy o p o e ha he designed P sys em is de e minis ic, con luen , and
sound.
The amily is polynomially uni o m by Tu ing machines. I can be obse ed ha he
abo e desc ip ion o he e olu ion ules is compu able in an uni o m way, in pa icula
om he cons an s n,m,k, and bi,i= 1,···, m.
Now, we p o e ha he amily Π= (Π( )) ∈Nsol es he MKP in linea ime.
The compu a ional p ocess o he designed P sys em wi h inpu g(u) can be s uc u ed
in ou s ages: a s age o gene a ion o all assignmen s o a iables; a s age o synch o-
niza ion; a s age o checking whe he he e is an assignmen which sa is ies he cons ain
inequali ies and he objec i e unc ion inequali y; and a s age o ou pu .
The gene a ion is con olled by he objec s di, wi h 1 ≤i≤n.
– The p esence in he skin o one objec di, wi h 1 ≤i≤n, will show ha all possible
pa ial assignmen s associa ed wi h {x1,· · · , xi}ha e been gene a ed.
350