为什么 co-NP 不是 NP 的子集

Why co-NP is not a subset of NP

有人问我这个问题,我花了一些时间重新阅读大学教科书后发现我无法回答。具体来说,这里是很多教科书中对co-NP的定义:

定义 1

"a problem A is in co-NP if and only if there is a polynomial time procedure V (·, ·) and a polynomial bound p() such that x ∈ A if and only if ∀y : |y| ≤ p(|x|), V (x, y) = 1"

  1. 这是否意味着如果 A 在 co-NP 中,那么它必须有一个证书(因为每个 y 都是一个证书)因此,A 也在 NP 中?

  2. 经过一番思考,我不确定上面的定义是否正确。给定以下 NP 定义:

定义 2

"决策问题A在NP中当且仅当存在多项式时间 过程 V (·, ·) 和一个多项式时间界限 p() 使得 x ∈ A 当且仅当 ∃y.|y| ≤ p(|x|) ∧ V (x, y) = 1"

co-NP 的直接定义似乎是:

定义 3

"a decision problem A is in co-NP if and only if there is a polynomial time bound p() such that x ∈ A if and only if ∀y : |y| ≤ p(|x|) there does NOT exist a polynomial time procedure V(.,.) such that V (x, y) = 1"

但是,定义 3 不等同于定义 1,因为 V(.,.) 可能是不可判定的。我错过了什么吗?谢谢!

Doesn't this mean that if A is in co-NP, then it MUST have a certificate (because every y would be a certificate) and therefore, A is also in NP?

没有。 V 不是 NP 定义意义上的问题 A 的验证者。为了让 V 在这个意义上成为验证者,我们需要能够通过找到一个满足 V(x, y) = 1 的 y 来确定 x ∈ A。有了这个 V,我们需要检查 y 的所有可能值.

你提议的"straightforward definition" co-NP 是错误的。对于任何问题 A,我们可以选择 V 作为忽略其参数并立即 returns 1 的过程。因此,根据您的定义,co-NP 中不会出现任何问题。