This is a commentary on, and critique of, Latif Salum's paper titled "Tractability of One-in-three $\mathrm{3SAT}$: $\mathrm{P} = \mathrm{NP}$." Salum purports to give a polynomial-time algorithm that solves the $\mathrm{NP}$-complete problem $\mathrm{X3SAT}$, thereby claiming $\mathrm{P} = \mathrm{NP}$. The algorithm, in short, fixes the polarity of a variable, carries out simplifications over the resulting formula to decide whether to keep the value assigned or flip the polarity, and repeats with the remaining variables. One thing this algorithm does not do is backtrack. We give an illustrative counterexample showing why the lack of backtracking makes this algorithm flawed.


翻译:这是对Latif Salum的论文的评论和批评, 题为“ 一对一的3$\ mathrm{3SAT}$:$\ mathrm{P} =\ mathrm{NP}$ 。 Salum 旨在给出一个多元时间算法, 解决$\ mathrm{NP} $- 完整的问题 $\ mathrm{X3SAT}$, 从而索赔$\ mathrm{P} =\ mathrm{NP}$ 。 算法, 简而言之, 修正变量的极性, 对由此产生的公式进行简化, 以决定是保留指定的值还是翻转极性, 重复剩余变量 。 此算法不起作用的一件事是反向轨道 。 我们给出一个示例反示例, 说明为什么缺乏回溯跟踪使此算法有缺陷 。

0
下载
关闭预览

相关内容

专知会员服务
75+阅读 · 2021年3月16日
专知会员服务
17+阅读 · 2020年9月6日
专知会员服务
158+阅读 · 2020年1月16日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
56+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
167+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
186+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
90+阅读 · 2019年10月10日
已删除
将门创投
5+阅读 · 2019年10月29日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
R语言自然语言处理:文本分类
R语言中文社区
7+阅读 · 2019年4月27日
R语言实现聚类kmeans
R语言中文社区
3+阅读 · 2019年2月14日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
VIP会员
相关VIP内容
专知会员服务
75+阅读 · 2021年3月16日
专知会员服务
17+阅读 · 2020年9月6日
专知会员服务
158+阅读 · 2020年1月16日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
56+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
167+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
186+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
90+阅读 · 2019年10月10日
相关资讯
已删除
将门创投
5+阅读 · 2019年10月29日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
R语言自然语言处理:文本分类
R语言中文社区
7+阅读 · 2019年4月27日
R语言实现聚类kmeans
R语言中文社区
3+阅读 · 2019年2月14日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员