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}$ 。 算法, 简而言之, 修正变量的极性, 对由此产生的公式进行简化, 以决定是保留指定的值还是翻转极性, 重复剩余变量 。 此算法不起作用的一件事是反向轨道 。 我们给出一个示例反示例, 说明为什么缺乏回溯跟踪使此算法有缺陷 。