从NP完整问题减少到某些问题$ x $意味着NP $中的$ x ？

Question

我在解决以下问题方面遇到问题：

考虑到一些问题$ x $。如果存在（例如）$ mbox {sat} $到$ x $，$（ mbox {sat} leq_ {p} x）$，则存在多项式时间的时间，并且由于我们知道$ mbox {sat}} $是$ mbox {np-complete} $，要证明$ x $是$ mbox {np-complete} $是否有必要通过某些第三方算法来证明$ x in mbox {np} $？

如果是，那为什么呢？

Answer 1

还原仅表明X至少与SAT（NP-HARD）一样硬。这可能意味着X中的X涉嫌比NP（例如Pspace或Exptime）更难。要证明X是NP填充，您必须证明它也位于NP中。如果您尝试一下，您会发现您可以轻松地将SAT减少到不怀疑在NP中的注册时间问题。这个想法是，您的减少表明X至少与SAT一样困难，但是与NP问题相比，问题要困难得多。

Answer 2

这是一个非常普遍的负面答案。考虑以下语言：$$ l = { langle m，x，o rangle：m text {outputs} o text {on Input} x }，$ o whene $ o in sigma^* in sigma^* cup { bot } $和$ langle cdot， cdot， cdot rangle $是任何poly Time配对函数（我们甚至可以要求它是logspace，甚至更弱）。某些Turing机器接受的每种语言都可以减少到Poly Time的$ L $，但是$ L $不可计算。