为什么co=P

Question

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

Answer 1

简单的解决方案:设L是图灵机M的原始语言，它接受L语言。为了计算L-补码，创建一个新机器M‘使M’与M相同，除非我们将所有转换到M的接受状态转换为“拒绝状态”，而所有转换到拒绝状态(或“畸形转换”)切换到接受状态。

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

一位评论者问，我是否可以提供直觉，为什么这不适用于NP和合作NP。这有助于在这里开始库克莱文定义的语言L是在NP，这允许一个明确的定义语言L‘在共同NP。(使用基于非确定性图灵机的定义会使co的定义更加困难)

在Cook-Levin定义中，L是NP语言，如果我们有一个“验证”图灵机V，使得对于L中的所有字符串S，都有一个多项式长度有界的证书字符串C，使得V接受这对(S，C) (把V看作是一台双带输入机器，或者认为它接受输入对的编码)。此外，我们还要求V在多项式时间内完成验证。

例如，对于3 3SAT语言，字符串S将是3 3SAT问题实例语句，证书C将是变量的真值分配。验证器V将查看真值赋值，并检查3 3SAT问题实例的每个子句是否与该真理赋值一起得到验证。

所以简单地说，NP中的L语言是用它的验证图灵机V来描述的，我们说：

​

​

因此，为了描述补语，L‘我们有：

​

​

如果我们想对NP和合作NP“尝试同样的伎俩”，那么这个机会并不是很好。我们要么需要对一个完全解决每个实例的语言的确定性图灵机(并且可能不会有一个多项式时间运行界)试一试，要么我们需要看看我们是否能够通过对V应用这个技巧来使它工作。如果我们简单地把结果换成验证机器V，我们仍然需要检查每一个可能的证书C，看看给定的字符串S是否真的不为V所接受。