M.Alekhnovich等人最近提出了一种覆盖了贪心法、回溯法和简单动态规划法的算法模型，称为BT模型，证明了一些NP完全问题的精确算法和近似算法在这个模型下的指数时间下界(M.Alekhovich，A.Borodin，J.Buresh-Oppenheim，R.Impagliazzo，A.Magen，andT.Pitassi，TowardaModelforBacktrackingandDynamicProgramming，ProceedingsofTwentiethAnnualIEEEConferenceonComputationalComplexity，pp308-322，2005)。本文在M.Alekhnovich等人的模型和下界证明方法的基础上，通过给出新的具体构造获得了一些新的结果，首先改进了他们关于NP完全的背包问题在动态BT模型下的指数时间下界，然后证明了NP完全的最大割、最小支配集、最大独立集问题在固定BT模型下的指数时间下界，最后证明了属于P的边覆盖问题在固定BT模型下的指数时间下界。本文获得的具体结果如下： (1)背包问题 ·对于简单背包问题(物品价值与重量相等)的精确算法，设物品数为n，背包容量为正整数N，对于任意的0＜∈≤1/2，存在正整数N0，使得N＞N0时，任何动态BT算法的时间复杂性下界是Ω(2(2-∈)n/3/√n)≈Ω(20.66n/√n)，M.Alekhnovich等人原来的结果是Ω(2n/2/√n)=Ω(20.5n/√n)。 ·对于简单背包问题的近似算法，要获得1-∈的近似比，任何动态BT算法的时间复杂性下界是Ω((1/∈)1/2.38)≈Ω((1/∈)0.420)，M.Alekhnovich等人原来的结果是Ω((1/∈)1/3.17)≈Ω((1/∈)0.315)。 (2)最大割问题 ·对于n个顶点无向图最大割问题的精确算法，任何固定BT算法的时间复杂性下界是Ω(2(「)n/18」)。 ·对于n个顶点无向图最大割问题的近似算法，对于任意0＜∈＜1/18，存在N＞0，使得对于任意的n＞N，任何固定BT算法都需要Ω(e4.50∈2n)的时间才能获得17/18+∈的近似比。 (3)最小支配集问题 ·对于n个顶点无向图最小支配集问题的精确算法，任何固定BT算法的时间复杂性下界是Ω(2(「)n/19」)。 ·对于n个顶点无向图最小支配集问题的近似算法，对于任意0＜∈＜1/14，存在N＞0，使得对于任意的n＞N，任何固定BT算法都需要Ω(e2.58∈2n)的时间才能获得15/14-∈的近似比。 (4)最大独立集问题 ·对于n个顶点无向图最大独立集问题的精确算法，任何固定BT算法的时间复杂性下界是Ω(2(「)n/17」)。 ·对于n个顶点无向图最大独立集问题的近似算法，对于任意0＜∈＜1/18，存在N＞0，使得对于任意的n＞N，任何固定BT算法都需要Ω(e4.77∈2n)的时间才能获得17/18+∈的近似比。 (5)最小边覆盖问题 ·对于n个顶点无向图最小边覆盖问题的精确算法，如果BT算法的每个数据项表示一条边及其两个端点，则任何固定BT算法的时间复杂性下界是Ω(2(「)n/6」)。 ·对于n个顶点无向图最小边覆盖问题的精确算法，如果BT算法的每个数据项表示一个顶点及其相邻顶点，则任何固定BT算法的时间复杂性下界是Ω(2(「)n/18」)。 上述结果中，(1)是对已有结果的改进，(2)～(5)是新的结果。