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

软件学报 2020年第4期31卷 1113-1123页

作者：符祖峰许道云贵州大学计算机科学与技术学院贵州贵阳550025 安顺学院电子与信息工程学院贵州安顺561000

研究具有正则结构的SAT问题是否是np完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的SAT问题是np完全问题.研究具有更强正则... 详细信息

研究具有正则结构的SAT问题是否是np完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的SAT问题是np完全问题.研究具有更强正则约束的d-正则(k,s)-SAT问题,其要求实例中每个变元的正负出现次数之差不超过给定的自然数d.通过设计一种多项式时间的归约方法,证明d-正则(k,s)-SAT问题存在一个临界函数f(k,d),使得当s≤f(k,d)时,所有实例都可满足;当s≥f(k,d)+1时,d-正则(k,s)-SAT问题是np完全问题.这种多项式时间的归约变换方法通过添加新的变元和新的子句,可以更改公式的子句约束密度,并约束每个变元正负出现次数的差值.这进一步说明,只用子句约束密度不足以刻画CNF公式结构的特点,对临界函数f(k,d)的研究有助于在更强正则约束条件下构造难解实例.

关键词： d-正则(k,s)-CNF公式 SAT问题 np完全性

来源：评论

学校读者我要写书评

暂无评论

表的等价性的np完全性的讨论

引用

计算机研究与发展 1996年第10期33卷 796-800页

作者：郝忠孝张英慧齐齐哈尔轻工学院

本文给出了表的等价性判定的一些结果：三元可满足性问题、表达式的ＮＰ完全性、表的ＮＰ完全性，还给出了函数依赖对表的影响、强等价性的复杂性的一些讨论。为对表的进一步研究指出了方向。

关键词：表 np完全性等价性数据库

来源：评论

学校读者我要写书评

暂无评论

SAT子类的np完全性和间隙问题复杂性研究

SAT子类的NP完全性和间隙问题复杂性研究

引用

作者：邓天炎贵州大学

学位级别：博士

从1972年发现np-完全性以来，很多学者就对np-难的优化问题能否有快速算法来计算其近似解感兴趣，然而对大部分这类问题，寻求有效的近似算法都令人失望。于是尝试来证明求其近似解也是np-难的，但除了极少个例成功之外就陷入停滞,并且... 详细信息

从1972年发现np-完全性以来，很多学者就对np-难的优化问题能否有快速算法来计算其近似解感兴趣，然而对大部分这类问题，寻求有效的近似算法都令人失望。于是尝试来证明求其近似解也是np-难的，但除了极少个例成功之外就陷入停滞,并且发现传统的Cook-Levin类型的归约技术并不能用来证明这类问题。直到1992年，由Arora等人发现了PCP定理，给出了np类的一个新特性，并提供了关于归约技术的一个新的起点，是极为令人震惊的。由PCP定理出发，可以得出很多np-难的优化问题，计算其近似解与计算其精确解具有同样的难度，因而除非P=np，否则不可能有多项式时间算法来求解。可以说，PCP理论是近20年来复杂性理论的重要成果之一，它是近似算法理论发展史上的一座里程碑。它对证明np难优化问题的不可近似性起到了关键性的作用。\n 本文应用PCP理论，对线性公式类LCNF及(k,s)-CNF公式类的np完全性及其间隙问题的复杂性进行了研究。对(k,s)-ksCNF公式类的临界函数下界的估计进行了探讨，主要作了以下工作：\n (1)考虑线性公式类LCNF，即公式中的任意两个子句最多只有一个公共变元。LSAT为LCNF的满足性判定问题，用间隙归约技术证明了MAX-LSAT属于第二类不可近似问题，即存在正数ε>0,MAX-LSAT要想取得近似比为1ε+的近似解是np-难的。进一步讨论了LCNF公式类的子类：k-LCNF，即其公式的每个子句的长度都是k，证明了对k≥3,MAX-k-LSAT≥也属于第二类。\n (2)用极小不可满足公式和递归方法解决了***等人在[PS06b]提出的开问题：对于k≥5，LCNF≥k中是否含有不可满足公式？这里LCNF≥k表示每个子句长度至少为k的线性公式构成的类。***用超图和拉丁方的方法构造出了LCNF≥3和LCNF≥4中的不可满足公式，然而其方法过于复杂且不具有推广性。我们给出了一种一般的构造方法，即用递归的方法构造出了k-LCNF中的不可满足公式，因而证明了：对于k≥3，k-LCNF含有不可满足公式，得到了比Porschen中提出的问题更强的结论。\n (3)考虑(k,s)-CNF公式类，它是由每个子句长度为k，而每个变元出现的次数不超过s的CNF公式构成的类，而(k,s)-SAT为其满足性判定问题。证明了MAX-(3,4)-SAT属于第二类不可近似的优化问题。并证明了：如果(k,s)-SAT是np-完全的，则MAX-(k,s))-SAT也属于第二类不可近似问题。\n (4)对(k,s)-SAT中的临界函数f(k)的界进行了研究。Kratochvil证明了：对每个k≥3，存在正整数s=f(k)，使得所有(k,s)-CNF中的公式都是可满足的；而(k,s+1)-CNF中存在不可满足公式，从而(k,s+1)-SAT是np完全的。关于f(k)，其精确值目前只知道f(3)=3,f(4)=，对k=5,6,…,9，目前已经知道的最好结果由Hoory、Berman和Kratochvil等人得到如下：\n 5≤f(5)≤7,7≤f(6)≤11,13≤f(7)≤17,24≤f(8)≤29,41≤f(9)≤51。\n 而对于k≥10，只有一般的估计式，相关的估计结果极少见到。我们通过用Berman等人构造的函数（公式略）。\n 它满足性质：对正整数k,d，如果存在x∈(0,1)，使得g(k,d,x)>1，则(k,d)-CNF中的每个公式都是可满足的。根据这个结果，结合函数作图，通过二分法或变步长搜索技术，对给定的正整数k，寻找存在x∈(0,1)，使函数g(k,d,x)>1的最大正整数d，把这个最大值d作为(f,k)的下界估计值，从而给出了寻求f(k)下界的一种方法。利用此方法，我们得出了k=10,11,…,20时f(k)有如下下界：\n f(10)≥75,f(11)≥136,f(12)≥251,f(13)≥463,f(14)≥860,f(15)≥1607,f(16)≥3013,f(17)≥5672,f(18)≥10715,f(19)≥20302,f(20)≥38574。\n 根据这种方法，还可以找出更多的下界。

关键词： SAT子类 np完全性间隙问题临界函数

来源：评论

学校读者我要写书评

暂无评论

缺陷幻方填充问题的np完全性判定研究

缺陷幻方填充问题的NP完全性判定研究

引用

作者：陈剑南国防科学技术大学

学位级别：硕士

缺陷幻方填充问题是幻方研究中发现的具有密码学意义的新问题,它是幻方数字锁原理和幻方数码防伪技术的基础,对此问题进行深入理论研究,以确认其安全强度,有着重要的理论和现实意义。同时,本文的研究对于推动幻方本身研究的发展也将有... 详细信息

缺陷幻方填充问题是幻方研究中发现的具有密码学意义的新问题,它是幻方数字锁原理和幻方数码防伪技术的基础,对此问题进行深入理论研究,以确认其安全强度,有着重要的理论和现实意义。同时,本文的研究对于推动幻方本身研究的发展也将有着重要的意义。针对这种需求,本文主要对缺陷幻方填充问题的np完全性判定展开研究,取得的主要成果有: (1)在文献[18]的基础上,提出了均衡泛对角线幻方的概念,证明了均衡泛对角线幻方与正交泛对角线拉丁方对是一一对应的,同时发现了泛对角线拉丁方与正则群的联系,还从泛对角线拉丁方的缺陷填充问题出发成功归约到均衡泛对角线幻方的缺陷填充问题上,证明了素数阶均衡泛对角线幻方的缺陷填充问题是np完全的。 (2)指出泛对角线拉丁方缺陷填充问题的np完全性证明中所存在的问题。对非线性泛对角线拉丁方的存在性问题进行了探讨,并把其难度与泛对角线拉丁方缺陷填充问题的np完全性证明的难度进行了比较。 (3)分别从主泛对角线拉丁方和对角线拉丁方(一种特殊的幻方)对幻方的缺陷填充问题的np完全性进行了探索,并从正则图的边着色问题出发归约到反对称拉丁方的填充问题上来,从而证明了缺陷反对称拉丁方的填充问题的np完全性。这对缺陷幻方的填充问题的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完全性

来源：评论

学校读者我要写书评

暂无评论

空间方向关系推理计算的np完全性研究

引用

江西师范大学学报（自然科学版） 2003年第3期27卷 279-282页

作者：毛建华邱小剑刘丽江西师范大学城市与环境科学学院江西南昌330027 江西师范大学物理与电子通信学院江西南昌330027

空间方向关系推理问题的np完全性证明是基于两个重要的变换基础之上的,其中一个变换是把空间方向关系推理问题变换为一个限定满足问题,基于这种变换,空间方向关系推理问题中的变量和值域相应地变换为限定满足问题中的空间目标和方向关... 详细信息

空间方向关系推理问题的np完全性证明是基于两个重要的变换基础之上的,其中一个变换是把空间方向关系推理问题变换为一个限定满足问题,基于这种变换,空间方向关系推理问题中的变量和值域相应地变换为限定满足问题中的空间目标和方向关系限制;另一个变换是从不全等3可满足问题到方向关系限定满足问题,基于这种变换,3可满足问题实例中的变量可以变换为两个方向关系限制.为此,一个满足所有目标方向关系限制的空间结构可以建立,从而可以证明空间方向关系推理问题的np完全性性质.

关键词：空间方向关系推理 np完全性锥形法空间方向关系推理模型计算复杂性地理信息系统

来源：评论

学校读者我要写书评

暂无评论

Petri网的步问题研究

引用

软件学报 2009年第3期20卷 505-514页

作者：潘理赵卫东王志成周新民柳先辉同济大学企业数字化技术教育部工程研究中心上海200092 湖南理工学院计算机与信息工程系湖南岳阳414006

在基于Petri网的模型验证方法中,步被广泛用于减少变迁实施产生的语义交织.为了研究基于步的构造算法的计算复杂性,提出步的判定问题,并证明该问题是np完全的.进一步给出了极大步问题的多项式时间算法和最大步问题的np等价性证明.最后... 详细信息

在基于Petri网的模型验证方法中,步被广泛用于减少变迁实施产生的语义交织.为了研究基于步的构造算法的计算复杂性,提出步的判定问题,并证明该问题是np完全的.进一步给出了极大步问题的多项式时间算法和最大步问题的np等价性证明.最后分析两类特殊子问题是P问题.

关键词： Petri网发步问题 np完全性 np等价性

来源：评论

学校读者我要写书评

暂无评论

星座网络的网关卫星选择问题

引用

东南大学学报（自然科学版） 2013年第6期43卷 1152-1156页

作者：吴俊陆延李斌扬州大学信息工程学院扬州225000

为了既能获得较好的星座网络星-地通信延迟性能又能较少地占用地面站资源,提出了网关卫星选择问题.将网关选择问题建模成一种受限的支配集模型,对该问题的复杂性和贪心选择算法进行了研究.通过将3-SAT问题多项式时间规约到网关卫星选择... 详细信息

为了既能获得较好的星座网络星-地通信延迟性能又能较少地占用地面站资源,提出了网关卫星选择问题.将网关选择问题建模成一种受限的支配集模型,对该问题的复杂性和贪心选择算法进行了研究.通过将3-SAT问题多项式时间规约到网关卫星选择问题,从而证明了网关卫星选择问题是np完全的.同时,设计了网关卫星选择问题的贪心算法,理论分析表明,若每颗卫星最多支持k条星间链路,则贪心选择算法是H(k+1)近似的,其中H表示调和函数.仿真实验结果表明,贪心算法在星座规模中等时性能接近最优解,在星座规模相对较大时性能接近H(k+1)的近似界.在平均规模情况下,采用贪心算法进行网关卫星选择能节省20%左右的星-地链路资源.

关键词：网关卫星 np完全性贪婪算法

来源：评论

学校读者我要写书评

暂无评论

np最优化问题的可近似性

引用

北京大学学报（自然科学版） 1995年第5期31卷 556-562页

作者：黄雄北京大学计算机科学与技术系

研究了ＮＰ最优化问题的可近似性。按照不同的可近似性将问题分类，证明了这些类是不同的（在Ｐ≠ＮＰ的假设下），并定义了问题之间保持近似比的归约，为每一类找到了在此归约下完全的问题。

关键词：计算复杂性 np完全性 np最优化可近似性

来源：评论

学校读者我要写书评

暂无评论

UET系统在m台处理机上的一种调度算法及其性能分析

引用

西南交通大学学报 1990年第4期25卷 46-51页

作者：石理

本文介绍了一种UET系统中有效的调度算法,其时间复杂性函数为O(na(n)+e)。该算法对m=2台处理机的调度为最优,而对m≥3台处理机上的未确定调度子问题,其解与最优解之比的最小上界为2-2/m,它也是一个近似程度相当好的有效算法。

关键词：调度算法算法分析 np完全性

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：