(k，s)-SAT是命题满足性问题限制在一类特殊的命题公式上，该命题公式具有每个子句只有k个不同的文字且每个变元出现的次数少于s次的特点。已经验明对于正整数k，s，存在一个指数函数f，满足：对任意s≤f(k)，所有的(k，s)-SAT例都是可满足的，而(k，f(k)+1)-SAT却是一个NP—完全问题。于是我们称f(.)为关于(k，s)-SAT的临界函数。到目前为止，只知道f(3)和f(4)的精确值。对于f(.)是否可计算是一个仍未解决的问题。因此，对该临界函数的上下界研究是具有理论意义的。目前，关于f(.)的最好上下界分别为Ω(2k/k)和O(2k/ka)，其中α=log43-1≈0.26。 由于每个满足某种条件的数值序列(阶梯序列)对应一个MU(1)中的公式，在文献[SS]中，S.Hoory和S.Sezider通过对数值序列的运算来构造(k，s)-CNF中的MU(1)公式例，从而得到了函数f(.)的可计算上界函数。但该方法是不确定的且不太实用。 本文主要有以下两方面贡献： (1)在临界函数的上界方面，基于文献[SS]的思想，本文提出了一个树规则以及基于该规则的计算上界的确定性算法。该树规则可以显著的减少阶梯数值序列的计算步骤，这使得新算法比文献[SS]的算法更实用。而得到的界却能接近文献[SS]所得的。此外，运用该算法，得到了一些NP—完全问题类。 (2)在临界函数的下界方面，本文提出了一个随机算法。对于任意一个(k，*)-CNF中的公式，该算法能随机产生一个赋值。再通过运用概率方法(Probabilisticmethod)及局部引理(LovászLocalLemma)，本文证明了，对任意(k，*)-CNF中的公式，如果该公式的子句数小于0.58√k/lnk2k，则公式是可满足的。同时还得到了临界函数f(.)的新下界Ω(√j/lnk2k/k。