Applied Course | Mock GATE | Test 1 | Question: 20

Question

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

• A. There is no language in $NP$ which has a Deterministic  Polynomial time algorithm.
• B. There is no language in $P$ which has a Deterministic Polynomial time algorithm.
• C. $NP$ is not a subset of $P$
• D. $P$ is not a subset of $NP$

Answer 1

(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$.