期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到6篇文章
< 1 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
极小不可满足公式在多项式归约中的应用 被引量：24
1
作者 许道云 《软件学报》 EI CSCD 北大核心 2006年第5期1204-1212,共9页
合取范式(CNF)公式F是极小不可满足的,如果F不可满足,并且从F中删去任意一个子句后得到的公式可满足,(r,s)-CNF是限制CNF公式中每个子句恰有r个不同的文字,且每个变元出现的次数不超过s次的公式类,对应的满足性问题(r,s)-SAT指实例公式... 合取范式(CNF)公式F是极小不可满足的,如果F不可满足,并且从F中删去任意一个子句后得到的公式可满足,(r,s)-CNF是限制CNF公式中每个子句恰有r个不同的文字,且每个变元出现的次数不超过s次的公式类,对应的满足性问题(r,s)-SAT指实例公式限制于(r,s)-CNF.对于正整数r≥3,有一个临界函数f(r),使得(r,f(r))-CNF中的公式都是可满足的,而(r,f(r)+1)-SAT却是NP-完全的.函数f是否可计算是一个开问题,除了知道f(3)=3,f(4)=4外,只能估计f(r)的界.描述了极小不可满足公式在CNF公式类之间转换中的作用.为使转换过程中引入较少的新变元,给出了CNF公式到3-CNF公式的一种新的转换方法,对于长度为l(>3)的子句,仅需引入???2l???个新变元.并且,给出了CNF到(r,s)-CNF公式转换以及(r,s)-CNF中不可满足公式构造的原理和方法. 展开更多
关键词 极小不可满足公式 问题 多项式归约 NP-完全 公式构造
下载PDF
Hamming距离下的最短路逆问题 被引量：2
2
作者 张斌武 王勤 《河海大学学报（自然科学版）》 CAS CSCD 北大核心 2008年第4期571-574,共4页
针对Hamming距离下的最短路逆问题,分析了最优解的性质,给出并证明了问题存在可行解的充分必要条件;利用把背包问题的实例多项式归约到该问题的实例,证明了该问题为NP困难的,为设计该类问题的近似算法提供了理论依据.
关键词 HAMMING距离 最短路 NP困难 多项式归约 3-SAT问题
下载PDF
NP难解问题的教学方法探讨 被引量：3
3
作者 张辉 王裕明 +1 位作者 姚兴华 孔丽红 《软件导刊.教育技术》 2018年第4期82-83,共2页
NP难解问题,由于其理解起来的难度,加之目前本科生中普遍存在的学习和思想误区,实际教学难以取得理想的效果。有鉴于此,讨论了两种教学方法,旨在使难于理解的抽象问题转换为具体的有趣问题,降低初学者理解NP难解问题的难度,唤起学生的... NP难解问题,由于其理解起来的难度,加之目前本科生中普遍存在的学习和思想误区,实际教学难以取得理想的效果。有鉴于此,讨论了两种教学方法,旨在使难于理解的抽象问题转换为具体的有趣问题,降低初学者理解NP难解问题的难度,唤起学生的学习热情,提升教学效果。 展开更多
关键词 理论计算机科学 NP难解问题 多项式时间归约 整数规划问题 可满足性问题
下载PDF
有不同中断时间代价的一致并行抢先调度问题 被引量：2
4
作者 周华奇 鲁鸣鸣 朱洪 《计算机研究与发展》 EI CSCD 北大核心 2005年第3期507-513,共7页
提出了具有不同中断时间代价的抢先调度问题(P|ptmn(δi)|Cmax).该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.首先证明了这个问题是一个NP难优化问题.并给出了一个时间复杂度为O(nlogn)的近似算法,其近... 提出了具有不同中断时间代价的抢先调度问题(P|ptmn(δi)|Cmax).该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.首先证明了这个问题是一个NP难优化问题.并给出了一个时间复杂度为O(nlogn)的近似算法,其近似度为5／3.算法的特点是结合中断时间δi来应用LPT思想,而不只是把它应用到任务i的执行时间pi上,从而避免了LPT算法在最坏情形下的近似度差的问题.在算法的关键部分,运用了均分的技巧来提高任务执行的并行性,进一步提高了近似度. 展开更多
关键词 调度问题 组合优化 NP NP完全 多项式时间归约 NP难
下载PDF
带测度函数的连通支配集问题
5
作者 马俊 朱洪 《计算机科学》 CSCD 北大核心 2006年第1期220-222,共3页
连通支配集问题在网络广播上有着广泛的应用,本文引入测度函数的概念,提出了带测度函数的连通支配集问题(CDS(F)),使得它具有更广的应用范围。文中首先给出问题的形式定义,证明了它在各种情形下的 NP 完全性,并给出多项式时间的近似算法... 连通支配集问题在网络广播上有着广泛的应用,本文引入测度函数的概念,提出了带测度函数的连通支配集问题(CDS(F)),使得它具有更广的应用范围。文中首先给出问题的形式定义,证明了它在各种情形下的 NP 完全性,并给出多项式时间的近似算法,它的近似度为 Ln△+3(△为图中顶点的最大度数)。 展开更多
关键词 支配集问题 组合优化 NP NP完全 多项式时间归约 NP难 测度函数 支配集 连通 NP完全性 多项式时间
下载PDF
NTRU的应用前景分析与展望 被引量：2
6
作者 杨铭 曹云飞 《信息安全与通信保密》 2007年第8期36-38,共3页
NTRU的安全性是基于格基归约的困难性,因此从理论上来说为公钥密码体制开辟了一个新的领域。本文分析了NTRU的优点,展望NTRU的应用前景,提出当前NTRU所面临的主要问题以及相应的解决策略。
关键词 NTRU 格基归约:多项式截断环
原文传递
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
使用帮助 返回顶部