algorithm - 为什么 P ⊆ co-NP？

Question

我见过几个地方简单地指出已知 P 是 NP 和 co-NP 的交集的一个子集。证明 P 是 NP 的子集的证明并不难找到。所以为了证明它是交集的一个子集，剩下要做的就是证明 P 是 co-NP 的一个子集。这可能是什么证据？非常感谢！

Answer 1

类P在补集下是封闭的：如果 L 是 P 中的一种语言，则 L 的补集也在P中。您可以通过为 L 采用任何多项式时间决策器并切换接受和拒绝状态来看到这一点；这台新机器现在决定 L 的补码，并在多项式时间内完成。

语言 L 在 co- NP中当且仅当它的补码在NP中。所以考虑任何语言 L ∈ P。L 的补码也在P中，因此 L 的补码在NP中（因为P ⊆ NP）。因此，L 在 co- NP中。因此，P ⊆ co- NP。

希望这可以帮助！

Answer 2

这样想吧。考虑类 co-P。由于 P 在恭维下是封闭的，所以 P=co-P。

还应该清楚 co-P 是 co-NP 的一个子集，因为 P 包含在 NP 中。由于 P = co-P，因此 P 包含在 co-NP 中。