有人问我这个问题，我发现即使花了一些时间重新阅读大学教科书，我也无法回答。具体来说，这是很多教科书中对co-NP的定义：
定义1
“问题 A 属于 co-NP 当且仅当存在多项式时间过程 V (·,·) 和多项式界限 p() 使得 x ∈ A 当且仅当 ∀y : |y| ≤ p (|x|)，V (x, y) = 1"
这不是意味着如果 A 在 co-NP 中，那么它必须有一个证书（因为每个 y 都是一个证书），因此 A 也在 NP 中？
经过一些思考，我不确定上面的定义是否正确。给出 NP 的以下定义：
定义2
“决策问题 A 属于 NP 当且仅当存在多项式时间 过程 V (·,·) 和多项式时间界限 p()，使得 x ∈ A 当且仅当 ∃y.|y| ≤ p(|x|) ∧ V (x, y) = 1"
co-NP 的简单定义似乎是：
定义3
“决策问题 A 属于 co-NP 当且仅当存在多项式时间界限 p() 使得 x ∈ A 当且仅当 ∀y : |y| ≤ p(|x|) 不存在多项式时间过程 V(.,.) 使得 V (x, y) = 1"
然而，定义3并不等价于定义1，因为V(.,.)可能是不可判定的。我错过了什么吗？谢谢！
这是否意味着如果 A 在 co-NP 中，那么它必须有一个证书（因为每个 y 都是一个证书），因此 A 也在 NP 中？
不。从 NP 定义的意义上来说，V 不是问题 A 的验证者。为了使 V 成为这个意义上的验证者，我们需要能够通过找到单个 y 来确定 x ∈ A，使得 V(x, y) = 1。有了这个 V，我们需要检查 y 的所有可能值.
您提出的 co-NP 的“直接定义”是错误的。对于任何问题 A，我们可以选择 V 作为忽略其参数并立即返回 1 的过程。因此，根据您的定义，co-NP 中不会出现任何问题。
定义1
“问题 A 属于 co-NP 当且仅当存在多项式时间过程 V (·,·) 和多项式界限 p() 使得 x ∈ A 当且仅当 ∀y : |y| ≤ p( |x|), V(x,y) = 1"
这是否意味着如果 A 在 co-NP 中，那么它必须有一个证书（因为每个 y 都是一个证书），因此 A 也在 NP 中？
借助定义中的多项式时间过程 V，让 A 成为 coNP 语言。结论 A 也属于 NP（通过 V）是不正确的。如果您检查不在 A 中的另一个元素 x，但它有一些证书使得 V(x,u) = 1，则 x 也在 A 中，因为 A 在 NP 中。然而，这是一个矛盾。应该存在另一个验证者来断定 A 属于 NP。