algorithm - 从 NP Complete 到其他问题的多项式时间缩减

Question

谁能解开我的疑惑？

假设我有一个已知属于 NP-complete 的问题 A。我还有另一个问题 B，我们不知道其复杂度等级。

如果我在多项式时间内将 A 减少到 B。我们可以说 B 也是 NP-Complete。

但是.. 如果我在多项式时间内将 B 减少到 A。为什么我不能在 NP-Complete 中也说 B？

Answer 1

if I reduce A to B in polynomial time . we can say B also is in NP-Complete.

不，我们可以说 B 是 NP-hard。完整性也需要 NP 的成员资格，这与假设不符。

例如，我们可以将 3SAT 简化为停机问题。停机问题不在 NP 中(它甚至不可判定)。

if I reduce B to A in polynomial time . why can't I say B also in NP-Complete?

我们可以说 B 在 NP 中。 B 的一种算法是使用归约然后解决 A。B 可能是一个简单的问题，例如“输入的长度是奇数”。