证明一个问题是 NP-hard 而不是 NP-complete in not in P
Prove a problem that is NP-hard and not NP-complete in not in P
如果A不是NP难的，但不是NP完全的，那么证明A不在P中。
如果存在 NP 完全问题 B，使得 B 在多项式时间内可归约为 A，则 A 是 NP-hard。如果 A 在 NP 中并且所有 NP 问题都可以在多项式时间内简化为 A，则 A 是 NP-complete。但是 A 不是 NP 完全的，因此其中一个或两个条件必须为假。如果 A 不在 NP 中，则 A 不在 P 中。另一种情况是存在至少一个在多项式时间内不可简化为 A 的 NP 问题。这就是我被困的地方。我如何知道存在可还原的 NP 完全问题和不可还原为 A 的 NP 问题不在 P 中？
如果问题 A 是 NP-hard，则所有 NP 问题都可以在多项式时间内归结为 A。
证明：
由于问题 A 不是 NP-Complete，因此存在上述定义的问题 B。 NP中的所有问题C都可以在多项式时间内归结为B，然后B在多项式时间内归结为A。多项式时间算法的组合是多项式的，所以C可以在多项式时间内归结为A。
--
因为A是NP-Hard而不是NP-Complete，所以A一定不在NP中，因此A也不在P中。
如果A不是NP难的，但不是NP完全的，那么证明A不在P中。
如果存在 NP 完全问题 B，使得 B 在多项式时间内可归约为 A，则 A 是 NP-hard。如果 A 在 NP 中并且所有 NP 问题都可以在多项式时间内简化为 A，则 A 是 NP-complete。但是 A 不是 NP 完全的，因此其中一个或两个条件必须为假。如果 A 不在 NP 中，则 A 不在 P 中。另一种情况是存在至少一个在多项式时间内不可简化为 A 的 NP 问题。这就是我被困的地方。我如何知道存在可还原的 NP 完全问题和不可还原为 A 的 NP 问题不在 P 中？
如果问题 A 是 NP-hard，则所有 NP 问题都可以在多项式时间内归结为 A。
证明： 由于问题 A 不是 NP-Complete，因此存在上述定义的问题 B。 NP中的所有问题C都可以在多项式时间内归结为B，然后B在多项式时间内归结为A。多项式时间算法的组合是多项式的，所以C可以在多项式时间内归结为A。
--
因为A是NP-Hard而不是NP-Complete，所以A一定不在NP中，因此A也不在P中。