CMI2010-A-10

Question

Consider the following statements.

1. NP-complete problems are those that we know we can never solve efficiently.
2. If we find an efficient algorithm for one NP-complete problem, then we can solve all NP-complete problems efficiently.
3. Checking whether a number is a prime is an NP-complete problem.

Then:

• A. $1$ and $2$ are true but $3$ is false.
• B. $1$ and $3$ are false but $2$ is true.
• C. $2$ and $3$ are true but $1$ is false.
• D. All three statements are false.

Answer 1

1)False, because  NP-complete problems are those for which we don't have efficient(polynomial time) algorithm but still, it has not yet mathematically proven that we can never solve efficiently. i.e. we may solve it efficiently in that case P=NP

2) True because from the definition of NP-Complete problem it follows "NPC problems are set of problems in NP that are as hard as any problem in NP"

3)False, Checking whether a number is a prime is in P. This a famous groundbreaking work by prof Manindra Agrawal of IIT-K and his two undergraduate students  namely AKS primality testing algorithm which shows that testing whether a number is a prime is in P
For more details about AKS algorithm, you may refer this: https://en.wikipedia.org/wiki/AKS_primality_test

Hence, Option B is the correct answer