Assuming P! = NP, which of the following is true?

(A) NP-complete = NP

(B) NP-complete / cap P = / Phi

(C) NP-hard = NP

(D) P = NP-complete

Answer is B, see explanations.

Explanation:

Answer is (B) NP-complete∩P=ϕ

Since, P≠NP, there is at least one problem in NP, which is harder than all P problems. Lets take the hardest such problem, say X. Since, P≠NP, X∉P.

Now, by definition, NP-complete problems are the hardest problems in NP and so X problem is in NP-complete. And being in NP, X can be reduced to all problems in NP-complete, making any other NP-complete problem as hard as X. So, since X∉P, none of the other NP-complete problems also cannot be in P.

B. NP-complete / cap P = / Phi

Explanation:

The is because no NP-Complete problem can be solved in polynomial time.

Assuming one NP-Complete problem can be solved in polynomial time, then all NP problems can solved in polynomial time. If that is the case, then NP and P set become same which contradicts the given condition.