NP完全减少

我对于与NP完全问题有关的减少有这个困惑。假设我们有两个问题R和S不知道在NP中。现在如果我们有一个众所周知的NP完全问题的多项式时间减少到R，并且我们也有一个从S到NP完全问题的多项式时间减少。对于R和S问题可以说什么呢？它们是NP完成的还是NP很难？NP完全减少

我投票结束这个问题作为题外话，因为这不是关于编程，而是数学。 –

如果一个NP完全问题在多项式时间内减少到R，那么NP中的所有问题都是这样的;因此，R是NP-Hard。

如果S简化为一个NP完全问题，则S是NP。

两者都不一定是NP完全;我们不知道R是否是NP（也许它是不可判定的），或者S是否是NP-Hard（也许它是微不足道的？）。

2013-02-05 20:35:13 Patrick87

谢谢你，我有我的心中另一个疑问让我们说一个问题L在NP是减少到一个问题L'..然后可以说什么问题L' – user2044593

@ user2044593没有任何实质：L'可能NP-Complete，NP，但不是NP-Complete（假设P！= NP）或P。请注意，任何问题都会自行消除。即使你抛出这个微不足道的情况，也不难发现问题L'，这样L'和L就可以通过基本相同的算法解决。 – Patrick87

感谢您的澄清！ – user2044593

回答