一阶逻辑归约与计算复杂性

在计算科学中,NP完全问题在区分可计算问题的复杂度类发挥着重大的作用,不仅是因为任意NP问题都可多项式时间归约到此类问题,而且若存在一个NP完全问题在确定图灵机多项式时间内可解,那么,所有的NP问题都可在多项式时间内解决.现在广泛认为NP完全问题不存在多项式时间算法,尽管尚未有效地证明,但识别一个问题是否为NP完全问题已经显得尤为重要.从描述复杂性角度阐述计算复杂性与逻辑之间的关联,通过具体实例:集合覆盖和控制集问题,讲述如何应用一阶投射方法证明一个NP问题的完全性.这种通过逻辑归约的方法被证明是十分有用的:只需要很少的公式而不再是冗长的证明.而逻辑归约的作用不仅在于此,在P类问题中应用逻辑归约时,发现计数最小不动点逻辑LFP+C,计数膨胀不动点逻辑IFP+C和C_(∞ω)~ω对P类问题的表达能力并不充分.     

关于相对化的P=?NP问题的注记

问题P=?NP在相对化后随外部信息集的不同可能有相反的答案.本文得出如下进一步的结果:1.存在着无穷个集合S₁,S₂,…,这些集合的复杂度依次严格上升,并且在它们分别地作为外部信息集合,能交替地使命题P=NP和P≠NP,相对比;2.存在着在NP类之外的递归集A,使得P=NP等价于P^A=NP^A.     

单体型装配问题及其算法

单核苷酸多态性(SNP)单体型装配问题就是从给定的来自某人染色体的SNP片段中去除错误,重构出尽可能与原来片段一致的单体型.这个问题有几个不同的模型最少片段去除(MFR)问题,最少SNP去除(MSR)问题以及最少错误纠正(MEC)问题.前两个问题的复杂性与算法已有一些学者研究过.第三个问题已被证明是NP完全问题,但这个问题的实际算法还没有.该文对MEC问题给出了一个分支定界算法,这个算法能得到问题的全局最优解.通过这个算法对实际数据的计算说明了MEC模型的合理性,即在一定条件下,通过修正最少的错误重构出的单体型确实是真实的单体型.由于分支定界算法对这样一个NP完全问题不能在可接受的时间内解规模较大的问题,文中又给出了求解MEC问题的两个基于动态聚类的算法,以便对规模较大的问题在可接受的时间内得到近似最优解.数值实际表明这两个算法很快,很有效.这两个算法总能得到与分支定界找到的全局最优解很接近的近似最优解.鉴于MEC问题是NP完全的,这两个算法是有效的、实际的算法.     

单台机以总完工时间为目标的批排序问题

研究单台机,工件加工时间相等,大小不同的批排序问题,给出了一个最坏情况界为9+3~(1/2)/6≈1.7817的多项式时间近似算法,并证明了即使工件总大小不超过2,该问题也不存在FPTAS,除非P=NP.     

O'下纯正多项式极小度的存在性

引言Homer 在中证明了在 P=NP 条件下可以证明 O′下纯正多项式极小度的存在性,他还证明了若干种 O″下的集不具有纯正多项式极小度.如果可以证明一切 O″下的集都不具有纯正极小度,那么可以证明 P≠NP。因此 Homer 的工作给出了一个解决“P=?NP”问题的一个可能途径.本文目的是在 P=NP 条件下证明在 O′下存在纯正多项式极小度.这样只须证明一切O′下的集都不具有纯正多项式极小度,则有 P≠NP.从而可以使证明 P≠NP 的这种途径     

NP完全问题多项式时间算法研究

本文从代数及组合两个方面论证了NP完全问题存在多项式时间算法 .以往利用线性规划 (LP)技术来分析NP完全问题中的TSP问题 ,因其存在子环游问题 ,从而使问题得不到有效解决 .文中发展一分层网络 ,在求解TSP问题时 ,存在另一类(不完全 )子环游问题 .但两模型允许解集的交集避免了两类子环游基本可行解 ,从而使TSP问题可利用LP技术多项式时间内得以解决 ,同时给出了求哈密尔顿回路的多项式标记证明方法 ,开创了NPC问题研究的新局面 .     

NP图灵完全集的一些性质

本文主要结果是:(1)P=NP 当且仅当一切 NP 图灵完全的无穷集组成一个非递归可表现的类;(2)NP=co-NP 当且仅当一切 NP 图灵完全集恰好组成一个多项式时间图灵等价类;(3)NP=co-NP 当且仅当 NP=P~(SAT).     

团剖分问题的复杂性

本文考虑分离图和树的平方图上团剖分问题的复杂性.文中的图均为无向简单图,团是指完备子图.分离图是指其点集可剖分为一个团和一个独立集之并的图.图 G 的团剖分是一组边不相重的团,它们包含了 G 的每条边.成员最少的团剖分叫做最小团部分.这个最小成员数叫做团剖分数,记为 CP(G).图的团剖分问题是 NP—完全的.本文的一个结果是证明了分离图上的团剖分问题仍保持,NP—完全性.     

议数学解题中的三个关键点——切入点、调节点与反思点

众所周知,数学是一门基础科学,任何一门自然科学和工程技术都离不开数学这一基础.而数学的产生和发展总是在提出问题和解决问题的过程中进行的.美国数学家哈尔莫斯(P.R.Hal mos)认为,问题是数学的心脏,数学的真正的组成部分是问题和解.著名数学家及数学教育家乔治.波利亚(G.Pol     

优化与生成——数学解题的价值取向

1 问题的提出 数学解题是数学学习与研究的基本活动.某种程度上说,数学学习与研究的过程就是解题的过程.数学家的解题往往是一个创造和发现的过程,作为学习的数学解题更多情况下是根据设计者预设目标进行的训练.通过训练,理解与探究数学的基本规律,使学习者学会像数学家那样"数学地思维".问题的设计或侧重已学知识的巩固,或关注学习者某方面能力的发展,通常表现为对数学结论的再发现过程.