有限模型理论中,描述复杂性作为连接计算复杂性和定义在有限结构上的逻辑语言的桥梁,通过提供新的证明方法和额外的证据使得计算复杂性变得“自然”而不再是只能被特定的抽象机器定义.对于一些主要的计算复杂类,描述复杂性提供了相应的逻辑语言,以语义学的形式去定义他们.比如复杂类PH,在多项式层级内的所有复杂类集合,就可以被二阶逻辑语句精确地刻画.理论计算科学家们,在此研究领域上证明了诸多不同的复杂类可被相应的逻辑刻画.我们称这些逻辑语言与其相应的复杂类是相等的.因此,我们就可以借助逻辑知识来研究计算复杂类的某些性质.然而,并不是所有的问题都可被某一逻辑刻画.这些不能被逻辑语言刻画的问题都是十分重要且具有导向作用的例子.在计算复杂性理论中,一个著名的开放问题就是Pvs NP.那么这些重要的结果极有可能会导致计算复杂类的分离.因此逻辑的这种不可表达性已经被认为是有限模型理论的核心主题.就此,本文中我们将针对逻辑的不可表达性进行了扩展：在描述复杂性理论中,当结构是有序的时候,存在二阶逻辑ESO Π1Horn(当其一阶逻辑部分是全称Horn语句时),最小不动点逻辑加计数LFP+C,膨胀不动点逻辑加计数IFP+C和C∞ωω逻辑能够刻画计算复杂类P.在第二章我们将展现在结构层级上,线性规划问题(LP)却不能由ESO Π1Horn语句在有序结构上刻画.为证明这个结论,我们先引用Manyem[41]的一个结果,即目标函数约束(OFC)不能由ESOΠ1Horn表达式刻画.再通过一个反例来得到证明.我们也证明在结构层级上,通过逻辑归约方法,在无序结构中LP既不能被逻辑LFP+C,IFP+C刻画也不能被逻辑C∞ωω刻画.并且线性规划和整数规划的表达式是相同的.根据以上这些逻辑在LP问题上的不可表达性,我们提出了新的逻辑公式表达LP.另外,我们处理了二次规划问题的逻辑不可表达性,并证明在有序结构上,ESOΠ11Horn逻辑语句不能够表达二次规划问题,尽管当二次规划也属于复杂类P时.在第三章中我们将展现逻辑语句L∞ωωLFP和PFP在完美匹配问题上的不可表达性.这里我们应用的是数理逻辑的方法论之一：着色鹅卵石博弈(Pebble Games).本文的另一个重点是考虑到,在计算科学中,NP完全问题在区分可计算问题的复杂度类发挥着重大的作用,不仅是因为任意NP问题都可多项式时间归约到此类问题,而且若存在一个NP完全问题在确定图灵机多项式时间内可解,那么所有的NP问题都可在多项式时间内解决,现在广泛认为NP完全问题不存在多项式时间算法,尽管尚未有效地证明,但识别一个问题是否为NP完全问题已经显得尤为重要.在第四章中,我们介绍了如何从描述复杂性的角度研究组合优化问题的计算复杂性,并通过具体实例讲述一阶投射方法在证明NP完全性时的应用.这种通过逻辑归约的方法被证明是十分有用的：我们只需要很少的公式而不再是冗长的证明.与此同时,考虑到P问题本身就是多项式时间可解的,那么在P类问题中应用多项式时间归约是不合适的.然而逻辑归约方法在P问题的研究中发挥了重要作用,关于这点的讨论我们在第二章中已经体现：在应用一阶逻辑归约时,我们发现LFP+C,IFP+C和C∞ωω逻辑语言是不足够刻画P类问题的.