一种布尔公式的代数逻辑约化新方法
文献类型：期刊论文
| 作者 | 刘江 ; 周鸿昊
|
| 刊名 | 计算机科学
 |
| 出版日期 | 2020 |
| 卷号 | 47期号:5页码:32 |
| 关键词 | NP complete problem Boolean satisfiability problem 1-in-3-SAT XCNF X pure literal NP完全问题 布尔可满足性问题 1-in-3-SAT XCNF X-纯文字 |
| ISSN号 | 1002-137X |
| 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可满足性等价。 |
| 语种 | 英语 |
| 源URL | [http://119.78.100.138/handle/2HOD01W0/11234]  |
| 专题 | 中国科学院重庆绿色智能技术研究院 |
| 作者单位 | 中国科学院重庆绿色智能技术研究院 |
| 推荐引用方式 GB/T 7714 | 刘江,周鸿昊. 一种布尔公式的代数逻辑约化新方法[J]. 计算机科学,2020,47(5):32. |
| APA | 刘江,&周鸿昊.(2020).一种布尔公式的代数逻辑约化新方法.计算机科学,47(5),32. |
| MLA | 刘江,et al."一种布尔公式的代数逻辑约化新方法".计算机科学 47.5(2020):32. |
入库方式： OAI收割
来源：重庆绿色智能技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。