np-complete - 我如何证明 2-CNF 不是 NP 完全的？

Question

我想知道如何证明 2-CNF 不是 NP-hard 或 NP complete？

Answer 1

已知 2-CNF 可满足性在 P 中。因此，如果您能够证明它不是 NP 完全的，则可以得出 P ≠ NP。因此，没有人知道如何证明这一点。