从1972年发现NP-完全性以来，很多学者就对NP-难的优化问题能否有快速算法来计算其近似解感兴趣，然而对大部分这类问题，寻求有效的近似算法都令人失望。于是尝试来证明求其近似解也是NP-难的，但除了极少个例成功之外就陷入停滞,并且发现传统的Cook-Levin类型的归约技术并不能用来证明这类问题。直到1992年，由Arora等人发现了PCP定理，给出了NP类的一个新特性，并提供了关于归约技术的一个新的起点，是极为令人震惊的。由PCP定理出发，可以得出很多NP-难的优化问题，计算其近似解与计算其精确解具有同样的难度，因而除非P=NP，否则不可能有多项式时间算法来求解。可以说，PCP理论是近20年来复杂性理论的重要成果之一，它是近似算法理论发展史上的一座里程碑。它对证明NP难优化问题的不可近似性起到了关键性的作用。　　本文应用PCP理论，对线性公式类LCNF及(k,s)-CNF公式类的NP完全性及其间隙问题的复杂性进行了研究。对(k,s)-ksCNF公式类的临界函数下界的估计进行了探讨，主要作了以下工作：　　(1)考虑线性公式类LCNF，即公式中的任意两个子句最多只有一个公共变元。LSAT为LCNF的满足性判定问题，用间隙归约技术证明了MAX-LSAT属于第二类不可近似问题，即存在正数ε>0,MAX-LSAT要想取得近似比为1ε+的近似解是NP-难的。进一步讨论了LCNF公式类的子类：k-LCNF，即其公式的每个子句的长度都是k，证明了对k≥3,MAX-k-LSAT≥也属于第二类。　　(2)用极小不可满足公式和递归方法解决了S.Porschen等人在[PS06b]提出的开问题：对于k≥5，LCNF≥k中是否含有不可满足公式？这里LCNF≥k表示每个子句长度至少为k的线性公式构成的类。S.Porschen用超图和拉丁方的方法构造出了LCNF≥3和LCNF≥4中的不可满足公式，然而其方法过于复杂且不具有推广性。我们给出了一种一般的构造方法，即用递归的方法构造出了k-LCNF中的不可满足公式，因而证明了：对于k≥3，k-LCNF含有不可满足公式，得到了比Porschen中提出的问题更强的结论。　　(3)考虑(k,s)-CNF公式类，它是由每个子句长度为k，而每个变元出现的次数不超过s的CNF公式构成的类，而(k,s)-SAT为其满足性判定问题。证明了MAX-(3,4)-SAT属于第二类不可近似的优化问题。并证明了：如果(k,s)-SAT是NP-完全的，则MAX-(k,s))-SAT也属于第二类不可近似问题。　　(4)对(k,s)-SAT中的临界函数f(k)的界进行了研究。Kratochvil证明了：对每个k≥3，存在正整数s=f(k)，使得所有(k,s)-CNF中的公式都是可满足的；而(k,s+1)-CNF中存在不可满足公式，从而(k,s+1)-SAT是NP完全的。关于f(k)，其精确值目前只知道f(3)=3,f(4)=，对k=5,6,…,9，目前已经知道的最好结果由Hoory、Berman和Kratochvil等人得到如下：　　5≤f(5)≤7,7≤f(6)≤11,13≤f(7)≤17,24≤f(8)≤29,41≤f(9)≤51。　　而对于k≥10，只有一般的估计式，相关的估计结果极少见到。我们通过用Berman等人构造的函数（公式略）。　　它满足性质：对正整数k,d，如果存在x∈(0,1)，使得g(k,d,x)>1，则(k,d)-CNF中的每个公式都是可满足的。根据这个结果，结合函数作图，通过二分法或变步长搜索技术，对给定的正整数k，寻找存在x∈(0,1)，使函数g(k,d,x)>1的最大正整数d，把这个最大值d作为(f,k)的下界估计值，从而给出了寻求f(k)下界的一种方法。利用此方法，我们得出了k=10,11,…,20时f(k)有如下下界：　　f(10)≥75,f(11)≥136,f(12)≥251,f(13)≥463,f(14)≥860,f(15)≥1607,f(16)≥3013,f(17)≥5672,f(18)≥10715,f(19)≥20302,f(20)≥38574。　　根据这种方法，还可以找出更多的下界。