基于变元加权的一种求解SAT问题的新方法

研究合取范式可满足性的SAT问题作为一个NP完全问题,在计算机科学及组合优化问题领域中有着中心课题的重要地位。由于其NP问题的性质决定了它尚无通用快速的完全算法,因此基于“实验算法学”的思想,按照平均性态而不是最坏情况性态的原则,对具有启发式策略的不完全算法的研究成为近年来大家关注与努力的焦点。该文正是立足于此,提出了“加权消元”这一种全新而且高效的算法。

A New Algorithm for SAT Problem Based on Weighted Variables

The satisfiability problem(SAT)is playing a very vital role in computing theory and combinatorial optimization fields.A fast and universal completed algorithm can't still be solved till now because SAT is a NP-Complete problem.So the research of uncompleted algorithms ,which is based on the idea of experimental algorithm theory,has been paid great attention to in these years.