为什么 co-P = P

Question

更具体地说，为什么有一个 TM 接受和停止 P 中的任何补语？我明白，有一个 TM 从 P 中拒绝语言 L，但为什么必须有一个接受 L 的补语的 TM？

Answer 1

简单的解决方案：让 L 成为接受语言 L 的图灵机 M 的原始语言。为了计算 L 补码，创建一个新机器 M'，使得 M' 与 M 相同，除非我们将所有转换切换到接受状态M 到“拒绝状态”，并且所有转换到拒绝状态（或“格式错误的转换”）到接受状态。

M' 的运行时间与 M 的运行时间相同。当 M 拒绝/接受时，它将接受/拒绝。

一位评论者问我是否可以提供直觉，说明为什么这对 NP 与 co-NP 不起作用。它有助于从库克-莱文 (Cook-Levin) 对语言 L 在 NP 中的定义开始，这允许清晰定义语言 L' 在 co-NP 中。（使用基于非确定性图灵机的定义会使 co-NP 的定义变得更难）

在 Cook-Levin 定义中，语言 L 是 NP，如果我们有一个“验证”图灵机 V，使得对于 L 中的所有字符串 S，存在多项式长度有界证书字符串 C，使得 V 接受该对（ S, C)（将 V 视为两带输入机，或者将其视为接受输入对的编码）。另外当然还有要求V在多项式时间内完成验证。

例如，对于 3SAT 语言，字符串 S 将是 3SAT 问题实例语句，证书 C 将是变量的真值赋值。验证者 V 将查看真值分配并检查 3SAT 问题实例的每个子句是否都通过该真值分配进行了验证。

所以简而言之，NP 中的语言 L 是由其验证图灵机 V 描述的，我们说：

所以为了描述补语，L'我们有：

如果我们想在 NP vs co-NP 中“尝试相同的技巧”，就像我们在 P vs co-P 中所做的那样，那么机会并不会很好地呈现出来。我们要么需要在确定性图灵机上尝试这个，它可以完全解决每个实例的语言（并且可能没有多项式时间运行界限），或者我们需要看看我们是否可以通过将技巧应用于 V如果我们简单地交换验证机器 V 的结果，我们仍然需要检查每个可能的证书 C，看看给定的字符串 S 是否真的不被 V 接受。