指数减少与多项式还原

Question

我很难理解减少。假设您有一个NP完成的决策问题。另外，另一个问题B可以从A中减少。

如果：

1）减少是在多项式时间内完成的
2）减少是在指数时间内完成的

我知道，如果A将A简化为B，则意味着，如果我们知道如何解决B，那么解决A将很容易。但是我不明白1和2表示什么。

说这是正确的1）
B与A同一班级

和2）
那B>然后NP完成？

Answer 1

实际上，根据要减少的课程，您需要谨慎对待所做的减少。

例如，要保留$ p $，您需要执行$ logspace $ reductions。对于$ np $，您需要$ p $ reductions。

我也担心您会扭转降低：要证明问题$ b $在$ np $中，您需要（多项式）将其减少到$ np $中的问题$ a $ a $。这意味着如果您如何解决$ np $中的$ a $ a $，则可以通过将其减少到$ a $来解决$ b $。

因此，总结一下，如果$ b leq_p a $和$ a in np $，则在np $中$ b 。实际上，NP算法很清楚：执行您的减少（多项式时间），然后求解您简化为$ a $的实例（以$ np $为单位）。

但是，如果减少是指数级的，那么我们不能说$ b $，除了它在$ exptime^{np} $中，即您可以在指数时间内使用$ NP $ oracle解决它。实际上，仅在Exptime $中说$ b ，因为NP Oracle不会添加电源。