NP不在NP中但可决定的NP难题

Question

我想知道是否有一个很好的例子可以易于理解 np-hard 问题不是 NP完整 并且不是不确定的吗？

例如， 停止问题 是np-hard，而不是NP完整的，但不可决定。

我认为这意味着可以验证解决方案但在多项式时间内不能进行解决方案是一个问题。 （如果不是这种情况，请更正此声明）。

Answer 1

由不确定的版本的 时间层次定理, ，我们有$ mathsf {np} subsetneq mathsf {nexp} $，其中 $ mathsf {nexp} $ 是可以在非确定性指数时间中解决的问题类别。因此，考虑到任何问题是$ mathsf {np} $ - 硬，而在$ mathsf {nexp} $中，但不在$ mathsf {np} $中。例如，我们可以考虑任何 $ mathsf {nexp} $ - 完整问题, ， 如

• 3个图形的三色，由简洁的电路描述 - 或图表上的任何其他NP完整问题 - “简洁电路”是表示输入中非常大图的格式：而不是明确表示图。 例如通过邻接列表，我们提供一个电路计算一些函数$ f： {0,1 }^{n} times {0,1 }^n to {0,1 } $ $ 2^n times 2^n $邻接矩阵的系数。

• （非）两个正则表达式的等效性， 在克莱恩之星被平方取代的地方（重复一个恰好的子图案，而不是零或更多次），我们询问两个这样的正则表达式是否代表不同的字符串集。

请注意，在后一种情况下，如果我们习惯于考虑使用正则表达式，包括Kleene Star，则结果问题是$ Mathsf {expspace} $ - 完整：因为我们有comantments $ mathsf {np} Subset Mathsf {nexp} subseteq Mathsf {expspace} $，这仍然是一个可决定的问题，是$ Mathsf {np} $ - 硬，而不是$ Mathsf {np} $。

Answer 2

免责声明：此答案是基于以下假设：$ mbox {pspace} neq mbox {np} $，一个假设，大多数科学家都坚信，但我们尚未证明。这意味着这些问题可能在$ mbox {np} $中，因此也可能是$ mbox {np} $ - 完成。

我会说最简单的是 真正的量化布尔公式 和 广义地理, ，两个$ mbox {pspace} $ - 完成。

TQBF被给予 量化 布尔公式，测试公式是否为true，即$ forall x 的形式上的公式为y forall z。 ; [（x lor y） land z] $是false，因为将$ z $设置为false会产生一个错误的语句。

广义地理是一个有趣的游戏（请参阅 文字链）如果您有一个字符串列表（例如城市名称）和播放器1首先说出一个名称，而玩家2则以先前名称以结尾的字母开始的名称响应。然后是玩家1的轮胎，直到有人被卡住（建议该游戏作为饮酒游戏，其中对象是乐队/艺术家，电影，城市，首都，著名的数学家或任何浮标。当然必须喝）。正式问题被称为问题 “玩家1有胜利策略吗”.