8wDlpd.png
8wDFp9.png
8wDEOx.png
8wDMfH.png
8wDKte.png

从汉密尔顿循环简化为 3-SAT

Rick James 2月前

23 0

我在网上找到了很多资料,描述了从 3-SAT 到汉密尔顿循环的简化,这两者都是 NP 完全问题。因此,我知道一定存在相反的简化

我在网上找到了很多资料,描述了从 3-SAT 到汉密尔顿循环的归约,这两个都是 NP 完全问题。因此,我知道一定存在一个反方向的归约,有人告诉我这已经定义好了,但我找不到任何地方。

我尝试在网上进行彻底搜索,但我无法找到很多关于这个主题的教科书/书籍,所以我陷入了困境。有人知道这种减少是否真的被定义了吗?

帖子版权声明 1、本帖标题:从汉密尔顿循环简化为 3-SAT
    本站网址:http://xjnalaquan.com/
2、本网站的资源部分来源于网络,如有侵权,请联系站长进行删除处理。
3、会员发帖仅代表会员个人观点,并不代表本站赞同其观点和对其真实性负责。
4、本站一律禁止以任何方式发布或转载任何违法的相关信息,访客发现请向站长举报
5、站长邮箱:yeweds@126.com 除非注明,本帖由Rick James在本站《algorithm》版块原创发布, 转载请注明出处!
最新回复 (0)
  • 我发现很多描述将 HC 简化为普通的旧 SAT,这不是 3-SAT,但这并不重要,因为您可以通过引入一些链接变量将大子句拆分为最多包含 3 个文字的子句。

返回
作者最近主题: