论文部分内容阅读
该文内容包括两个部分分别是关于非确定怀函数类和SAT的结构性质.本质上该文研究非确定性多项式时间问题类NP的搜索问题的计算揽杂性.上述两个部分的内容研究的 分别是NP非完全集和NP完全集.为了研究各种NP非完全集搜索问题的复杂性,该文分 别定义了对应于NP和NP子类FewP和UP非确定性函数类,并且定义了求解各种NP搜索问 题的函数类.该文研究了前一类函数类之间的包含关系和复合关系.证明在这些类中 有一个新类是FewP的对应物.该文研究了后一类函数类之间的包含关系和归约关系. 提出了关于其中一个类的一个猜想.这些结果对于理解各种NP非完全问题的搜索问题 的复杂性是重要的,因为它们提供了比较和分类各种NP非完全集搜索问题的复杂性的 框架.关于NP完全集搜索问题的复杂性,最重要的假设是`SAT是多项式时间并行地搜 索归约为判定的假设.因为用现有的证明技术不可能绝对地解决这个假设,该文研究了这个假设与其他SAT结构性质的假设之间的关系,证明了如果`NP有多项式时间图灵 归约下的稀疏完全集则`SAT是多项式时间并行地搜索归约为判定,以及如果假设`P 不等于NP,则要么`SAT不是多项式时间并行地搜索归判定,要么`SAT不能用多项式 时间真值表归约归约为有界可近似集.并且证明假设`P不等于NP,则`NP在多项式时间析取归约下没有稀疏完全集.这些各SAT难解决的假设之间建立联系,推进了对于SAT的结构性质和对于NP完全问题的搜索问题的复杂性的知识,是使用目前的证明技术 所能够设想的最佳研究路线.这些结论对于所有NP完全集都是适用的.证明这些结论 的关键引理是`NP稀疏集是可以用多项式时间并行查询SAT所计算的函数来打印的.该引理改进了过去关于稀疏NP集的可打印性结果.该文的第二部分还用集合类代替函数 类研究了对可挑选性的扩充定义,证明了对于文献中已知的一些扩充定义,这两种方 法给出相同结果.