+1 vote
74 views

Consider the complexity class $CO-NP$ 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?

1. Only $S_1$
2. Only $S_2$
3. Both $S_1$ and $S_2$
4. Neither $S_1$ nor $S_2$

edited | 74 views