The Gateway to Computer Science Excellence
+1 vote

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$
in Algorithms by
edited by | 166 views

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,375 questions
60,613 answers
95,431 users