Exponential Time Algorithms Of Knapsack And Constraint Satisfaction Problem

In this thesis, we study the analysis of exponential time algorithms for some intractable problems. After the brief introduction to the basic concepts of computational complexity and NP-complete problems, this paper then gives short retrospect of recent developments in the area of various computation models and exponential time algorithms. In chapters 2&3, two major results established in the author's post-graduate period are presented in details. First result is a proof of the Knapsack problem's exponential lower bound under BT model, where the second result is a DPLL-like algorithm for the CSP problem and its non-trivial exponential upper bound. The actual results are:1. Algorithmic model lower boundFor the Simple Knapsack problem (which items have equal value and weight), let n be the number of items, then for any positive real numberε, every adaptive BT algorithm has running time lower bounded byΩ. The result of M.Aleknovich et al. isΩ.2. Algorithm upper boundFor DPLL-like algorithms of the k-CSP problem, let n be the number of variables, d be the size of each variable's domain. If d is constant, then the algorithm's running time is upper bounded by O ; if d varies, consider the case of d = nα: ifα≤1, then the upper bound is ; ifα> 1, the upper bound is , here O? means there is a factor at most polynomial in n.