导读:本文包含了判定问题的复杂性论文开题报告文献综述及选题提纲参考文献，主要关键词:线性公式,满足性,NP-完全性,极小不可满足公式
判定问题的复杂性论文文献综述
李培培[1]（2008）在《线性公式可满足性判定问题的复杂性》一文中研究指出可满足性问题(Satisfiability Problem，简称SAT)是计算机科学的中心问题之一，也是第一个被证明的NP-完全问题，并且是一大类NP-完全问题的核心。SAT问题是指可满足布尔表达式的集合，它在数理逻辑、人工智能、约束可满足性问题、VLSI集成电路设计与检测、计算机科学理论、计算机视觉、机器定理证明、机器人规划、机器学习等领域具有广阔的应用背景。一个CNF公式F称为线性的，如果F中任意两个不同的子句中至多包含一个相同的变元。一个CNF公式F称为严格线性的，如果F中任两个不同的子句恰好包含一个相同的变元。所有严格线性公式是可满足的([33]S．Porschen etc．，2006)。对于线性公式类LCNF，判定问题LSAT是NP-完全的。对于LCNF的子类LCNF_(≥k)(其公式中每个子句的长度至少为k)，如果在LCNF_(≥k)公式中存在一个不可满足公式，则判定问题LSAT_(≥k)是NP-完全的([31，32]S．Porschen，E．Speckenmeyer，2006)。因此，对于LCNF_(≥k)(k≥3)公式，判定问题LSAT_(≥k)的NP-完全性取决于在LCNF_(≥k)公式中是否存在不可满足公式。在([31，32]S．Porschen，E．Speckenmeyer，2006)中，通过构造超图和拉丁方阵，已经证明了LCNF_(≥3)和LCNF_(≥4)都包含不可满足公式，并提出了一个公开问题：当k≥5时，在LCNF_(≥k)公式中是否存在不可满足公式。本文基于线性公式的结构与特点，提出了线性化算法，使用该算法可以在|F|多项式时间内把任一公式F转化为线性公式F~(lin)，且两者有相同的可满足性。另外，本文通过研究极小不可满足公式在公式归约中的应用，给出了在k-LCNF(其公式中每个子句的长度都为k，k≥3)公式中构造不可满足公式的一般方法。证明了：对每个k≥3，k-LCNF公式中存在极小不可满足公式，并且证明了下面更强的结果：对每个k≥3，k-LSAT是NP-完全的。(本文来源于《贵州大学》期刊2008-05-01）
高随祥,杨德庄[2]（2002）在《布尔函数的判定树复杂性及问题(英文)》一文中研究指出设f（x1,x2,…,xn）是一个布尔函数。如果计算f（x1,x2,…,xn）的每个判定树算法在最坏情况下都要检查所有n个变量才能求得f的值,则称f是诡秘函数。1988年,A.C.C.Yao提出一个问题:如果一个单调非平凡的布尔函数f（x1,x2,…,xn）在循环群Cm×Cn的直积的可迁作用下不变,则f是诡秘的吗?对这个问题的肯定回答支持着名的Rivest-Vuillemin猜想.本文将部分地解答这一问题.(本文来源于《数学研究与评论》期刊2002年04期）
杨青[3]（1995）在《多项式族(系数仿射依赖于参数的情形)稳定性判定的计算复杂性问题的解决和多项式算法研究》一文中研究指出本文通过将仿射型参数摄动的多项式稳定性问题化为一个单参数的秩2半正定简单二次规划问题,利用二次规划的理论,证明了此问题不是NP-完全的, 并给出了一个多项式时间算法,从而解决了长期困扰人们的组合爆炸问题(本文来源于《1995年中国控制会议论文集（上）》期刊1995-10-01）
判定问题的复杂性论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
设f（x1,x2,…,xn）是一个布尔函数。如果计算f（x1,x2,…,xn）的每个判定树算法在最坏情况下都要检查所有n个变量才能求得f的值,则称f是诡秘函数。1988年,A.C.C.Yao提出一个问题:如果一个单调非平凡的布尔函数f（x1,x2,…,xn）在循环群Cm×Cn的直积的可迁作用下不变,则f是诡秘的吗?对这个问题的肯定回答支持着名的Rivest-Vuillemin猜想.本文将部分地解答这一问题.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
判定问题的复杂性论文参考文献
[1].李培培.线性公式可满足性判定问题的复杂性[D].贵州大学.2008
[2].高随祥,杨德庄.布尔函数的判定树复杂性及问题(英文)[J].数学研究与评论.2002
[3].杨青.多项式族(系数仿射依赖于参数的情形)稳定性判定的计算复杂性问题的解决和多项式算法研究[C].1995年中国控制会议论文集（上）.1995