SAT问题多项式时间算法-一个稳定的NP问题算法

摘要：

本文基于逻辑代数的反向运算和对自变元的等级划分规则给出了一种分级赋值求解SAT问题的多项式时间算法.这种方法根据逻辑代数中基本逻辑运算的特点,赋予由执行这些基本逻辑运算的反向运算而得到的自变元的值以相应的等级,并且通过由拥有高等级的自变元修正低等级自变元相应值的方法得出问题的确定解.这种方法在包括最坏情况下的时间复杂度为O(n).

关键词： SAT问题 逻辑代数 分级赋值 多项式时间算法.

作者: 崔刚

作者单位: 沈阳大学,信息工程学院,沈阳,110044

会议类型: 国内会议

会议名称: 中科院自动化研究所自动化与信息技术发展战略研讨会暨2003年学术年会

会议地点: 北京

会议语种:中文

页码: 682-687

在线出版日期: 2003-10-16（万方平台首次上网日期，不代表论文的发表时间）