Solving Knapsack Problems in a Sticker Based Model

Solving Knapsack Problems in a Sticker Based Model P´erez–Jim´enez, M.J. and Sancho–Caparrini, F. Dpt. Computer Science and Artificial Intelligence. University of Seville. Spain Abstract. Our main goal in this paper is to give molecular solutions for two NP–complete problems, namely Subset-sum and Knapsack, in a sticker based model for DNA computations. In order to achieve this, we have used a finite set sorting subroutine together with the description of a procedure to formally verify the designed programs through the labeling of test tubes using inductive techniques. 1 Introduction The sticker model was introduced by S. Roweis, E. Winfree et al ([3]) as an abstract model of molecular computing based on DNA with a random access memory and a new form of encoding the information. The main goal of this work is the resolution, in this model, of two NP– complete problems: the Subset-Sum problem and the Knapsack problem, in its 0/1 bounded and unbounded versions. The information is represented in the sticker model in a different way from that used in the Adleman-Lipton paradigm. A (n, k, m)-memory strand, with n≥k·m,isnbases in length subdivided into knon-overlapping substrand each mbases long. The substrands should be significantly different from each other. A sticker associated to a (n, k, m)-memory strand is mbases long and complementary to exactly one of the ksubstrands in the memory strand. If a sticker is annealed to its matching substrand on a memory strand, then the particular substrand is said to be on. If no sticker is annealed to a substrand, then the region is said to be off.A(n, k, m)-memory complex is a (n, k, m)-memory strand along with its annealed stickers (if any). In a direct way, (n, k, m)-memory complexes represent bit strings of {0,1}k. For this reason, it is usual to identify them either as binary functions (σ:{1, ..., k}−→{0,1}, such that σ(i)=1if and only if the i-th substrand is on), or as subsets of {1, ..., k}by means of the characteristic function. Within the sticker model, a tube is a finite multiset whose elements are memory complexes (that is, a collection of memory complexes where each one can be repeated). The following operations over tubes of the sticker model are used in this paper: –Merge (T1,T 2): the memory complexes from the tubes T1,T 2are combined to form the multiset union of all strings in the two input tubes. We write Merge(T1,T 2)=T1∪T2as well. –Separate (T,i): Given a tube, T, and an integer, i(1 ⩽i⩽number of substrands that form each complex of T), create two new tubes, +(T,i)and −(T,i), where +(T,i)(resp.−(T,i)) contain all strings of Thaving the i–th substrand set to 1 (resp. set to 0). We write (T1,T 2)←separate(T,i)to indicate that T1=+(T,i)andT2=−(T,i). –Set (T,i): Given a tube, T, and an integer, i(1 ⩽i⩽number of substrands that form each complex of T), this operation produces a new tube where the i–th substrand of each memory complex in Tis set to 1. That is, the sticker for that bit is annealed to i-th region on every memory complex in T. –Read (T): Given a nonempty tube T, this operation reads its content. For that, one memory complex must be isolated from Tand its annealed stickers, if any, determined. A(k,l)-library, with 1 ≤k≤l, consists of memory complexes with ksubstrands, the first lsubstrands are either on or off, in all possible ways, whereas the last k−lsubstrands are off. In section 2, the problem of sorting the elements of a finite family of finite sets, according to their cardinality, is studied, and for the first time, a program that is able to solve this problem is described within the sicker model. If it is taken into account that just two molecular operations have been used, namely separate and merge, the program designed can also be considered as a program within the unrestricted model of Adleman ([1]). In section 3 we give a filling subroutine within the sticker model to encode the weight of subsets regarding a given positive function that will be used in following sections. In section 4, we give a molecular solution within the sticker model for the Subset–Sum problem, using the sorting by cardinality program and the filling subroutine. Formal verification of the programs designed in sections 2, 3 and 4 is established through the prior labeling of the distinct tubes which appear in the execution. Then we prove the soundness and completeness of these programs using inductive techniques and analyzing the history of every molecule in the initial test–tube along the process. In sections 5 and 6, we give molecular solutions, within the sticker model, for Knapsack problem (0/1 bounded and unbounded versions), based in both the sorting by cardinality program given in section 2, and the filling subroutine given in section 3. All designed programs use a linear number of tubes, and the number of molecular operations is, basically, quadratic. 2 Sorting by Cardinality Problem:Let A={1, ..., p},B={b1, ..., bs}⊆A,F={D1, ..., Dt}⊆P(A). Sort the sets of Faccording to their relative cardinality to B(that is, according to the number of elements of B∩Di). Next, we will design a molecular program within the sticker model which solves the above problem. –The input tube, T0, will contain memory complexes, σ, based on DNA, encoding each set of the family F. For this, each complex of T0will be represented through a boolean function, that is, T0={{σ:|σ|=p∧∃j(χDj= σ)}}, where χDjis the characteristic function of Djin A(χDj(i)=1if i∈Dj,andχDj(i)=0ifi∈A−Dj). –The program consists of a main loop FOR with ssteps. In the i–th step, i+1tubes, T0,T 1,...,T i, are generated verifying the condition: ∀σ(σ∈ Tj−→ | σ∩{b1,...,b i}| =j). In order to achieve this, we design the body of the loop by induction. Once the tubes T0,T 1,...,T icorresponding to the i–th step have been built, the tubes of the next step T0,T 1,...,T i,T i+1 are generated in this 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 execution of the molecular program can be described starting from a rooted graph that we denominate labeled merge–binary tree that is defined by recursion as follows: –A node with a label is a labeled merge–binary tree of depth 0. –Let Abe a labeled merge–binary tree of depth h. From it, a labeled merge– binary tree, A, of depth h+ 1 is built in this way: •Initially, each leaf of Adetermines two children. •The right child of each leaf and the left one of the next leaf give a node of Awhose label is the composition of the labels of this children by a certain fixed binary operation. In the description that has been carried out so far, the nodes of the merge– binary tree of execution are labeled by means of tubes. The left and right children of a tube, T, of depth hare labeled starting from the separate operation: (Tleft,T right)←− separate(T,bh+1). Finally, the binary operation considered is the molecular merge operation applied to the tubes indicated by the labels of the nodes. These ideas suggest the following molecular program: Input: (T0,B) for i=1 to sdo (T0,T 1)←separate (T0,b i) for j=0 to i−1do (T j,T j+1)←separate (Tj,b i) Tj←T j∪T j end for Ti←T i end for Output: T0, ..., Ts The procedure described will return s+ 1 tubes and we will note them as: Cardinal sort(T0,B)[j],(0 ≤j≤s). We have that |Cardinal sort(T0,B)[j]|=j. This molecular program uses 2stubes and the number of molecular operations is s·(s+3) 2. Let us note that the program we have given to solve the sorting problem is valid in a model without random access memory, like the unrestricted model of Adleman. The simplest way to see this is to adapt the input tube, replacing memory complex for single strands of DNA. To establish the formal verification of the algorithm program, we will proceed to label the tubes obtained along the execution so that we can individualize them in any moment of the running. Input: T0 T0,0←T0;T0,−1←∅;T0,1←∅ for i=1 to sdo Ti,−1←∅;Ti,i+1 ←∅ for j=0 to ido Ti,j ←+(Ti−1,j−1,b i)∪−(Ti−1,j,b i) end for end for Output: Ts,0, ..., Ts,s By means of convenience, we assume that T0,−1=T0,1=∅, and we will note Bj={b1, ..., bj}, and, by definition, we will take B0=∅. Proposition 1. ∀i(1 ≤i≤s→∀j≤i∀σ(σ∈Ti,j →|σ∩Bi|=j)). Proof. By induction on i. Let us see that ∀j≤1∀σ∈T1,j (|σ∩B1|=j). –Let σ∈T1,0=+(T0,−1,b 1)∪−(T0,0,b 1). Since T0,−1=∅and T0,0=T0,it results that σ∈−(T0,b 1), that is, b1/∈σ. Then, |σ∩B1|=0. –Let σ∈T1,1=+(T0,0,b 1)∪−(T0,1,b 1). Since T0,1=∅, it results that σ∈T0,0=T0and b1∈σ, then |σ∩B1|=1 Let i(1 ≤i<s) be such that ∀j≤i∀σ∈Ti,j (|σ∩Bi|=j). Let us see that the result verifies for i+ 1. For it, we now proceed by induction on j: ∀j≤i+1∀σ∈Ti+1,j (|σ∩Bi+1|=j). –Let σ∈Ti+1,0=+(Ti,−1,b i+1)∪−(Ti,0,b i+1). Since Ti,−1=∅, it results that σ∈Ti,0and bi+1 /∈σ, by induction hypothesis we deduce that |σ∩Bi|=0. So |σ∩Bi+1|= 0, since bi+1 /∈σ. –Let j>0andσ∈Ti+1,j =+(Ti,j−1,b i+1)∪−(Ti,j,b i+1). Then •If σ∈Ti,j−1and bi+1 ∈σ, by induction hypothesis we have that |σ∩ Bi|=j−1. Since bi+1 ∈σ, we conclude that |σ∩Bi+1|=j−1+1=j. •If σ∈Ti,j and bi+1 /∈σ, by induction hypothesis we have that |σ∩Bi|= j.Asbi+1 /∈σ,wehave|σ∩Bi+1|=j. Proposition 2. ∀σ∈T0∀i(0 ≤i≤s→σ∈Ti,|σ∩Bi|). Proof. By induction on i.Fori= 0, the result is trivial. Assume the result holds for i(0 ≤i<s); we will prove it for i+1. –If bi+1 ∈σ,wehave|σ∩Bi+1|=1+|σ∩Bi|. By induction hypothesis, σ∈Ti,|σ∩Bi|, then σ∈+(Ti,|σ∩Bi|,b i+1)⊆Ti+1,|σ∩Bi|+1. –If bi+1 /∈σ, then |σ∩Bi+1|=|σ∩Bi|. By induction hypothesis, σ∈Ti,|σ∩Bi|, then σ∈−(Ti,|σ∩Bi|,b i+1)⊆Ti+1,|σ∩Bi|=Ti+1,|σ∩Bi+1|. ¿From the preceding propositions it may be concluded, respectively, soundness (every molecule of the output tube provides a correct solution associated to that tube) and completeness (every molecule of the input tube appears in the corresponding output tube, according to its cardinality) of the designed program. Corollary 1. (Soundness) ∀j∀σ(0 ≤j≤s∧σ∈Ts,j →|σ∩B|=j). Corollary 2. (Completeness) If σ∈T0and |σ∩B|=j, then σ∈Ts,j . As cases of particular interest, that we will use in other molecular programs, we get the following: –Cardinal sort(T0), when B=A. –Cardinal sort(T0,l,k), when B={l,l +1, ..., k}. 3 A filling subroutine In this section we show a molecular program that will be used as auxiliary subroutine to solve the Subset–Sum problem and the Knapsack problem in the following sections. Let A={1, ..., p},r∈IN a n d f:A−→ IN a function. If B⊆A,we note f(B)=i∈Bf(i). For convenience we define f(0) = 0. Let qf=f(A), Ai={0,...,i}(0 ≤i≤p)andT0a multiset of (n, k, m)-memory complexes, σ, with k≥p+r+qf. As it was seen in the previous section, each σ∈T0encodes a subset Bσ⊆A characterized by the condition Bσ={i:1≤i≤p∧σ(i)=1}, and reciprocally, each subset, B⊆A, can be encoded by a molecule σB∈T0, characterized by the condition: σB(i) = 1 if and only if i∈B. If σ∈T0, we can suppose that it is formed by the following zones: (Aσ)=σ(1) ...σ(p), (Fσ)=σ(p+r+1)...σ(p+r+qf) (Lσ)=σ(p+1)...σ(p+r), (Rσ)=σ(p+r+qf+1)... The subroutine works over T0, and it modifies their elements making that the molecules of the output tube store in (Fσ) the weight, regarding f,ofthe subset of Aencoded in (Aσ) (zones (Rσ) and (Lσ) have no effect in the process, but they will be useful for a general use). That is: p  i=1 σ(i)f(i)= p+r+qf  j=p+r+1 σ(j) The designed program will be noted Parallel Fill(T0,f,p,r): Input: (T0,f,p,r) for i=1 to pdo (T+,T−)←separate(T0,i) for j=1 to f(i)do T+←set(T+,p+r+f(Ai−1)+j) end for T0←merge (T+,T−) end for Output: T0 To establish the formal verification of the algorithm, we will proceed to label the tubes obtained along the execution. Input: (T0,f,p,r) for i=1 to pdo (T+ i,0,T− i)←separate(Ti−1,i) for j=1 to f(i)do T+ i,j ←set(T+ i,j−1,p+r+f(Ai−1)+j) end for Ti←merge (T+ i,f(i),T− i) end for Output: Tp For each i(1 ≤i≤p) we consider the following regions: Ri={p+r+f(Ai−1)+1, ..., p +r+f(Ai)} Definition 1. For each σ∈T0and each k(1 ≤k≤p), we will note σkthe molecule obtained from σafter the execution of the k–th step in the main loop of the program. That is, the molecules σkprovide the history of the molecule σof the input tube, while the program is running. Keeping in mind the syntactic structure of the program, it is straightforward to prove the following results: Lemma 1. 1. The initial zone of the molecule (encoding the subset of A) does not change along the execution of the program; that is, ∀σ∈T0∀k(1 ≤k≤p→(Aσ)=(Aσk)) (1) 2. The molecules that are obtained in the k-th step of the main loop are stored in the tube Tk; that is, ∀σ∈T0∀k(1 ≤k≤p→σk∈Tk) (2) 3. Every molecule of the k-th tube comes from some molecule in the initial tube; that is, ∀k(1 ≤k≤p→∀τ∈Tk∃σ∈T0(σk=τ)) (3) 4. The execution of a step of the main loop does not modify the regions corresponding to previous steps; that is, ∀σ∈T0∀i∀k(1 ≤i≤k≤p→σi |Ri=σk |Ri) (4) 5. After the execution of the i-th step of the main loop, the region Riof σhas been modified to agree with the value of σ(i); that is, ∀σ∈T0∀i∀k(1 ≤i≤k≤p→σk |Ri≡σ(i)) (5) 6. The execution of a step of the main loop does not modify the zones (Lσ)and (Rσ); that is, ∀σ∈T0∀k(1 ≤k≤p→(Lσ)=(Lσk)∧(Rσ)=(Rσk)) (6) The following result assures us that the main loop modifies the regions Riof the molecules to encode the partial weight of the set represented by each one of them. Proposition 3. Let B⊆Asuch that σB∈T0, then for each k(1 ≤k≤p)we have that: f(B∩{1, ..., k})= p+r+f(Ak)  j=p+r+1 σk B(j) Proof. ¿From (1) it follows that f(B∩{1, ..., k})= k  i=1 f(i)·σB(i)= k  i=1 f(i)·σk B(i) On the other hand, (1) and (5) assures that f(i)·σk B(i)=j∈Riσk B(j)) (1 ≤i≤k) Corollary 3. For each B⊆Asuch that σB∈T0there exists τ∈Tpsuch that f(B)=p+r+qf i=p+r+1 τ(i). Proof. Given B⊆A, let us consider the associated molecule σB∈T0. It suffices to consider τ=σp B, since f(B)=f(B∩{1, ..., p})=p+r+qf j=p+r+1 σp B(j).  4 Subset-Sum problem Problem:Let A={1, ..., p}and w:A−→ IN a weight function. Let k∈IN be such that k≤w(A)=qw. Determine whether there exists a subset B⊆Asuch that the sum of the weights of the elements in Bis, exactly, k. Next we will design a molecular program within the sticker model that solves the Subset–Sum problem. The input tube, T0, will be a (p+qw,p)-library. In a first stage (filling), each molecule, σ, of the input tube is filled in order to obtain in their last qcomponents the weight of the subset that it encodes; the molecules of the resulting tube of the previous stage are ordered according to their cardinality. Finally, the k-th tube is read: it contains the molecules from the input tube encoding subsets of Aof weight k,ifany. These ideas suggest the design of the following molecular program: Subset Sum(p, w, k) qw←p i=1 w(i) T0←(p+qw,p)-library T1←Parallel Fill(T0,w,p,0) Tout ←Cardinal sort(T1,p+1,p+qw)[k] Read(Tout) The number of used tubes (including the subroutines) is 4 + 2qand the number of molecular operations is 2p+q+1+q·(q+3) 2. The following result shows the soundness of the molecular program; that is, every molecule in the output tube encodes a correct solution for the Subset–Sum problem. Theorem 1. (Soundness) If Tout =∅, then there exists B⊆Asuch that w(B)=k. Proof. Taking τ∈Tout, and applying (3) and proposition 3, we obtain σ∈T0 verifying the result for Bσ. Next theorem proves the completeness of the given molecular program; that is, every molecule in the input tube encoding a correct solution of the Subset– Sum problem, is in the output tube. Theorem 2. (Completeness) Let σ∈T0be such that w(Bσ)=k.ThenTout =∅ Proof. Let σ∈T0be such that w(Bσ)=k, from corollary 3, after the execution of the filling subroutine, we have a molecule τ=σp∈T1such that w(Bσ)= p+qw i=p+1 τ(i). Then τ∈Tout. Note. The above program does not only solve the problem of decision, but rather, it returns all the solutions to the problem. If we only wanted to solve the decision problem, once the filling stage has been executed, we could use some appropriate restriction enzymes which remove from each molecule, σ,in the tube Tp, the initial region (Aσ), and then apply an appropriate procedure Cardinal sort, so that we may work with molecules of smaller length in the final stage. 5 0/1 Bounded Knapsack Problem Problem:Let A={1, ..., p}be a non empty finite set, w:A−→ IN a weight function, and ρ:A−→ IN a function of values. Let k,k∈IN be such that k≤w(A)=qwand k≤ρ(A)=qρ. Determine whether there exists a subset B⊆Asuch that w(B)≤kand ρ(B)≥k. Next we will design a molecular program in the sticker model that solves the problem 0/1 bounded Knapsack problem: we begin with a (p+qw+qρ,p)- library. In a first stage (filling), we proceed as in the previous program: each molecule of the initial tube is filled appropriately so that it encodes the weight of the associate subset; next the molecules, σ, of the resulting tube are ordered according to the cardinal of w(Aσ), being obtained some tubes, T0, ..., Tqw, such that ∀σ(σ∈Tj⇒|w(Aσ)|=j). With the tube T0∪... ∪Tka second stage of filling is carried out, regarding the function of values. Then, the molecules, σ, from the resulting tube are ordered according to the cardinal of ρ(Aσ), being obtained, again, some tubes, T0, ..., Tqρ, such that ∀σ(σ∈Tj⇒|ρ(Aσ)|=j). Finally, the tube Tk∪... ∪Tqρ, containing the encoded solutions to the problem, is read. These ideas suggest the following molecular program: Knapsack(p, w, ρ, k, k) qw←p i=1 w(i); qρ←p i=1 ρ(i); T0←(p+qw+qρ,p)-library T0←Parallel Fill(T0,w,p,0) Cardinal sort(T0,p+1,p+qw) T1←∅ for i=1 to kdo T1←merge (T1,Cardinal sort(T0,p+1,p+qw)[i]) end for T0←Parallel Fill(T1,ρ,p,q w) Cardinal sort(T0,p+qw+1,p+qw+qρ) T1←∅ for i=kto qρdo T1←merge (T1,Cardinal sort(T0,p+qw+1,p+qw+qρ)[i]) end for Read(T1) The number of tubes used by the program (again, including the subroutines) is 5+ 2 ·max{qw,q ρ}, and the number of molecular operations carried out in the execution is 4p+k−k+qw·(qw+5)+qρ·(qρ+7) 2+1. The formal verification of this program is similar to the one for the Subset– Sum problem, we omit its proof since it does not show any new ideas for the verification methods for the sticker model. 6 0/1 Unbounded Knapsack Problem Problem:Under the same conditions as the Knapsack problem, determine a subset B⊆Asuch that ρ(B) = max{ρ(C): C⊆A∧w(C)≤k}. A molecular solution is obtained from the solution of the bounded problem, changing the final output stage: after the sorting of the tubes regarding the function of values, we will choose the non empty tube with bigger index. Unbounded Knapsack(p, w, ρ, k) qw←p i=1 w(i); qρ←p i=1 ρ(i); T0←(p+qw+qρ,p)-library T0←Parallel Fill(T0,w,p,0) Cardinal sort(T0,p+1,p+qw) T1←∅ for i=0 to kdo T1←merge(T1,Cardinal sort(T0,p+1,p+qw)[i]) end for