• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>International Journal of Engineering & Technology >Polynomial Exact-3-SAT-Solving Algorithm
【24h】

Polynomial Exact-3-SAT-Solving Algorithm

机译：多项式精确3-SAT求解算法

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This article describes an algorithm which is supposed by the author to be capable of solving any instance of a 3-SAT CNF in maximal O(n^15), whereby n is the variable index range within the 3-SAT CNF to solve. The presented algorithm imitates the proceeding of an exponential, fail-safe solver. This exponential solver stores internal data in m-SAT clauses, with 3 = m = n. The polynomial solver works similarly, but uses 3-SAT clauses only to save the same data. The paper explains how, and proves why this can be achieved. On the supposition the algorithm is correct, the P-NP-Problem would be solved with the result that the complexity classes NP and P are equal.
机译：本文介绍了一个算法，该算法由作者能够在最大O（n ^ 15）中求解3-SAT CNF的任何实例，由此N是用于解决3-SAT CNF内的可变索引范围。所提出的算法模仿指数，故障安全求解器的进行。该指数求解器将内部数据存储在M-SAT子句中，其中3 <= m <= n。多项式求解器类似地工作，但仅使用3-SAT子句来保存相同的数据。本文解释了如何，并证明为什么可以实现这一点。在假设算法是正确的情况下，P-NP问题将解决复杂性类NP和P等于的结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号