<分区>
图灵机停机概率与 3 CNF SAT 之间有关系吗？ 我找不到任何算法书籍 它们之间的关系是什么？
标签 algorithm
<分区>
图灵机停机概率与 3 CNF SAT 之间有关系吗？ 我找不到任何算法书籍 它们之间的关系是什么？
最佳答案
停机问题更难。
3-SAT 是 NP 完全问题，而停机问题在一般情况下是不可判定的。换句话说，不可能制定一种算法来解决图灵机上的一般停机问题。
为什么停机问题可以变得和图灵机上可解决的任何决策问题一样难，这是一个直觉。您可以为一个难题编写求解器，如果找到答案就会停止，然后询问该求解器是否会停止。
关于algorithm - 图灵机停机概率与 3 CNF SAT 之间有关系吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19090902/