Solving Knapsack Problems in a Sticker Based Model

Sol ing Knapsack P oblems in a S icke Based Model P´e ez–Jim´enez, M.J. and Sancho–Capa ini, F. Dp . Compu e Science and A ificial In elligence. Uni e si y o Se ille. Spain Abs ac . Ou main goal in his pape is o gi e molecula solu ions o wo NP–comple e p oblems, namely Subse -sum and Knapsack, in a s icke based model o DNA compu a ions. In o de o achie e his, we ha e used a fini e se so ing sub ou ine oge he wi h he desc ip ion o a p ocedu e o o mally e i y he designed p og ams h ough he labeling o es ubes using induc i e echniques. 1 In oduc ion The s icke model was in oduced by S. Roweis, E. Win ee e al ([3]) as an abs ac model o molecula compu ing based on DNA wi h a andom access memo y and a new o m o encoding he in o ma ion. The main goal o his wo k is he esolu ion, in his model, o wo NP– comple e p oblems: he Subse -Sum p oblem and he Knapsack p oblem, in i s 0/1 bounded and unbounded e sions. The in o ma ion is ep esen ed in he s icke model in a diffe en way om ha used in he Adleman-Lip on pa adigm. A (n, k, m)-memo y s and, wi h n≥k·m,isnbases in leng h subdi ided in o knon-o e lapping subs and each mbases long. The subs ands should be significan ly diffe en om each o he . A s icke associa ed o a (n, k, m)-memo y s and is mbases long and complemen a y o exac ly one o he ksubs ands in he memo y s and. I a s icke is annealed o i s ma ching subs and on a memo y s and, hen he pa icula subs and is said o be on. I no s icke is annealed o a subs and, hen he egion is said o be off.A(n, k, m)-memo y complex is a (n, k, m)-memo y s and along wi h i s annealed s icke s (i any). In a di ec way, (n, k, m)-memo y complexes ep esen bi s ings o {0,1}k. Fo his eason, i is usual o iden i y hem ei he as bina y unc ions (σ:{1, ..., k}−→{0,1}, such ha σ(i)=1i and only i he i- h subs and is on), o as subse s o {1, ..., k}by means o he cha ac e is ic unc ion. Wi hin he s icke model, a ube is a fini e mul ise whose elemen s a e memo y complexes ( ha is, a collec ion o memo y complexes whe e each one can be epea ed). The ollowing ope a ions o e ubes o he s icke model a e used in his pape : –Me ge (T1,T 2): he memo y complexes om he ubes T1,T 2a e combined o o m he mul ise union o all s ings in he wo inpu ubes. We w i e Me ge(T1,T 2)=T1∪T2as well. –Sepa a e (T,i): Gi en a ube, T, and an in ege , i(1 ⩽i⩽numbe o subs ands ha o m each complex o T), c ea e wo new ubes, +(T,i)and −(T,i), whe e +(T,i)( esp.−(T,i)) con ain all s ings o Tha ing he i– h subs and se o 1 ( esp. se o 0). We w i e (T1,T 2)←sepa a e(T,i) o indica e ha T1=+(T,i)andT2=−(T,i). –Se (T,i): Gi en a ube, T, and an in ege , i(1 ⩽i⩽numbe o subs ands ha o m each complex o T), his ope a ion p oduces a new ube whe e he i– h subs and o each memo y complex in Tis se o 1. Tha is, he s icke o ha bi is annealed o i- h egion on e e y memo y complex in T. –Read (T): Gi en a nonemp y ube T, his ope a ion eads i s con en . Fo ha , one memo y complex mus be isola ed om Tand i s annealed s icke s, i any, de e mined. A(k,l)-lib a y, wi h 1 ≤k≤l, consis s o memo y complexes wi h ksub- s ands, he fi s lsubs ands a e ei he on o off, in all possible ways, whe eas he las k−lsubs ands a e off. In sec ion 2, he p oblem o so ing he elemen s o a fini e amily o fini e se s, acco ding o hei ca dinali y, is s udied, and o he fi s ime, a p og am ha is able o sol e his p oblem is desc ibed wi hin he sicke model. I i is aken in o accoun ha jus wo molecula ope a ions ha e been used, namely sepa a e and me ge, he p og am designed can also be conside ed as a p og am wi hin he un es ic ed model o Adleman ([1]). In sec ion 3 we gi e a filling sub ou ine wi hin he s icke model o encode he weigh o subse s ega ding a gi en posi i e unc ion ha will be used in ollowing sec ions. In sec ion 4, we gi e a molecula solu ion wi hin he s icke model o he Subse –Sum p oblem, using he so ing by ca dinali y p og am and he filling sub ou ine. Fo mal e ifica ion o he p og ams designed in sec ions 2, 3 and 4 is es ablished h ough he p io labeling o he dis inc ubes which appea in he execu ion. Then we p o e he soundness and comple eness o hese p og ams using induc i e echniques and analyzing he his o y o e e y molecule in he ini ial es – ube along he p ocess. In sec ions 5 and 6, we gi e molecula solu ions, wi hin he s icke model, o Knapsack p oblem (0/1 bounded and unbounded e sions), based in bo h he so ing by ca dinali y p og am gi en in sec ion 2, and he filling sub ou ine gi en in sec ion 3. All designed p og ams use a linea numbe o ubes, and he numbe o molecula ope a ions is, basically, quad a ic. 2 So ing by Ca dinali y P oblem:Le A={1, ..., p},B={b1, ..., bs}⊆A,F={D1, ..., D }⊆P(A). So he se s o Facco ding o hei ela i e ca dinali y o B( ha is, acco ding o he numbe o elemen s o B∩Di). Nex , we will design a molecula p og am wi hin he s icke model which sol es he abo e p oblem. –The inpu ube, T0, will con ain memo y complexes, σ, based on DNA, en- coding each se o he amily F. Fo his, each complex o T0will be ep e- sen ed h ough a boolean unc ion, ha is, T0={{σ:|σ|=p∧∃j(χDj= σ)}}, whe e χDjis he cha ac e is ic unc ion o Djin A(χDj(i)=1i i∈Dj,andχDj(i)=0i i∈A−Dj). –The p og am consis s o a main loop FOR wi h ss eps. In he i– h s ep, i+1 ubes, T0,T 1,...,T i, a e gene a ed e i ying he condi ion: ∀σ(σ∈ Tj−→ | σ∩{b1,...,b i}| =j). In o de o achie e his, we design he body o he loop by induc ion. Once he ubes T0,T 1,...,T ico esponding o he i– h s ep ha e been buil , he ubes o he nex s ep T0,T 1,...,T i,T i+1 a e gene a ed in his way: ⎧ ⎨ ⎩ T0=−(T0,b i+1) Tj=+(Tj−1,b i+1)∪−(Tj,b i+1)(1⩽j⩽i) Ti+1 =+(Ti,b i+1) The execu ion o he molecula p og am can be desc ibed s a ing om a oo ed g aph ha we denomina e labeled me ge–bina y ee ha is defined by ecu sion as ollows: –A node wi h a label is a labeled me ge–bina y ee o dep h 0. –Le Abe a labeled me ge–bina y ee o dep h h. F om i , a labeled me ge– bina y ee, A, o dep h h+ 1 is buil in his way: •Ini ially, each lea o Ade e mines wo child en. •The igh child o each lea and he le one o he nex lea gi e a node o Awhose label is he composi ion o he labels o his child en by a ce ain fixed bina y ope a ion. In he desc ip ion ha has been ca ied ou so a , he nodes o he me ge– bina y ee o execu ion a e labeled by means o ubes. The le and igh chil- d en o a ube, T, o dep h ha e labeled s a ing om he sepa a e ope a ion: (Tle ,T igh )←− sepa a e(T,bh+1). Finally, he bina y ope a ion conside ed is he molecula me ge ope a ion applied o he ubes indica ed by he labels o he nodes. These ideas sugges he ollowing molecula p og am: Inpu : (T0,B) o i=1 o sdo (T0,T 1)←sepa a e (T0,b i) o j=0 o i−1do (T j,T j+1)←sepa a e (Tj,b i) Tj←T j∪T j end o Ti←T i end o Ou pu : T0, ..., Ts The p ocedu e desc ibed will e u n s+ 1 ubes and we will no e hem as: Ca dinal so (T0,B)[j],(0 ≤j≤s). We ha e ha |Ca dinal so (T0,B)[j]|=j. This molecula p og am uses 2s ubes and he numbe o molecula ope a- ions is s·(s+3) 2. Le us no e ha he p og am we ha e gi en o sol e he so ing p oblem is alid in a model wi hou andom access memo y, like he un es ic ed model o Adleman. The simples way o see his is o adap he inpu ube, eplacing memo y complex o single s ands o DNA. To es ablish he o mal e ifica ion o he algo i hm p og am, we will p oceed o label he ubes ob ained along he execu ion so ha we can indi idualize hem in any momen o he unning. Inpu : T0 T0,0←T0;T0,−1←∅;T0,1←∅ o i=1 o sdo Ti,−1←∅;Ti,i+1 ←∅ o j=0 o ido Ti,j ←+(Ti−1,j−1,b i)∪−(Ti−1,j,b i) end o end o Ou pu : Ts,0, ..., Ts,s By means o con enience, we assume ha T0,−1=T0,1=∅, and we will no e Bj={b1, ..., bj}, and, by defini ion, we will ake B0=∅. P oposi ion 1. ∀i(1 ≤i≤s→∀j≤i∀σ(σ∈Ti,j →|σ∩Bi|=j)). P oo . By induc ion on i. Le us see ha ∀j≤1∀σ∈T1,j (|σ∩B1|=j). –Le σ∈T1,0=+(T0,−1,b 1)∪−(T0,0,b 1). Since T0,−1=∅and T0,0=T0,i esul s ha σ∈−(T0,b 1), ha is, b1/∈σ. Then, |σ∩B1|=0. –Le σ∈T1,1=+(T0,0,b 1)∪−(T0,1,b 1). Since T0,1=∅, i esul s ha σ∈T0,0=T0and b1∈σ, hen |σ∩B1|=1 Le i(1 ≤i<s) be such ha ∀j≤i∀σ∈Ti,j (|σ∩Bi|=j). Le us see ha he esul e ifies o i+ 1. Fo i , we now p oceed by induc ion on j: ∀j≤i+1∀σ∈Ti+1,j (|σ∩Bi+1|=j). –Le σ∈Ti+1,0=+(Ti,−1,b i+1)∪−(Ti,0,b i+1). Since Ti,−1=∅, i esul s ha σ∈Ti,0and bi+1 /∈σ, by induc ion hypo hesis we deduce ha |σ∩Bi|=0. So |σ∩Bi+1|= 0, since bi+1 /∈σ. –Le j>0andσ∈Ti+1,j =+(Ti,j−1,b i+1)∪−(Ti,j,b i+1). Then •I σ∈Ti,j−1and bi+1 ∈σ, by induc ion hypo hesis we ha e ha |σ∩ Bi|=j−1. Since bi+1 ∈σ, we conclude ha |σ∩Bi+1|=j−1+1=j. •I σ∈Ti,j and bi+1 /∈σ, by induc ion hypo hesis we ha e ha |σ∩Bi|= j.Asbi+1 /∈σ,weha e|σ∩Bi+1|=j. P oposi ion 2. ∀σ∈T0∀i(0 ≤i≤s→σ∈Ti,|σ∩Bi|). P oo . By induc ion on i.Fo i= 0, he esul is i ial. Assume he esul holds o i(0 ≤i<s); we will p o e i o i+1. –I bi+1 ∈σ,weha e|σ∩Bi+1|=1+|σ∩Bi|. By induc ion hypo hesis, σ∈Ti,|σ∩Bi|, hen σ∈+(Ti,|σ∩Bi|,b i+1)⊆Ti+1,|σ∩Bi|+1. –I bi+1 /∈σ, hen |σ∩Bi+1|=|σ∩Bi|. By induc ion hypo hesis, σ∈Ti,|σ∩Bi|, hen σ∈−(Ti,|σ∩Bi|,b i+1)⊆Ti+1,|σ∩Bi|=Ti+1,|σ∩Bi+1|. ¿F om he p eceding p oposi ions i may be concluded, espec i ely, soundness (e e y molecule o he ou pu ube p o ides a co ec solu ion associa ed o ha ube) and comple eness (e e y molecule o he inpu ube appea s in he co esponding ou pu ube, acco ding o i s ca dinali y) o he designed p og am. Co olla y 1. (Soundness) ∀j∀σ(0 ≤j≤s∧σ∈Ts,j →|σ∩B|=j). Co olla y 2. (Comple eness) I σ∈T0and |σ∩B|=j, hen σ∈Ts,j . As cases o pa icula in e es , ha we will use in o he molecula p og ams, we ge he ollowing: –Ca dinal so (T0), when B=A. –Ca dinal so (T0,l,k), when B={l,l +1, ..., k}. 3 A filling sub ou ine In his sec ion we show a molecula p og am ha will be used as auxilia y sub ou ine o sol e he Subse –Sum p oblem and he Knapsack p oblem in he ollowing sec ions. Le A={1, ..., p}, ∈IN a n d :A−→ IN a unc ion. I B⊆A,we no e (B)=i∈B (i). Fo con enience we define (0) = 0. Le q = (A), Ai={0,...,i}(0 ≤i≤p)andT0a mul ise o (n, k, m)-memo y complexes, σ, wi h k≥p+ +q . As i was seen in he p e ious sec ion, each σ∈T0encodes a subse Bσ⊆A cha ac e ized by he condi ion Bσ={i:1≤i≤p∧σ(i)=1}, and ecip o- cally, each subse , B⊆A, can be encoded by a molecule σB∈T0, cha ac e ized by he condi ion: σB(i) = 1 i and only i i∈B. I σ∈T0, we can suppose ha i is o med by he ollowing zones: (Aσ)=σ(1) ...σ(p), (Fσ)=σ(p+ +1)...σ(p+ +q ) (Lσ)=σ(p+1)...σ(p+ ), (Rσ)=σ(p+ +q +1)... The sub ou ine wo ks o e T0, and i modifies hei elemen s making ha he molecules o he ou pu ube s o e in (Fσ) he weigh , ega ding ,o he subse o Aencoded in (Aσ) (zones (Rσ) and (Lσ) ha e no effec in he p ocess, bu hey will be use ul o a gene al use). Tha is: p  i=1 σ(i) (i)= p+ +q  j=p+ +1 σ(j) The designed p og am will be no ed Pa allel Fill(T0, ,p, ): Inpu : (T0, ,p, ) o i=1 o pdo (T+,T−)←sepa a e(T0,i) o j=1 o (i)do T+←se (T+,p+ + (Ai−1)+j) end o T0←me ge (T+,T−) end o Ou pu : T0 To es ablish he o mal e ifica ion o he algo i hm, we will p oceed o label he ubes ob ained along he execu ion. Inpu : (T0, ,p, ) o i=1 o pdo (T+ i,0,T− i)←sepa a e(Ti−1,i) o j=1 o (i)do T+ i,j ←se (T+ i,j−1,p+ + (Ai−1)+j) end o Ti←me ge (T+ i, (i),T− i) end o Ou pu : Tp Fo each i(1 ≤i≤p) we conside he ollowing egions: Ri={p+ + (Ai−1)+1, ..., p + + (Ai)} Defini ion 1. Fo each σ∈T0and each k(1 ≤k≤p), we will no e σk he molecule ob ained om σa e he execu ion o he k– h s ep in he main loop o he p og am. Tha is, he molecules σkp o ide he his o y o he molecule σo he inpu ube, while he p og am is unning. Keeping in mind he syn ac ic s uc u e o he p og am, i is s aigh o wa d o p o e he ollowing esul s: Lemma 1. 1. The ini ial zone o he molecule (encoding he subse o A) does no change along he execu ion o he p og am; ha is, ∀σ∈T0∀k(1 ≤k≤p→(Aσ)=(Aσk)) (1) 2. The molecules ha a e ob ained in he k- h s ep o he main loop a e s o ed in he ube Tk; ha is, ∀σ∈T0∀k(1 ≤k≤p→σk∈Tk) (2) 3. E e y molecule o he k- h ube comes om some molecule in he ini ial ube; ha is, ∀k(1 ≤k≤p→∀τ∈Tk∃σ∈T0(σk=τ)) (3) 4. The execu ion o a s ep o he main loop does no modi y he egions co es- ponding o p e ious s eps; ha is, ∀σ∈T0∀i∀k(1 ≤i≤k≤p→σi |Ri=σk |Ri) (4) 5. A e he execu ion o he i- h s ep o he main loop, he egion Rio σhas been modified o ag ee wi h he alue o σ(i); ha is, ∀σ∈T0∀i∀k(1 ≤i≤k≤p→σk |Ri≡σ(i)) (5) 6. The execu ion o a s ep o he main loop does no modi y he zones (Lσ)and (Rσ); ha is, ∀σ∈T0∀k(1 ≤k≤p→(Lσ)=(Lσk)∧(Rσ)=(Rσk)) (6) The ollowing esul assu es us ha he main loop modifies he egions Rio he molecules o encode he pa ial weigh o he se ep esen ed by each one o hem. P oposi ion 3. Le B⊆Asuch ha σB∈T0, hen o each k(1 ≤k≤p)we ha e ha : (B∩{1, ..., k})= p+ + (Ak)  j=p+ +1 σk B(j) P oo . ¿F om (1) i ollows ha (B∩{1, ..., k})= k  i=1 (i)·σB(i)= k  i=1 (i)·σk B(i) On he o he hand, (1) and (5) assu es ha (i)·σk B(i)=j∈Riσk B(j)) (1 ≤i≤k) Co olla y 3. Fo each B⊆Asuch ha σB∈T0 he e exis s τ∈Tpsuch ha (B)=p+ +q i=p+ +1 τ(i). P oo . Gi en B⊆A, le us conside he associa ed molecule σB∈T0. I suffices o conside τ=σp B, since (B)= (B∩{1, ..., p})=p+ +q j=p+ +1 σp B(j).  4 Subse -Sum p oblem P oblem:Le A={1, ..., p}and w:A−→ IN a weigh unc ion. Le k∈IN be such ha k≤w(A)=qw. De e mine whe he he e exis s a subse B⊆Asuch ha he sum o he weigh s o he elemen s in Bis, exac ly, k. Nex we will design a molecula p og am wi hin he s icke model ha sol es he Subse –Sum p oblem. The inpu ube, T0, will be a (p+qw,p)-lib a y. In a fi s s age (filling), each molecule, σ, o he inpu ube is filled in o de o ob ain in hei las qcomponen s he weigh o he subse ha i encodes; he molecules o he esul ing ube o he p e ious s age a e o de ed acco ding o hei ca dinali y. Finally, he k- h ube is ead: i con ains he molecules om he inpu ube encoding subse s o Ao weigh k,i any. These ideas sugges he design o he ollowing molecula p og am: Subse Sum(p, w, k) qw←p i=1 w(i) T0←(p+qw,p)-lib a y T1←Pa allel Fill(T0,w,p,0) Tou ←Ca dinal so (T1,p+1,p+qw)[k] Read(Tou ) The numbe o used ubes (including he sub ou ines) is 4 + 2qand he numbe o molecula ope a ions is 2p+q+1+q·(q+3) 2. The ollowing esul shows he soundness o he molecula p og am; ha is, e e y molecule in he ou pu ube encodes a co ec solu ion o he Subse –Sum p oblem. Theo em 1. (Soundness) I Tou =∅, hen he e exis s B⊆Asuch ha w(B)=k. P oo . Taking τ∈Tou , and applying (3) and p oposi ion 3, we ob ain σ∈T0 e i ying he esul o Bσ. Nex heo em p o es he comple eness o he gi en molecula p og am; ha is, e e y molecule in he inpu ube encoding a co ec solu ion o he Subse – Sum p oblem, is in he ou pu ube. Theo em 2. (Comple eness) Le σ∈T0be such ha w(Bσ)=k.ThenTou =∅ P oo . Le σ∈T0be such ha w(Bσ)=k, om co olla y 3, a e he execu ion o he filling sub ou ine, we ha e a molecule τ=σp∈T1such ha w(Bσ)= p+qw i=p+1 τ(i). Then τ∈Tou . No e. The abo e p og am does no only sol e he p oblem o decision, bu a he , i e u ns all he solu ions o he p oblem. I we only wan ed o sol e he decision p oblem, once he filling s age has been execu ed, we could use some app op ia e es ic ion enzymes which emo e om each molecule, σ,in he ube Tp, he ini ial egion (Aσ), and hen apply an app op ia e p ocedu e Ca dinal so , so ha we may wo k wi h molecules o smalle leng h in he final s age. 5 0/1 Bounded Knapsack P oblem P oblem:Le A={1, ..., p}be a non emp y fini e se , w:A−→ IN a weigh unc ion, and ρ:A−→ IN a unc ion o alues. Le k,k∈IN be such ha k≤w(A)=qwand k≤ρ(A)=qρ. De e mine whe he he e exis s a subse B⊆Asuch ha w(B)≤kand ρ(B)≥k. Nex we will design a molecula p og am in he s icke model ha sol es he p oblem 0/1 bounded Knapsack p oblem: we begin wi h a (p+qw+qρ,p)- lib a y. In a fi s s age (filling), we p oceed as in he p e ious p og am: each molecule o he ini ial ube is filled app op ia ely so ha i encodes he weigh o he associa e subse ; nex he molecules, σ, o he esul ing ube a e o de ed acco ding o he ca dinal o w(Aσ), being ob ained some ubes, T0, ..., Tqw, such ha ∀σ(σ∈Tj⇒|w(Aσ)|=j). Wi h he ube T0∪... ∪Tka second s age o filling is ca ied ou , ega ding he unc ion o alues. Then, he molecules, σ, om he esul ing ube a e o de ed acco ding o he ca dinal o ρ(Aσ), being ob ained, again, some ubes, T0, ..., Tqρ, such ha ∀σ(σ∈Tj⇒|ρ(Aσ)|=j). Finally, he ube Tk∪... ∪Tqρ, con aining he encoded solu ions o he p oblem, is ead. These ideas sugges he ollowing molecula p og am: Knapsack(p, w, ρ, k, k) qw←p i=1 w(i); qρ←p i=1 ρ(i); T0←(p+qw+qρ,p)-lib a y T0←Pa allel Fill(T0,w,p,0) Ca dinal so (T0,p+1,p+qw) T1←∅ o i=1 o kdo T1←me ge (T1,Ca dinal so (T0,p+1,p+qw)[i]) end o T0←Pa allel Fill(T1,ρ,p,q w) Ca dinal so (T0,p+qw+1,p+qw+qρ) T1←∅ o i=k o qρdo T1←me ge (T1,Ca dinal so (T0,p+qw+1,p+qw+qρ)[i]) end o Read(T1) The numbe o ubes used by he p og am (again, including he sub ou ines) is 5+ 2 ·max{qw,q ρ}, and he numbe o molecula ope a ions ca ied ou in he execu ion is 4p+k−k+qw·(qw+5)+qρ·(qρ+7) 2+1. The o mal e ifica ion o his p og am is simila o he one o he Subse – Sum p oblem, we omi i s p oo since i does no show any new ideas o he e ifica ion me hods o he s icke model. 6 0/1 Unbounded Knapsack P oblem P oblem:Unde he same condi ions as he Knapsack p oblem, de e mine a subse B⊆Asuch ha ρ(B) = max{ρ(C): C⊆A∧w(C)≤k}. A molecula solu ion is ob ained om he solu ion o he bounded p oblem, changing he final ou pu s age: a e he so ing o he ubes ega ding he unc ion o alues, we will choose he non emp y ube wi h bigge index. Unbounded Knapsack(p, w, ρ, k) qw←p i=1 w(i); qρ←p i=1 ρ(i); T0←(p+qw+qρ,p)-lib a y T0←Pa allel Fill(T0,w,p,0) Ca dinal so (T0,p+1,p+qw) T1←∅ o i=0 o kdo T1←me ge(T1,Ca dinal so (T0,p+1,p+qw)[i]) end o