考虑具有以下特殊位置属性的 3SAT 实例。假设布尔公式中有 n 个变量，并且它们的编号为 1,2,3....n，这样每个子句都包含编号在 +-10 范围内的变量。给出求解此类 3SAT 实例的线性时间算法。
我无法解决这个问题，但我的直觉是，如果我们可以将问题映射到图表中，那么可能会得到解决，但不能走得更远..
问问题
1744 次
2 回答
4
这是一个相对简单的动态规划问题。我将描述一个解决方案，忽略围绕任一边界的相当简单的索引问题。
在第 m 步之后，我们有一组可能的变量值 (m-10, m-9, ..., m+10)，它们可能是迄今为止的解决方案，每个都链接到所有先前变量的一组值这导致方程 1..m 的解。
对于第 m+1' 步，我们采用这个可能的解决方案集的每个成员，忽略第 m-10' 值，并考虑第 m+11' 值的每种可能性。如果第 m+1 个方程为真，我们将其添加到下一个解集，指向我们的历史，前提是该解模式尚未添加。
这使我们为 m+2nd 步骤做好了准备。
需要 n 个步骤，每个步骤可以考虑大约 200 万个可能的情况，所以这是线性的。
（有趣的挑战。修改这个算法，不仅要找到解决方案，还要计算有多少解决方案。）
于 2012-04-18T17:06:33.330 回答
1
我认为你可以在多时间内暴力破解它。将子句列表分成两部分。对分裂两边的变量进行详尽的搜索。最多有 30 个，因此可以尝试 2^30 = O(1) 设置。一旦设置了这些变量，您就可以递归地解决两边，每一个都是具有 n/2 个变量的独立 SAT 实例。
于 2012-04-18T16:54:27.917 回答