NP-Hard的解決方案在多項式時間內無法驗證嗎？

Question

我正在經歷複雜類。需要明確NP_Hard問題。

感謝，在多項式時間 Hareendra

Answer 1

問題覈查的是NP。 NP是NEXPTIME的一個子集。因此，NEXPTIME \ NP不是空的，它的問題在多項式時間內是不可驗證的。根據定義，NEXPTIME \ NP中的問題是NP難題。

請參閱Wikipedia - EXPTIME。