一种布尔公式的代数逻辑约化新方法

• 作者: 刘江 周鸿昊
• 来源期刊: 计算机科学
• 关键词: NP完全问题 布尔可满足性问题 1-in-3-SAT XCNF X-纯文字
• 年，卷（期）: 2020,（5）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 32-37
• 页数: 6页
• 字数: 8977字
• 语种: 中文
• DOI: 10.11896/jsjkx.190400018

摘要

布尔可满足问题是最早被证明的NP完全问题之一,1-in-3-SAT问题是一个NP完全的布尔可满足子类问题.1-in-3-SAT的计算复杂度取决于对应公式的变量以及子句的个数.将1-in-3公式归约为一个变量数或者子句数更少的1-in-3公式,是提高1-in-3-SAT问题求解效率的一个关键.基于一个新的范式形式——XCNF,针对1-in-3-SAT问题提出一种新的代数逻辑约化方法,用于在多项式时间内约减一个1-in-3公式的变量数和子句数.所提算法的主要思想为:首先将1-in-3公式转化为XCNF公式,然后尝试找出XCNF公式中的X-纯文字,并利用X-纯文字法则对1-in-3公式中相应的布尔变量赋值,最后得到一个约减公式,该约减公式与原公式的1-in-3可满足性等价.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘江	中国科学院重庆绿色智能技术研究院高性能计算应用研究中心	36	769	13.0	27.0
2	周鸿昊		1	0	0.0	0.0