姜咏江 我确信子句消去法是快速求出 SAT 问题满足解的唯一方法。子句消去法是一个多项式时间的算法,我已经在科学网上介绍了它完整的证明,我有十足的把握,没有人能够推翻它。 由于 SAT 问题直接能够运用到超大规模集成电路化简、生物基因计算、博弈决策、密码破译、人工智能、计算机系统设计等诸多方面, ...
SAT问题满足解详解求解例题 姜咏江 从一开始接触 SAT 问题求解,我就说过:“科学网是我科研的地方。”两年,我在科学网上经历了与别人不一样的研究历程,当然,也收获了与别人不一样的成果。我以 3-SAT 问题求解的实例,来详细告诉感兴趣的人们,如何在多项式时间内求出这类 SAT 问题满足解。这是对以往阅读过我那 ...
姜咏江 消去块中唯一解, 不然找一可选解, 解多暂时一边放, 全多选解可得解。 《时间复杂度解释: 子句块变量唯一解的判断条件为有2 k-1 个0或1,如果同时0和1都有2 k-1 个SAT无解 。 SAT 的子句块最多有 2 k C n k +2 k-1 C n k-2 +…+ C n 1 这多项式个,子句块变量最多 ...