recategorized by
483 views
1 votes
1 votes

Assuming $P \neq NP$, Which of the following statements are TRUE?

  1. There is no language in $NP$ which has a Deterministic  Polynomial time algorithm.
  2. There is no language in $P$ which has a Deterministic Polynomial time algorithm.
  3. $NP$ is not a subset of $P$
  4. $P$ is not a subset of $NP$
recategorized by

1 Answer

0 votes
0 votes
Applied Course 2019 Mock1-20
(A) $\rightarrow$ FALSE: All class $P$ problems are subset of $NP$ and have Deterministic polynomial time algorithm.
(B) $\rightarrow$ FALSE: $P$ is subset of $NP$.
(C) $\rightarrow$ TRUE: $NP$ is not a subset of $P$. If NP is a subset of $P$ then $P=NP$ contradicts the assumption $P \neq NP$.
(D) $\rightarrow$ FALSE: $P$ is not subset of $NP$.
Answer:

Related questions

1 votes
1 votes
1 answer
3
Applied Course asked Jan 16, 2019
502 views
Suppose a radix sort was done on the following set of numbers, in binary i.e,$[11, 10, 3, 14, 12, 2, 8, 15, 2]$. How many passes of counting sort would be performed _____...