检索结果-内蒙古大学图书馆

自从Steve Cook证明了第一个NP完全问题以来,大量的NP完全问题不断被发现,而且很多问题具有重要的实际应用。比如,SAT问题是大规模集成电路自动布线和人工智能领域的关键问题,着色问题在组合优化、规划调度等方面有着广泛应用,子图同构问题是模式匹配中的核心问题,子集和问题可以应用于公钥加密。是否存在能够多项式时间内求解NP完全问题的确定性算法(即是否NP=P),是理论计算机领域多年悬而未决的难题。无论NP=P抑或NP≠P,对NP完全问题的研究都能促进人们加深对此类问题乃至人类思维过程的理解。近年来越来越多的学者开始从算法的实用性角度质疑P与NP问题的价值,比如Knuth就指出,“就算NP=P,仅仅知道一个问题有多项式时间算法是没有实际意义的,因为那个指数可能大得超过计算能力,因此也许我们从一开始就不应该提出P与NP这个糟糕的问题。”[56]尽管如此,P与NP问题作为千禧年七大难题之一仍然是理论计算机科学的圣杯[57]。近几年,每每有人提出P与NP问题的证明,总能引起学界和社会上的热烈讨论,这足以说明人们依然十分关注这一基本问题的研究动向。P与NP问题看起来很容易却又难以着手,每当人们以为即将解决它时却又发现总因遇到绕不过的障碍而不得不回到原点。这导致了这一问题提出近50年至今仍然没有太大进展。文献[1]针对一种称为msp问题的新的NP完全问题,提出了一种名叫Z-H算法的多项式时间求解方案,为NP完全问题的研究提供了新的着力点。相关结果已于2010年向Transactions on Algorithms投稿,评审至今没有发现问题。自2010年下半年至2014年上半年,已产生了5300万例msp问题随机实例以测试Z-H算法,无一出错。但是,当前对于msp问题的NP完全性研究工作还刚刚起步;而且目前Z-H算法只能求解小型实例,如何对算法进行充分测试成为难题。本文依托国家自然科学基金项目“NP完全问题求解复杂性研究”,从多个角度深入研究msp问题的特性,并在此基础上设计了大量针对Z-H算法的测试方案。主要工作如下:1.基于问题归结研究了msp问题与SAT、着色、子图同构、哈密顿回路、团、子集和问题的对应关系(其中子图同构和子集和问题的归结是第一次给出),揭示msp问题所反映的NP完全问题的共性及其作为NP完全性模型的强大表达力,为利用其他NP完全问题迥异的实例结构深入测试Z-H算法作了铺垫。2.通过实验观察到了msp问题在特定区域上有解实例比例和Z-H算法平均求解时间的相变现象。这是继回溯、概率搜索等算法之后,又一种新的算法框架被发现存在相变,印证了相变属于问题内在属性而与算法无关的猜想[61]。确定了msp问题的相变序参量和相变点,初步估计了解的存在性临界值。利用msp问题的相变模型,能够对Z-H算法作进一步测试。3.由于Z-H算法思想基于直觉形象而非分析解构,针对具体多级图实例的Z-H算法执行过程(特别是Change算子)非常复杂,每一步操作的边数之多使得想要通过机械地人工计算来摸透算法内涵几乎不可能,因此以往的研究都只能笼统地给出算法的大致思想而没能分析具体实例[54,55]。本文利用鸽笼公式实例的良好结构特性以及从SAT问题到msp问题的归结,结合手工推导和机器计算,第一次清晰地给出了较大问题规模下的算法运行特征分析。4.反复研读、推敲和讨论了Z-H算法的正确性证明。提出了针对撕裂证明的实例合并测试方法。实验证明已经测试多年的现有代码[1,55,62]存在漏洞,从而表明了合并测试方法的有效性。依据已有的严格数学证明[1],我们认为Z-H算法本身仍然是正确的。5.设计实现了基于Z-H算法的NP完全问题通用求解器。一方面可以用来求解多类NP完全问题;更重要的是,以往的Z-H算法测试都是针对小规模的随机msp实例,利用上述问题求解器,可以利用归结、相变和合并构造等对Z-H算法进行更大强度的测试。在本文作者的课题组和北航许可教授的努力下,共同完成了以上测试。

关键词： msp问题 NP完全问题归结相变

来源：评论

学校读者我要写书评

暂无评论

SAT问题可多项式归结到msp问题

引用

计算机科学 2012年第11期39卷 179-182页

作者：樊硕姜新文国防科技大学计算机学院长沙410073

针对文献[1]中提出的msp问题(定义见正文),从SAT问题出发,给出SAT问题到msp问题的多项式归结,进而给出msp问题NP完全性质的另一种证明。

关键词： msp问题 SAT问题多项式归结 NP完全性

来源：评论

学校读者我要写书评

暂无评论

msp问题的一个求解算法

引用

计算技术与自动化 2016年第1期35卷 60-70页

作者：姜新文吴添君李鹏坤樊硕周泰杨魏登萍国防科技大学计算机学院湖南长沙410073

msp问题是文献[1,2]提出的一个问题。研究表明[3]该问题对NP类问题有很强的表达能力。本文给出一个关于该问题的求解算法、复杂性分析,以及正确性证明。本文对于NP完全问题研究有重要意义。

关键词：算法 msp问题算法设计复杂性

来源：评论

学校读者我要写书评

暂无评论

求解msp问题的ZH算法正确性证明研究

求解MSP问题的ZH算法正确性证明研究

引用

作者：李鹏坤国防科学技术大学

学位级别：硕士

P ***问题一直是理论计算机科学领域中最为复杂的一个问题,已经被列为世界七大数学难题之首。P ***问题已经吸引了世界上许多学者对其研究,但遗憾的是,仍然未获得被广泛认可的结论。在P ***问题的研究中,对NP完全问题的探索是一个关键... 详细信息

P ***问题一直是理论计算机科学领域中最为复杂的一个问题,已经被列为世界七大数学难题之首。P ***问题已经吸引了世界上许多学者对其研究,但遗憾的是,仍然未获得被广泛认可的结论。在P ***问题的研究中,对NP完全问题的探索是一个关键突破口。它不仅为证明P和NP的关系奠定了基础,而且对许多科学和应用领域具有深远的影响。本论文的研究正是以一个NP完全问题——msp问题为基础开展的。本文以文献[1]为基础进一步对msp问题进行研究,主要工作包括:1.给出更加详细的证明过程。文献[1]更加关注的是证明的思想和框架,因此没有给出关于算法正确性证明的全部细节。本论文把重心放在算法正确性证明的研究上,关注证明的每一个细节,最终给出关于算法正确性证明的详细过程。2.总结和证明算法的若干性质。在对求解msp问题算法的分析中,通过剖析算法的主要过程,进而获得并证明了算法的两条重要性质——顶点边集守恒性质和顶点边集存在性质。3.对msp问题及其求解算法进行新的理解和解读,发现一些新的性质,从新的角度解读了算法的过程和作用。本文给出的关于求解msp问题的算法正确性的详细证明进一步验证了算法的正确性,新性质的扩展发现以及对算法过程和作用的新视角分析也为msp问题的研究提供重要参考,并为该问题研究的进一步改进提供重要帮助。

关键词： NP完全问题 msp问题算法分析多项式算法正确性证明

来源：评论

学校读者我要写书评

暂无评论

特殊形式和结构的msp问题的求解研究

特殊形式和结构的MSP问题的求解研究

引用

作者：马兰湘潭大学

学位级别：硕士

自Steve Cook证明了第一个NP完全问题以来,众多的NP完全问题被陆续发现。目前,以SAT问题为根节点,四千多个NP完全问题已经形成了一棵巨大的归结树。NP完全问题遍布人工智能、数据库、程序语言、计算机网络等计算机科学领域,其研究具有... 详细信息

自Steve Cook证明了第一个NP完全问题以来,众多的NP完全问题被陆续发现。目前,以SAT问题为根节点,四千多个NP完全问题已经形成了一棵巨大的归结树。NP完全问题遍布人工智能、数据库、程序语言、计算机网络等计算机科学领域,其研究具有重要的研究意义和应用价值。本文针对一个NP完全问题,即msp问题,研究其结构性质,猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引,从定义、算法、证明、归结等角度多方面深入理解msp问题的特性,提出一种特殊形式和结构的msp问题。类比对SAT问题开展研究时,同样开展特殊结构的2-SAT问题、3-SAT问题、k-SAT、max-SAT问题研究,特殊形式和结构的msp问题同样具有重要意义,并能进一步推动原问题的研究。提出的课题依托了“NP完全问题求解复杂性研究”这一国家自然科学基金项目。本文的主要工作如下:1.首先介绍了msp问题的定义和相关概念。详细说明了ZH算法的步骤和各个算子的功能。将SAT问题归结到msp问题。2.从特殊形式的角度侧面研究msp问题,提出一种特殊形式和结构的msp问题。并在此基础上说明特殊结构的特殊意义。还证明了特殊结构和形式的msp问题的NP完全性。3.将ZH算法应用于本文提出的特殊结构msp问题求解,给出了新的证明。针对特殊结构msp问题求解算法的新的证明中,简化图的输入条件,使得部分结论的证明更加简单。4.对ZH算法求解特殊结构msp问题的正确性证明进行了实验验证。具体做法是,对产生的特殊结构的msp问题的问题实例进行求解,同时与回溯法进行比较,验证算法的正确性。

关键词： msp问题多项式归结 NP完全问题

来源：评论

学校读者我要写书评

暂无评论

msp问题及其求解研究

引用

计算技术与自动化 2006年第4期25卷 145-159页

作者：姜新文国防科技大学计算机学院湖南长沙410073

提出多级图简单路径求解问题,我们称之为msp问题.给出求解该问题的Z-H算法,证明算法的正确性,分析算法的时间复杂性.最后通过将HC问题(哈密顿图判定问题)多项式归结成msp问题,证明msp问题的NP完全性质.结论是:msp∈P,HC∈P.

关键词：算法 msp问题 HC问题 NP问题 NP完全问题

来源：评论

学校读者我要写书评

暂无评论

msp问题及其求解研究

MSP问题及其求解研究

引用

中南六省（区）自动化学会第24届学术年会

作者：姜新文国防科技大学计算机学院

提出多级图简单路径求解问题,我们称之为msp问题。给出求解该问题的Z算法,证明算法的正确性,分析算法的时间复杂性。最后通过将HC问题（哈密顿图判定问题）多项式归结成msp问题, 证明msp问题的NP完全性质。结论是:msp∈P,HC∈P。

关键词：算法 msp问题 HC问题 NP问题 NP完全问题

来源：评论

学校读者我要写书评

暂无评论

特殊形式和结构的msp问题NP完全性研究

引用

计算技术与自动化 2021年第3期40卷 78-83页

作者：马兰刘新朱哲湘潭大学计算机学院网络空间安全学院湖南湘潭411105

针对一个NP完全问题,即msp问题,研究其问题的结构性质,猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引,提出一种特殊形式和结构的msp问题。而约束了形状的特殊形式和结构的msp问题如果不具备NP完全性,会极大影响进一步简化... 详细信息

针对一个NP完全问题,即msp问题,研究其问题的结构性质,猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引,提出一种特殊形式和结构的msp问题。而约束了形状的特殊形式和结构的msp问题如果不具备NP完全性,会极大影响进一步简化算法证明的研究意义。因此,提出的特殊形式和结构的msp问题进行了NP完全性质证明。类比对SAT问题开展研究时,同样开展特殊结构的2-SAT问题、3-SAT问题、k-SAT、max-SAT问题研究,特殊形式和结构的msp问题同样具有重要意义,并进一步推动原问题的研究。

关键词： msp问题多项式归结 NP完全性

来源：评论

学校读者我要写书评

暂无评论

哈密顿图判定问题的多项式时间算法

引用

计算机科学 2020年第7期47卷 8-20页

作者：姜新文湘潭大学计算机学院·网络空间安全学院湖南湘潭411105 国防科技大学计算机学院长沙410073 智能计算和信息处理教育部重点实验室湖南湘潭411105

NP=?P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困难问题之首,2005年Science将其列为25个困难问题之19。Science最近列出的125个亟待解决的重要问题中,第19个问题实质上就是NP=?P的... 详细信息

NP=?P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困难问题之首,2005年Science将其列为25个困难问题之19。Science最近列出的125个亟待解决的重要问题中,第19个问题实质上就是NP=?P的问题。如果NP=P,对于很多困扰科学研究的困难计算问题,理论上就存在多项式时间算法来迅速求解它们。而现代密码学建立在NP≠P的假设之上。人们希望存在难解问题,希望基于难解问题构造加密算法,希望能够利用难解问题的求解复杂性对抗分析和攻击。如果NP=P,所有在NP≠P假定之上开展的计算研究都至少需要重新审视其意义。NP完全问题的求解复杂性决定NP=P是否成立。针对一个被称为msp问题的新问题,文中提出了一个关于msp问题的多项式时间算法,并给出了该算法的证明和时间复杂性分析。由于已经发表了十多个经典的NP完全问题到msp问题的归结以及msp问题到SAT问题的归结,因此msp问题存在多项式时间算法这样一个研究结果对于研究NP=P有重要和积极的意义。

关键词： msp问题 HC问题 NP完全问题多项式时间算法

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：