NP完全性相关论文
摘 要:针对一个NP完全问题,即MSP问题,研究其问题的结构性质,猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引,提出一种特殊......
可满足性问题(the satisfiability prblem,简称SAT)是计算机科学的中心问题之一,相变现象则是SAT问题的一个重要特性.该文首先总结......
我们完成的主要工作如下:(1)编程实现简化的环匹配算法、 Mfold算法和Lyngsφ算法,给出其试验与比较结果. (2)提出一个实用的新简......
自从Steve Cook证明了第一个NP完全问题以来,大量的NP完全问题不断被发现,而且很多问题具有重要的实际应用。比如,SAT问题是大规模......
从1972年发现NP-完全性以来,很多学者就对NP-难的优化问题能否有快速算法来计算其近似解感兴趣,然而对大部分这类问题,寻求有效的近似......
由于NP问题存在通用多项式算法,所以NP问题就是一种P类问题.这种P类问题不仅大量存在于各种计算领域,而且确实有可能用非确定性方......
超协调限制逻辑LPc是一种同时具有非单调性和超协调性的非经典逻辑,它可作为在不完全与不协调知识下常识推理的形式化.给出了命题L......
连通支配集问题在网络广播上有着广泛的应用,本文引入测度函数的概念,提出了带测度函数的连通支配集问题(CDS(F)),使得它具有更广的应用范......
针对文献[1]中提出的MSP问题(定义见正文),从SAT问题出发,给出SAT问题到MSP问题的多项式归结,进而给出MSP问题NP完全性质的另一种证......
本文介绍了一种UET系统中有效的调度算法,其时间复杂性函数为O(na(n)+e)。该算法对m=2台处理机的调度为最优,而对m≥3台处理机上的......
空间方向关系推理问题的NP完全性证明是基于两个重要的变换基础之上的,其中一个变换是把空间方向关系推理问题变换为一个限定满足......
在基于Petri网的模型验证方法中,步被广泛用于减少变迁实施产生的语义交织.为了研究基于步的构造算法的计算复杂性,提出步的判定问题,......
幻方与拉丁方都是属于组合数学范畴的问题,两者关系十分密切。为进一步研究拉丁方与幻方之间的关系,在完美幻方的基础上,提出均衡......
研究了NP最优化问题的可近似性,按照不同的可近似性将问题分类,证明这些类型是不同的(在P≠NP的假设下),并定义了问题之间保持近似比的归纳,为......
非功能性需求(non-functional requirement,NFR)是当前软件工程研究的一个重要课题,是衡量一个软件是否达到用户满意度的重要指标,而软......
本文提出一个构造的 Np 全全问题 DHC。该问题由(?)郎担问题和哈密顿回路判定问题导出,导出 DHC 的基本思想是试图使求解与 DHC 相......
本文给出了表的等价性判定的一些结果:三元可满足性问题,表达式的NP完全性,表的NP完全性,还给出了函数依赖对表的影响,强等价性的复杂性的一......
研究具有正则结构的SAT问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函......
无线传感器网络是由具有一定计算及无线通信能力的传感器节点和用于收集数据的sink节点所组成的无线自组织网络系统。近年来,随着......
本文根据运输问题中一类常见的情况建立了在并容量网络中求最大并流的网络模型,证明了最大并流问题的NP完全性,并给出了求解该问题的一......
由于半导体技术在最近30年间里成指数式发展,研究人员们有能力利用这个半导体生产技术制造小型化的天线和能够感应物理世界的传感......
随着分布仿真应用规模的扩大,兴趣管理逐渐成为分布仿真领域中一个重大而艰难的研究方向。兴趣管理的目的主要有两个:一是尽可能减少......
为了既能获得较好的星座网络星地通信延迟性能又能较少地占用地面站资源,提出了网关卫星选择问题。将网关选择问题建模成一种受限的......