从3SAT轻松减少到汉密尔顿路径问题

Question

第286页从3SAT到汉密尔顿路径问题，Sipser的书《计算理论简介》的著作减少了。

有更简单的减少吗？

简单地说，我的意思是减少（对于学生）更容易理解。

是否有使用线性变量数量的减少？

sipser的减少使用$ o（kn）$变量，其中$ k $是条款的数量，$ n $是变量的数量。换句话说，减少的大小可能从$ s $ to $ o（s^2）$吹嘘。是否有一个简单的减少，减少输出的大小在其输入的大小中是线性的？

如果不可能，是否有原因？这是否意味着复杂性/算法的未知结果？

Answer 1

从3SAT到指导的汉密尔顿路径（dhampath）中众所周知的顶点数量可以轻松减少到$ o（n+k）$，其中$ n $是变量的数量，$ k $是子句，因此构造的图形实例的大小是线性到原始3SAT实例的大小。

在原始减少的情况下，我们启动了顶点和End顶点，条款的$ K $顶点，变量的长度为4K $的$ N $列表。这个想法是，我们不必为每个变量构建长度$ 4K $的列表，我们可以根据所有条款中的变量出现的数字构造列表。由于子句中变量的总数为$ 3K $，因此是$ O（N+K）$。