如果我们看到这里介绍的算法：https ://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/threeSAT_to_hamiltonianCycle.html
它每级使用 2k 个节点，其中 k 是子句数或引用优化版本中特定变量的子句数。然而，路径的歧义似乎肯定是可能的，令人惊讶的是，一个学术网站会在归约证明中包含如此重大的错误。
此处介绍的算法版本：https ://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/08PolynomialTimeReductions-2x2.pdf
似乎是正确的，因为它在每个级别使用 3k+3 个节点，其中它的 2k 版本在子句/变量对之间添加了节点以用于额外的 k-1 个节点，然后在每行的开头和结尾额外增加 2 个节点. 这给出了 2k+k-1+2+2=3k+3 个节点。
似乎不仅 UNSAT 公式可能是可满足的，而且可以肯定的是，SAT 方程将有由 OpenDSA 上的方程产生的错误解。在一本制作精良的专业书籍中发现这样一个错误是相当令人惊讶的，所以我认为这值得一问。我已经就此通知了 OpenDSA。