图灵机停止问题和3 CNF SAT之间有关系吗？我找不到任何算法书籍它们之间的关系是什么？
问问题
627 次
3 回答
4
停机问题更难。
3-SAT 是 NP 完全的，而停止问题在一般情况下是不可判定的。换句话说，不可能制定一种算法来解决图灵机上的一般停机问题。
一个直觉是，停机问题可以像图灵机上可解决的任何决策问题一样困难。您可以为一个困难问题编写一个求解器，如果它找到答案就会停止，然后询问该求解器是否会停止。
于 2013-09-30T09:41:20.290 回答
2
停止的问题是图灵机可以识别哪些语言，甚至有无限的时间。这是一个严格逻辑的问题。
3SAT问题是关于解决一个问题需要多少操作，这意味着你需要多少时间。这是一个关于寻找快速算法的问题，因为已知存在慢速算法。
于 2013-09-30T09:50:52.690 回答
0
停机问题在图灵机上是不可能解决的，而 3SAT 可以解决。你还在寻找什么其他类型的关系？
于 2013-09-30T09:44:49.020 回答