Consider the complexity class \(๐ถ๐โ๐๐\) as the set of languages \(L\) suchโฆ
2019
Consider the complexity classย \(๐ถ๐โ๐๐\)ย as the set of languagesย \(L\) such thatย \(\overline{L} \in NP\), and the following two statements:
\(S_1: \: P \subseteq CO-NP\)
\(S_2: \: \text{ If } NP \neq CO-NP, \text{ then } P \neq NP\)
Which of the following is/are correct?
- A.
Onlyย
\(๐_1\) - B.
ย Onlyย
\(๐_2\) - C.
ย Bothย
\(๐_1\)andย\(๐_2\) - D.
ย Neitherย
\(๐_1\)norย\(๐_2\)
Attempted by 111 students.
Show answer & explanation
Correct answer: C
Answer: Both statements are true.
Key facts: CO-NP is the class of languages whose complements lie in NP. The class P is closed under complement (if a language is in P then its complement is also in P), and P โ NP.
Proof that the first statement is true: For any language L in P, the complement of L is also in P because P is closed under complement. Since P โ NP, the complement of L is in NP. By definition of CO-NP, this means L โ CO-NP. Therefore P โ CO-NP.
Proof that the second statement is true: Prove the contrapositive. If P = NP, then NP = P is closed under complement, so NP is closed under complement and thus NP = CO-NP. Taking the contrapositive of this implication gives: if NP โ CO-NP then P โ NP.
Conclusion: Both statements hold, so the correct choice is that both are true.
A video solution is available for this question โ log in and enroll to watch it.