【摘 要】
：
研究具有正则结构的SAT问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;
【机 构】
：
贵州大学计算机科学与技术学院,安顺学院电子与信息工程学院
【基金项目】
：
国家自然科学基金(61762019,61862051)
论文部分内容阅读
研究具有正则结构的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
其他文献
目的探讨应用寰椎侧块螺钉与枢椎椎弓根螺钉固定融合治疗上颈椎不稳的疗效。方法2006年2月至2008年9月,采用寰椎侧块螺钉结合枢椎椎弓根螺钉技术治疗寰枢椎不稳l0例,其中齿突
随着经济活动数据的不断丰富,互联网平台上产生了大量的财经文本,其中蕴含了经济领域发展状况的影响因素.如何从这些财经文本中有效地挖掘与经济有关的经济要素,是实现非结构
随着社会经济的发展和科学技术的进步,我国的电力行业得到了快速的发展。电能源作为现阶段的主要能源物质,不仅对国家、城市的经济发展有着非常重要的作用和意义,而且对人们
为了缓解神经网络的“黑盒子”机制引起的算法可解释性低的问题,基于使用证据推理算法的置信规则库推理方法(以下简称RIMER)提出了一个规则推理网络模型.该模型通过RIMER中的
提出在平行凸轮间歇摆动驱动装置产品设计过程中,根据市场需求,产品成本降低和整体布局合理来确定系列主参数,在此基础上对该产品进行功能分析并建立功能模块系统,应用模块设
目前,大多数高校都会将摄影课作为专业选修课推进。摄影实验室所承担的最重要任务就是完成摄影课程教学。摄影实验室除完成摄影课教学任务外,更多的是为各专业学生进行课程作
随着我国国民经济的飞速发展,作为金融系统最关键的组成部分银行扮演者越来越重要的角色,科学技术的进步使得银行系统信息化程度越来越高,而复杂的外部环境又使银行信息安全
对一体式厌氧膜生物反应器污泥进行离心分离,考察污泥各组分和膜污染的特性之间的关系.通过对已有理论模型进行变形,推导出阻力的数学模型方程式,并分析了膜通量、膜阻力的变
通过比较分析换流站直流线路再起动保护与站间通讯中逻辑关系,找出每种工况下的再启动过程.当直流系统发生再启动时,现场能迅速而准确判断再启动保护逻辑动作正确性,以便更快
为了从根本上解决瓦斯爆炸的危害，提出了一种防治瓦斯爆炸的新方法，即绝热氧化法。该项技术的基本原理是：将接近爆炸浓度的含瓦斯气体稀释至爆炸浓度以下，再通过负压转移系统送入