NP-Hard中是否存在解在多项式时间内不可验证的决策问题？

Question

我正在学习复杂类。需要弄清楚NP_Hard问题。

谢谢，Hareendra

Answer 1

在多项式时间内可验证的问题是NP。NP是NEXPTIME的真子集。因此，NEXPTIME\NP不是空的，并且它的问题在多项式时间内是不可验证的。根据定义，NEXPTIME\NP中的问题是NP难的。

参见Wikipedia - EXPTIME。