CODEWITHSUNDEEP
computer-sciencecomplexity-theory
jzl106
jzl106

Reputation: 355

Why co-NP is not a subset of NP?

Someone asked me this question and I found I could not answer it even after spending some time re-reading my college textbooks. Specifically, here is the definition of co-NP in many text books:

Definition 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. 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?

  2. With some thoughts, I am not sure the above definition is correct. Given the following definition of NP:

Definition 2

a decision problem A is in NP if and only if there is a polynomial time procedure V (·, ·) and a polynomial time bound p() such that x ∈ A if and only if ∃y.|y| ≤ p(|x|) ∧ V (x, y) = 1

The straightforward definition for co-NP seems to be:

Definition 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

However, Definition 3 is not equivalent to Definition 1, because V(.,.) can be undecidable. Am I missing anything?

Upvotes: -1

Views: 1835

Answers (2)

minh quý lê
minh quý lê

Reputation: 133

Definition 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"
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?

Let A be a coNP language thanks to polynomial-time procedure V as in the definition. The conclusion A is also in NP (by V) is not true. If you check another element x not in A, but it has some certificate so that V(x,u) = 1 then x is also in A since A is in NP. However, this is a contradiction. It should exist another verifier to conclude A is in NP.

Upvotes: 0

user2357112
user2357112

Reputation: 281757

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?

No. V is not a verifier for problem A in the sense of the definition of NP. For V to be a verifier in that sense, we would need to be able to determine x ∈ A by finding a single y such that V(x, y) = 1. With this V, we need to check all possible values of y.

Your proposed "straightforward definition" of co-NP is wrong. For any problem A, we could pick V to be the procedure that ignores its arguments and immediately returns 1. Thus, by your definition, no problems would be in co-NP.

Upvotes: 1

Related Questions