将3-SAT分配的多项式时间缩短为3-SAT可决定性
说我们有一个多时间算法来确定是否存在3个SAT的解决方案。然后找到一个用于查找该解决方案的聚时间算法
Say we have a poly time algorithm for determining whether a solution to 3-sat exists or not. Then find a poly time Algo for finding that solution
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
重复直到没有变量：
选择方程中的任何变量。
查看
equation_false和equation_true，将您选择的变量全局替换为True和False的结果。其中至少必须满足其中之一。利用您已经知道如何求解 3Sat 的事实来确定哪个。根据哪个方程可满足，将变量设置为
True或False。 （如果两者都是，则选择其中一个。）使用可满足的方程继续该算法。在第 2 步中，您知道其中一个是可满足的，因为您知道原始方程至少有一个解，并且在该解中变量设置为 True代码> 或<代码>False。
Repeat until you have no variables:
Pick any variable in the equation.
Look at
equation_falseandequation_true, the results of globally replacing the variable you picked withTrueandFalse. At least one of them must be satisfiable. Use the fact that you already know how to solve 3Sat to determine which.Set your variable to
TrueorFalsedepending on which of the equations is satisfiable. (If they both are, just pick either.) Continue this algorithm with the satisfiable equation.In Step 2, you know that one of them is satisfiable because you know that there is at least one solution to the original equation, and in that solution the variable is either set to
TrueorFalse.