如果 A 可以在多项式时间内简化为 B，那么您所知道的就是 B 比 A 更难。在您的情况下，如果 A 是 NP 完全的，则 B 是 NP 困难的。
如果 B 也恰好处于 NP 状态，那么 B 将是 NP 完全的（因为 NP 完全意味着同时处于 NP 状态并且是 NP-hard 状态）。
然而，没有什么可以阻止你将 A 简化为不属于 NP 的问题。例如，将 NP 中的任何问题简化为停止问题（除了 NP 难问题之外还无法判定的问题）是微不足道的：
Construct the following program:
Test all possible solutions for A.
If one of them is successful halt and otherwise enter an infinite loop.
A has a solution if-and-only if that program halts
If A can be reduced to B in polynomial time all you know is that B is harder than A. In your case, if A is NP-complete, B is NP-hard.
If B also happens to be in NP then B will be NP-complete (since NP-complete means being both in NP and being NP-hard at the same time).
However, nothing stops you from reducing A to a problem that is not in NP. For example, it is trivial to reduce any problem in NP to the halting problem - a problem that is undecideable in addition to being NP-hard:
Construct the following program:
Test all possible solutions for A.
If one of them is successful halt and otherwise enter an infinite loop.
A has a solution if-and-only if that program halts
Since problem A can be reduced to problem B in polynomial time, any solution to problem B can be used to find a solution to A. Or more simply, solving A cannot be harder than solving B. Since we know A is NP-complete, which class of problems is at least as hard as NP-complete problems?
For reference you might also want to take a look at the wikipedia articles on NP-Hard (specifically the 2nd sentence), NP-Complete. and Reduction.
如果A是NP完全的，那么它也必然是NP。这反过来意味着 A 的每个潜在解都可以在多项式时间内得到验证，这意味着 B 也是如此（因为 A 在多项式时间内可简化为 B）。因此 B 是 NP；不必将其声明为单独的条件。
If A is NP-Complete, then it is also necessarily NP. This in turns means that every potential solution for A can be verified in polynomial time, which implies that the same is true for B (since A is reducible to B in polynomial time). Hence B is NP; it doesn't have to be stated as separate condition.
发布评论
评论（3）
如果 A 可以在多项式时间内简化为 B，那么您所知道的就是 B 比 A 更难。在您的情况下，如果 A 是 NP 完全的，则 B 是 NP 困难的。
如果 B 也恰好处于 NP 状态，那么 B 将是 NP 完全的（因为 NP 完全意味着同时处于 NP 状态并且是 NP-hard 状态）。
然而，没有什么可以阻止你将 A 简化为不属于 NP 的问题。例如，将 NP 中的任何问题简化为停止问题（除了 NP 难问题之外还无法判定的问题）是微不足道的：
If A can be reduced to B in polynomial time all you know is that B is harder than A. In your case, if A is NP-complete, B is NP-hard.
If B also happens to be in NP then B will be NP-complete (since NP-complete means being both in NP and being NP-hard at the same time).
However, nothing stops you from reducing A to a problem that is not in NP. For example, it is trivial to reduce any problem in NP to the halting problem - a problem that is undecideable in addition to being NP-hard:
由于问题 A 可以在多项式时间内简化为问题 B，因此问题 B 的任何解都可以用来找到 A 的解。或者更简单地说，解决 A 不可能比解决 B 更难。因为我们知道 A 是 NP 完全的，哪一类问题至少与 NP 完全问题一样难？
作为参考，您可能还想查看有关 NP-Hard 的维基百科文章（特别是第二句话），NP-Complete。
和减少。
Since problem A can be reduced to problem B in polynomial time, any solution to problem B can be used to find a solution to A. Or more simply, solving A cannot be harder than solving B. Since we know A is NP-complete, which class of problems is at least as hard as NP-complete problems?
For reference you might also want to take a look at the wikipedia articles on NP-Hard (specifically the 2nd sentence), NP-Complete.
and Reduction.
如果A是NP完全的，那么它也必然是NP。这反过来意味着 A 的每个潜在解都可以在多项式时间内得到验证，这意味着 B 也是如此（因为 A 在多项式时间内可简化为 B）。因此 B 是 NP；不必将其声明为单独的条件。
If A is NP-Complete, then it is also necessarily NP. This in turns means that every potential solution for A can be verified in polynomial time, which implies that the same is true for B (since A is reducible to B in polynomial time). Hence B is NP; it doesn't have to be stated as separate condition.