不是 NP-hard 的不可判定的例子？
Example of an undecidable that is not NP-hard?
谁能给我一个非 NP-hard 的不可判定问题的例子？
我无法理解两者之间的区别。
非常感谢！
NP-hard 问题是指 NP 中的所有问题都可以归结为它。其实就是"at least as hard as"NP中的问题class。例如，TSP（Traveling Sales Person）是 NP-hard。然而，undecidable 是一个没有算法总是正确决定的问题。例如，程序是否在某个点停止的问题是不可判定的。事实上，你可能没有一个算法可以为世界上所有的程序正确回答这个问题。 (这个可以证明)
所以，简而言之，一个不可判定的问题逻辑上很难；无论你的计算机或算法有多强大，它们都无法解决。但是，NP-hard 问题有算法可以解决，但这些算法不是时间多项式的。
谁能给我一个非 NP-hard 的不可判定问题的例子？
我无法理解两者之间的区别。
非常感谢！
NP-hard 问题是指 NP 中的所有问题都可以归结为它。其实就是"at least as hard as"NP中的问题class。例如，TSP（Traveling Sales Person）是 NP-hard。然而，undecidable 是一个没有算法总是正确决定的问题。例如，程序是否在某个点停止的问题是不可判定的。事实上，你可能没有一个算法可以为世界上所有的程序正确回答这个问题。 (这个可以证明)
所以，简而言之，一个不可判定的问题逻辑上很难；无论你的计算机或算法有多强大，它们都无法解决。但是，NP-hard 问题有算法可以解决，但这些算法不是时间多项式的。