一类布尔方程组的可满足性阈值研究

• 作者: 郑志明 郭炳晖 韦卫
• 来源期刊: 计算机应用研究
• 关键词: 布尔方程组 NP问题 可满足性 阈值估计 算法设计
• 年，卷（期）: 2010,（10）
• 页码范围: 3666-3669
• 分类号: TP301.5
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2010.10.015

摘要

以一类布尔方程组形式的NP问题可满足性阈值估计为研究目的,通过将高斯消去算法与摘叶算法相结合的方法给出了一种求解该问题的完全算法,并通过不同参数条件下对大量随机实例进行数值实验得到了原问题可满足性阈值的算法估计值.所得研究结果不仅首次给出了该问题的可满足性阈值估计,而且可以作为相关启发式完全算法的设计依据.