You are an expert at summarizing long articles. Proceed to summarize the following text: 
m.aleknovich et . al have proposed a backtracking model in @xcite which generalizes both the priority model of borodin , nielson and rackoff @xcite , as well as a simple dynamic programming model due to woeginger @xcite , and hence spans a wide spectrum of algorithms . borodin then shared his insights into these models in @xcite . the definition of backtracking model is as follows . let @xmath2 be an arbitrary data domain that contains objects @xmath3 called data items . let @xmath4 be a set , representing the set of allowable decisions for a data item . for example , for the knapsack problem , a natural choice for @xmath2 would be the set of all pairs @xmath5 where @xmath6 is a weight and @xmath7 is a profit ; the natural choice for @xmath4 is @xmath8 where 0 is the decision to reject an item and 1 is the decision to accept an item . a backtracking search / optimization problem @xmath9 is specified by a pair @xmath10 where @xmath11 is the underlying domain , and @xmath12 is a family of objective functions , @xmath13 , where @xmath14 is a set of variables that range over @xmath4 , and @xmath15 is a set of variables that range over @xmath2 . on input @xmath16 , the goal is to assign each @xmath17 a value in @xmath4 so as to maximize ( or minimize ) @xmath18 . a search problem is a special case where @xmath18 outputs either 0 or 1 .    for any domain @xmath19 write @xmath20 for the set of all orderings of elements of @xmath19 . a backtracking algorithm @xmath21 for problem @xmath22 consists of the ordering functions @xmath23 and the choice functions @xmath24 where @xmath25 . there are three classes of bt algorithms . * _ fixed _ algorithms : @xmath26 does not depend upon any of its arguments . * _ adaptive _ algorithms : @xmath26 depends on @xmath27 but not on @xmath28 . * _ fully adaptive _ algorithms : @xmath26 depends on both @xmath27 and @xmath28 . the value of @xmath26 specifies the order to consider the remaining items , given that the choices about the first @xmath29 items have been made ; the value of @xmath30 specifies the order to make possible decisions about @xmath31 . for more detailed explanation of bt model , refer to @xcite . but it seems reasonable to repeat the definition of computation tree here , which serves as a good interpretation of _ assume that @xmath9 is a bt problem and @xmath21 is a bt algorithm for @xmath9 , for any instance @xmath32 we define the _ computation tree _ @xmath33 as an oriented rooted tree in the following recursive way . * each node @xmath34 of depth @xmath29 in the tree is labelled by a tuple @xmath35 . * the root node has the empty label . * for every node @xmath34 of depth @xmath36 with a label @xmath37 , let @xmath38 be the data item in @xmath39 that goes first in the list @xmath40 . assume that the output @xmath41 has the form @xmath42 , where @xmath43 . if @xmath44 then @xmath34 has no children . otherwise it has @xmath45 child nodes @xmath46 that go from left to right and have labels + @xmath47 resp .    following is an example diagram of computation tree , nodes for data items , edges for choices . it s easy to see that it represents an adaptive bt algorithm , but not fully adaptive . clearly the width of a computation tree is a lower bound of the computational complexity of the corresponding bt algorithm , so we will consider the asymptotic lower bounds of the computation tree width in the following text . to understand the proof shown later , we give the basic idea to prove such lower bounds first . it s a game between solver and adversary . initially , the adversary presents to the algorithm(solver ) some finite set of possible input items , @xmath48 , and the partial instance @xmath49 is empty , @xmath50 is the set consisting of the null partial solution . the game consists of a series of phases . at any phase @xmath51 , there is a set of possible data items @xmath52 , a partial instance @xmath53 and a set @xmath54 of partial solutions for @xmath53 . in phase @xmath51 , @xmath55 , the solver picks any data item @xmath56 , adds @xmath57 to obtain @xmath58 , and chooses a set @xmath54 of partial solutions , each of which must extend a solution in @xmath59 . the adversary then removes @xmath57 and some further items to obtain @xmath52 . the strategy of adversary will usually have the following form . the number of rounds , @xmath60 will be fixed in advance . the adversary will choose some @xmath61 such that , for many partial solutions @xmath62 of @xmath53 , there is an extension of @xmath53 to an instance @xmath63 so that all valid / optimal / approximately optimal solutions to @xmath64 are extensions of @xmath62 . we ll call such a partial solution _ indispensable _ , since if @xmath65 , the adversary can set @xmath52 to @xmath66 so that the algorithm will never result in correct solution . first let us recall the definition of knapsack problem . knapsack problem : :    is defined by :    +    * input : @xmath60 pairs of non - negative integers ,    @xmath67 and a positive integer    @xmath68 , @xmath69 represents the weight of the    @xmath51th item and @xmath70 represents the value of    the @xmath51th item . @xmath68 is the volume of the    knapsack . * output : @xmath71 , such that    @xmath72 is maximized with respect to    @xmath73 . simple knapsack problem : :    is defined by :    +    * input : @xmath60 non - negative integers    @xmath74 and a positive integer @xmath68 ,    @xmath69 is the weight and value of the @xmath51th    item and @xmath68 is the volume of the knapsack . * output : @xmath71 , such that    @xmath75 is maximized with respect to    @xmath73 . both problems are np complete , we will consider only the simple knapsack problem , and denote a simple knapsack problem with @xmath60 items and volume of @xmath68 with @xmath76 . m.alekhnovich et . al @xcite have proved the following theorem :    for simple knapsack problem ( n , n ) , the time complexity of any adaptive bt algorithms is at least @xmath77    we will improve this lower bound using the same technique as the previous work , by optimizing related parameters , formally :    for simple knapsack problem ( n , n ) , the time complexity of any adaptive bt algorithms is at least @xmath78 where @xmath79 is any small positive number . _ proof _ : consider positive numbers @xmath80 satisfying @xmath81 , then @xmath82 , so we can choose another positive number @xmath83 that satisfies @xmath84 and @xmath85 . these parameters will be fixed later to optimize the lower bound . let @xmath68 be some large integer , our initial set of items are integers in @xmath86 . solver takes the first @xmath87 items one by one , and following each one , adversary applies the following rules to remove certain items from future consideration : remove all items that are the difference of the sums of two subsets already seen ; also remove all items that complete any subset to exactly @xmath68 ( ie all items with value @xmath88 , where @xmath19 is a subset of the items considered so far ) . these rules guarantee that at any point , no two subsets will generate the same sum , and that no subset will sum to @xmath68 . also notice that this eliminates at most @xmath89 numbers . to know why , the difference of the sums of any two subsets can be represented as a weighted sum of the numbers seen so far , with three possible weights : 1 , 0 and -1 , so the number of distinct differences of any two subsets is at most @xmath89 ; the number of distinct values that complete any subset to exactly @xmath68 is even less ( @xmath90 ) , thus can be omitted here . so we will never exhaust the range from which solver can pick the next item provided that @xmath91 . call the set of numbers chosen so far @xmath9 and consider any subset @xmath92 contained in @xmath9 of size @xmath93 . our goal is to show that @xmath92 is indispensable ; that is , we want to construct a set @xmath94 of size @xmath95 , consisting of numbers in the feasible input with the following properties .    1 .   @xmath96 . 2 .   @xmath97 does not contain other subsets that sum to @xmath68 . the above properties indeed imply that @xmath92 is indispensable since obviously there is a unique solution with optimal value @xmath68 and , in order to get it , @xmath92 is the subset that must be chosen among the elements of @xmath9 . we thus get a lower bound on the width of the computation tree of any adaptive bt , which is the number of subsets of size @xmath93 in @xmath9 ; namely @xmath98 . below is a diagram of such construction .        for any @xmath99 , let @xmath100 , @xmath101 , @xmath102 $ ] . we show that @xmath103 . note that numbers in @xmath92 are less than @xmath104 , so @xmath105 , the last step follows from @xmath85 and @xmath106 ; and @xmath107 , the last step follows from @xmath84 and @xmath106 .    to construct @xmath108 , first choose @xmath109 items in @xmath110 . after each choice , we will remove some items from the remaining by the following rules . let @xmath19 be the set of items currently in @xmath97 .    1 .   for all @xmath111 , remove items of value @xmath112 . 2 .   for all @xmath113 , remove items of value @xmath114 .    since @xmath100 , we can always avoid the points that need to be eliminated , and sum to a number @xmath115 so that @xmath116 . this can be done by iteratively picking numbers bigger / smaller than @xmath57 according to whether they average to below / above @xmath57 currently .    to complete we need to pick two more items @xmath117 that sum to @xmath118 , and so that they are not the difference of sums of any two subsets of the @xmath119 items picked so far . assume for simplicity that @xmath120 is an integer . of the @xmath121 pairs @xmath122 , where @xmath123 , at least one pair @xmath124 will suffice . ( note that , since @xmath125 , the smallest number is @xmath126 , and the largest number is @xmath127 , provided that @xmath68 is sufficiently large . so we will never go beyond the range of @xmath128 . ) now it has @xmath96 , the only thing left is to prove there does not exist another subset which also sums to @xmath68 . suppose for contradiction @xmath19 is such a subset , namely @xmath129 , following are three cases :    1 . neither @xmath130 nor @xmath131 belong to @xmath19 , contradictary to the second rule when picking the first @xmath119 items . both @xmath130 and @xmath131 belong to @xmath19 , by comparing @xmath19 and @xmath132 , we get two subsets of the first @xmath119 items that sum equally , contradictary to the first rule . 3 . exactly one of @xmath130 and @xmath131 belong to @xmath19 , by comparing @xmath19 and @xmath132 , we find that @xmath130 or @xmath131 is equal to the difference of the sums of some two subsets of the first @xmath119 items , contradiction . the rest of the proof is about maximizing the lower bound : @xmath98 , subject to @xmath133 and @xmath81 .    according to stirling formula , the target function can be simplified : @xmath134    by applying logorithm transform , our goal is equivalent to maximize : @xmath135 subject to @xmath133 and @xmath136 . note that for convenience , we allow @xmath137 here , the case will be handled later . take partial differential on @xmath138 , which is : @xmath139    so @xmath140 is strictly increasing respect to @xmath138 , since @xmath141 , by setting @xmath138 to @xmath142 , we only need to maximize : @xmath143    whose differential is : @xmath144    the only root of the above function that lies in @xmath145 is @xmath146 , which maximizes @xmath147 , thus @xmath148 . so @xmath138 can be arbitrarily close to @xmath149 , and the maximum value of @xmath150 is @xmath151 by substitution , where @xmath79 is any small positive number . consequently , the optimal lower bound @xmath98 is : @xmath152 backtracking is an important algorithmic scheme which is pervasive in solving hard problems such as propositional satisfiability problem ( sat ) and constraint satisfaction problem ( csp ) . proving lower bounds for these problems under bt model will both deepen our understanding of the structure and properties of these hard problems and guide our designing of algorithms to solve these problems . an exponential time lower bound for sat under fully adaptive bt model has already appeared in @xcite . recently , xu and li have proven an exponential lower bound for a class of random csps ( model rb ) under tree - like resolution @xcite . since tree - like resolution has a close tie with dpll , a famous backtracking search strategy for sat with corresponding exponential time lower bound in @xcite , it is natural to investigate the time complexity of some class of random csps ( rb model ) under bt model , and we expect that this future work may produce the first exponential time lower bound for some class of random csps under bt model . we thank professor ke xu for joining our discussion and providing helpful comments . a.borodin , a.magen , j.buresh-oppenheim , m.alekhnovich , r.impagliazzo and t.pitassi : toward a model for backtracking and dynamic programming , proceedings of 20th annual ieee conference on computational complexity ( 2005 ) 308 - 322 xin li , tian liu , han peng , liyan qian , hongtao sun , jin xu , ke xu and jiaqi zhu : improved exponential time lower bound of knapsack problem under bt model , proceedings of fourth annual conference on theory and applications of models of computation ( 2007 ) 624 - 631 p.pudlak : proofs as games . american math . monthly , 23 ( 2000 ) 541 - 550 d.itsykson , e.hirsch and m.alekhnovich : exponential lower bounds for the running time of dpll algorithms on satisfiable formulas , proceedings of 31st international colloquium on automata , languages and programming ( 2004 ) 84 - 96 ke xu , wei li : many hard examples in exact phase transitions , theoretical computer science , 355 ( 2006 ) 291 - 302 a.borodin , c.rackoff and m.nielson : ( incremental ) priority algorithms , algorithmica , 37 ( 2003 ) 295 - 326 g.woeginger : when does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme ( fptas ) ? informs journal on computing , 12 ( 200 ) 57 - 75 a.borodin : further reflections on a theory for basic algorithms , proceedings of second annual conference on algorithmic aspects in information and management ( 2006 ) 1 - 9
m.aleknovich et al . have recently proposed a model of algorithms , called bt model , which generalizes both the priority model of borodin , nielson and rackoff , as well as a simple dynamic programming model by woeginger . 
 bt model can be further divided into three kinds of fixed , adaptive and fully adaptive ones . 
 they have proved exponential time lower bounds of exact and approximation algorithms under adaptive bt model for knapsack problem . 
 their exact lower bound is @xmath0 , in this paper , we slightly improve the exact lower bound to about @xmath1 , by the same technique , with related parameters optimized .