recategorized by
1,547 views
8 votes
8 votes

Suppose a language $L$ is $\mathbf{NP}$ complete. Then which of the following is FALSE?

  1. $L \in \mathbf{NP}$
  2. Every problem in $\mathbf{P}$ is polynomial time reducible to $L$.
  3. Every problem in $\mathbf{NP}$ is polynomial time reducible to $L$.
  4. The Hamilton cycle problem is polynomial time reducible to $L$.
  5. $\mathbf{P} \neq \mathbf{NP}$ and $L \in \mathbf{P}$.
recategorized by

3 Answers

Best answer
8 votes
8 votes

Option E leads to a contradiction, hence is false.

We know that $L$ is $\mathbf{NPC}$, hence  $\in \mathbf{NP}$. If $\mathbf{P} \neq \mathbf{NP}$, then $L$ can't be in $\mathbf{P}$

edited by
10 votes
10 votes
A) A Problem is NP Complete Means, It is NP Hard & Belongs To NP. L Is NP Complete, it belongs to NP so correct.

B) NP Complete is as hard as every other problem in NP. As P is subset of NP (Every P Problem is NP) B Is correct.

C) This is correct, NP Complete = As hard as all other NP Problems. All can be reduces to it.

D) Hamilton cyle is NP Complete, so This is correct.

E) This created contradiction. If P != NP Then NP Complete problem can not belong to P.
2 votes
2 votes
E is false. First 4 options follow from the definition of NPC which requires all problems in NP be reducible to any NPC problem and any NPC problem must be in NP.
Answer:

Related questions