Aspire Faculty ID #19285 · Topic: UGC NET Computer Science June 2019 (Paper II) · Just now
UGC NET Computer Science June 2019 (Paper II)

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:$ If $NP\ne CO-NP$, then $P\ne NP$

Which of the following is/are correct?

Solution

Statement $S_1$ is true.

Class $P$ is closed under complement. Also, $P\subseteq NP$.

So,

$P\subseteq CO-NP$

Statement $S_2$ is also true.

If $P=NP$, then since $P$ is closed under complement, we would get

$NP=CO-NP$

But the statement says $NP\ne CO-NP$.

Therefore, $P\ne NP$.

Hence, both $S_1$ and $S_2$ are correct.

Previous 10 Questions — UGC NET Computer Science June 2019 (Paper II)

Nearest first

Next 10 Questions — UGC NET Computer Science June 2019 (Paper II)

Ascending by ID
1
Consider the following steps: $S_1$: Characterize the structure of an optimal solution $S_2$: Compute the value of an o…
Topic: UGC NET Computer Science June 2019 (Paper II)
2
Consider the following properties with respect to a flow network $G=(V,E)$ in which a flow is a real-valued function $f…
Topic: UGC NET Computer Science June 2019 (Paper II)
3
Consider the following statements: $S_1$: For any integer $n>1$, $a^{\phi(n)}\equiv 1\ (\text{mod }n)$ for all $a\in…
Topic: UGC NET Computer Science June 2019 (Paper II)
4
Which data structure is used by the compiler for managing variables and their attributes?
Topic: UGC NET Computer Science June 2019 (Paper II)
5
On translating the expression given below into quadruple representation, how many operations are required?$(ij)+(e+f)(a…
Topic: UGC NET Computer Science June 2019 (Paper II)
6
Replacing the expression $4*2.14$ by $8.56$ is known as:
Topic: UGC NET Computer Science June 2019 (Paper II)
7
Shift-reduce parser consists of:$(a)$ Input buffer $(b)$ Stack $(c)$ Parse table Choose the correct option from those …
Topic: UGC NET Computer Science June 2019 (Paper II)
8
How many states are there in a minimum state automata equivalent to regular expression given below? Regular expression …
Topic: UGC NET Computer Science June 2019 (Paper II)
9
Match List-I with List-II: List-I List-II (a) $\overlin…
Topic: UGC NET Computer Science June 2019 (Paper II)
10
How can the decision algorithm be constructed for deciding whether context-free language $L$ is finite? $(a)$ By constr…
Topic: UGC NET Computer Science June 2019 (Paper II)
Ask Your Question or Put Your Review.

loading...