NP完全性

作品数：20被引量：21H指数：4
导出分析报告
相关领域：自动化与计算机技术更多>>
相关作者：陈剑南姜新文周新民王志成柳先辉更多>>
相关机构：国防科学技术大学广州大学贵州大学扬州大学更多>>
相关期刊：《北京大学学报（自然科学版）》《计算机工程与应用》《广州大学学报（自然科学版）》《江西师范大学学报（自然科学版）》更多>>
相关基金：国家自然科学基金国家高技术研究发展计划上海市科学技术委员会资助项目国家科技支撑计划更多>>
-
在结果中检索

检索结果分析

结果分析中...
共 条 记 录，以下是1-10
全选清除导出
参考文献引证文献引用追踪
视图：
排序：
可满足性问题的精确算法和计算复杂性
《广州大学学报（自然科学版）》2023年第5期41-51,共11页陈建二 杨伟 
国家自然科学基金资助项目(61872097)。
可满足性(SAT)问题是计算机科学中最重要的理论研究和实际应用问题之一。文章从标准计算复杂性理论的角度论述SAT问题的精确算法和计算复杂性,主要论述算法的发展,分析算法(最坏情况)的复杂度,并探讨SAT问题的复杂度上限。对一些具有意...
关键词：可满足性 SAT算法 NP完全性 精确算法 计算复杂性理论 
特殊形式和结构的MSP问题NP完全性研究
《计算技术与自动化》2021年第3期78-83,共6页马兰 刘新 朱哲 
国家自然科学基金资助项目(61272010)。
针对一个NP完全问题,即MSP问题,研究其问题的结构性质,猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引,提出一种特殊形式和结构的MSP问题。而约束了形状的特殊形式和结构的MSP问题如果不具备NP完全性,会极大影响进一步简化...
关键词：MSP问题 多项式归结 NP完全性 
NP问题的通用多项式算法被引量：1
《数理化解题研究》2021年第18期4-5,共2页王海东 
由于NP问题存在通用多项式算法,所以NP问题就是一种P类问题.这种P类问题不仅大量存在于各种计算领域,而且确实有可能用非确定性方法一次给出正确答案.这种非确定性方法就是符合最短路线选择定理和最短路线构造定理的计算方法.
关键词：P类问题 NP问题 NP完全性 
d-正则(k,s)-SAT问题的NP完全性被引量：2
《软件学报》2020年第4期1113-1123,共11页符祖峰 许道云 
国家自然科学基金(61762019,61862051)。
研究具有正则结构的SAT问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的SAT问题是NP完全问题.研究具有更强正则...
关键词：d-正则(k s)-CNF公式 SAT问题 NP完全性 
非功能需求满足性的建模及其难解性
《合肥工业大学学报（自然科学版）》2017年第6期752-756,共5页李红杰 谢惠扬 
国家自然科学基金资助项目(61370193)
非功能性需求(non-functional requirement,NFR)是当前软件工程研究的一个重要课题,是衡量一个软件是否达到用户满意度的重要指标,而软目标相互依存图是描述非功能性需求的重要方法之一。文章研究了根据相互依存图实现软目标最优化的问...
关键词：非功能需求(NFRs)框架 NP完全性 软目标 局部最优 时间复杂度 
MSP问题NP完全性研究被引量：4
《计算机科学》2015年第7期12-14,27,共4页吴添君 姜新文 
国家自然科学基金(61272010)资助
针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法。
关键词：MSP问题 NP完全 问题归结 相变 
星座网络的网关卫星选择问题
《东南大学学报（自然科学版）》2013年第6期1152-1156,共5页吴俊 陆延 李斌 
国家自然科学基金资助项目(61070210;61070133);江苏省网络与信息安全重点实验室开放课题基金资助项目(BM2003201-201001)
为了既能获得较好的星座网络星-地通信延迟性能又能较少地占用地面站资源,提出了网关卫星选择问题.将网关选择问题建模成一种受限的支配集模型,对该问题的复杂性和贪心选择算法进行了研究.通过将3-SAT问题多项式时间规约到网关卫星选择...
关键词：网关卫星 NP完全性 贪婪算法 
SAT问题可多项式归结到MSP问题被引量：4
《计算机科学》2012年第11期179-182,共4页樊硕 姜新文 
国防科技大学校预研基金资助
针对文献[1]中提出的MSP问题(定义见正文),从SAT问题出发,给出SAT问题到MSP问题的多项式归结,进而给出MSP问题NP完全性质的另一种证明。
关键词：MSP问题 SAT问题 多项式归结 NP完全性 
素数阶均衡完美幻方若干问题初探被引量：5
《计算机工程与应用》2009年第21期179-182,共4页陈剑南 
幻方与拉丁方都是属于组合数学范畴的问题,两者关系十分密切。为进一步研究拉丁方与幻方之间的关系,在完美幻方的基础上,提出均衡完美幻方的概念,证明了均衡完美幻方与正交完美拉丁方对是一一对应的,同时发现了基于Zn的n阶完美拉丁方与...
关键词：均衡完美幻方 完美拉丁方 置换 正则群 缺陷填充问题 NP完全性 
Petri网的步问题研究被引量：5
《软件学报》2009年第3期505-514,共10页潘理 赵卫东 王志成 周新民 柳先辉 
国家高技术研究发展计划(863);国家科技支撑计划;上海市科委项目~~
在基于Petri网的模型验证方法中,步被广泛用于减少变迁实施产生的语义交织.为了研究基于步的构造算法的计算复杂性,提出步的判定问题,并证明该问题是NP完全的.进一步给出了极大步问题的多项式时间算法和最大步问题的NP等价性证明.最后...
关键词：PETRI网 发 步问题 NP完全性 NP等价性 
全选清除导出
共2页<12>
检索报告 对象比较 聚类工具 使用帮助 返回顶部