论文部分内容阅读
针对文献[1]中提出的MSP问题（定义见正文）,从SAT问题出发,给出SAT问题到MSP问题的多项式归结,进而给出MSP问题NP完全性质的另一种证明。
SAT问题可多项式归结到MSP问题
【摘 要】
：
针对文献[1]中提出的MSP问题（定义见正文）,从SAT问题出发,给出SAT问题到MSP问题的多项式归结,进而给出MSP问题NP完全性质的另一种证明。
【机 构】
：
国防科技大学计算机学院
【出 处】
：
计算机科学
【发表日期】
：
2012年11期
【基金项目】
：
国防科技大学校预研基金资助
其他文献
系统地总结了现有的具有最大代数免疫度的布尔函数的构造方法,将现有各种构造方法按其构造思想的不同分为有代表性的几类,并分别介绍了基于这几类方法的一些结果和进展,其中
直接数字频率合成(DDS)技术由于输出杂散信号多且难预测,限制了其发展和应用。依据DDS基本原理,利用傅立叶变换法分析了理想DDS输出频谱特征,推导了相位截断引入杂散信号的频
传统的UDDI不支持语义推理以及基于服务属性的匹配,因此存在召回率低、匹配效率低等问题。基于此问题提出了一种基于Petri网的OWL-S语义匹配机制,即借助Multi-Agent服务发现
依靠基因调控网络来预测农作物的表现型,对于保障全球的粮食安全有着极其重要的意义。提出了一种基于笛卡尔遗传规划（Cartesian genetic programming）和线性递减惯性权重粒子群
通过分析Web-Harvest数据提取规则的设计原理,设计实现了一个xScraper系统。该系统的主要功能有：（1）定制设计满足不同需求的Web数据提取规则模板,驱动Web-Harvest内核进行无结构
为了提高现行模糊辨识方法的有效性,提出了基于移动率的T-S模糊模型的结构辨识方法。主要工作如下：首先,定义T-S模糊模型的S型、Z型和梯形隶属函数的移动率,将此移动率与现行
从理论上分析了几种随机数发生器后处理方法,提出了一种新的针对真随机数发生器的后处理方法,经过后处理的随机序列满足均匀性、独立性以及提高每比特熵的要求。对实际带有偏
用户评分数据极端稀疏的情况下,传统相似性度量方法存在弊端,导致推荐系统的推荐质量急剧下降。针对此问题,提出了一种基于项目聚类的全局最近邻的协同过滤算法。该算法根据
分布式一致性算法可用于解决分布式协作参数估计等许多问题,但在无线传感器网络的应用中还要满足低能耗、高可靠性、实时性的要求。为加快一致性算法的收敛速率,以降低通信能
对于移动对象历史轨迹索引,现有的方案绝大多数都基于室外空间,难以直接应用于室内空间中;同时,未将对象本身作为一个独立的维度加以索引,无法提供高效的对象轨迹查询方式。