Register

UGC NET CSE | June 2019 | Part 2 | Question: 67

• edited by
1,203 views
1 votes
1 votes

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 by
User Avatar

1 Answer

Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
2 answers
1
Arjun asked Jul 2, 2019
1,666 views
UGC NET CSE | June 2019 | Part 2 | Question: 61
Match List-I with List-II: ... ii) (a) - (ii); (b)-(i); (c)-(iv); (d)-(iii) (a) - (iii); (b)-(i); (c)-(iv); (d)-(ii)
Match List-I with List-II:$$\begin{array}{|c|c|c|c|} \hline {} & \text{List-I} & {} & \text{List-II} \\ \hline (a) & \text{Prim’s algorithm} & (i) & O(V^3 \log V) \\ \h...
User Avatar
7 votes
7 votes
3 answers
3
Arjun asked Jul 2, 2019
3,327 views
UGC NET CSE | June 2019 | Part 2 | Question: 64
Which of the following is best running time to sort $n$ integers in the range $0$ to $n^2-1$? $O(\text{lg } n)$ $O(n)$ $O(n\text { lg }n)$ $O(n^2)$
Which of the following is best running time to sort $n$ integers in the range $0$ to $n^2-1$?$O(\text{lg } n)$$O(n)$$O(n\text { lg }n)$$O(n^2)$
User Avatar
1 votes
1 votes
1 answer
4
Arjun asked Jul 2, 2019
1,881 views
UGC NET CSE | June 2019 | Part 2 | Question: 65
Which of the following is application of depth-first search? Only topological sort Only strongly connected components Both topological sort and strongly connected components Neither topological sort nor strongly connected components
Which of the following is application of depth-first search?Only topological sortOnly strongly connected componentsBoth topological sort and strongly connected components...
User Avatar
Link Copied!