The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+10 votes

Assuming P ≠ NP, which of the following is **TRUE**?

- NP-complete = NP
- NP-complete $\cap$ P = $\phi$
- NP-hard = NP
- P = NP-complete

+20 votes

Best answer

Answer is (B) NP-complete $\cap P = \phi$

Since, P $\neq$ 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 $\neq$ NP, $X \notin $ 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 \notin $P, none of the other NP-complete problems also cannot be in P.

Since, P $\neq$ 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 $\neq$ NP, $X \notin $ 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 \notin $P, none of the other NP-complete problems also cannot be in P.

+6 votes

Every problem in P is also in NP.

Given that P != NP, it means that there exists a problem which is in NP and not in P.

**Every NP-Complete problem has the property that it is in NP and if it is in P then every problem in NP is also in P.**

Now suppose if NP-Complete ∩ P is non-empty this implies there exists a problem which is NP-Complete as well as in P.

But then from the definition of NP-Complete, every problem in NP must be in P.

That is NP = P, which is contradicting the given condition.

Hence our only assumption: "NP-Complete ∩ P is non-empty" must be wrong.

So NP-Complete & P must be disjoint if P!=NP.

+4 votes

This pic clears this question.

(a) As NP complete problem are hardest problem in NP class.Every NP complete problem is in NP, but vice versa is not true. Moreover NP Complete problem also should be satisfy NP hard property. So, all NP problem shouldnot reduced to NP Complete.

A fast solution to any NP-Complete problem would mean that as long as you can *verify* proposed solutions to a problem you would *never* need to search through a substantial fraction of the search space to find solutions; there would *always* be a faster way. Therefore most mathematician thought there is no solution faster than NP complete (Which cannot be a case for NP)

(b) If a problem is in NP Complete then it must be in NP . Means if X is a NP Complete problem , then X must be in NP. Here NP!=P , that is why $$NPComplete\cap P=\phi$$

(c) NP Hard=NP

What does NP-hard mean? A lot of times you can solve a problem by reducing it to a different problem. I can reduce Problem B to Problem A if, given a solution to Problem A, I can easily construct a solution to Problem B. (In this case, "easily" means "in polynomial time.")

Only NP complete problem polynomial time reducible to NP Hard problem. But all NP problem not in NPC. So, all NP problem cannot be reduced to NP Hard .http://gatecse.in/p-np-np-complete-np-hard/

(d) NP Complete problem is the set of problems, for which NP problems can be reduced to NP Complete.And we know . If NP problem can be solved quickly, then NP Complete problem also can solved quickly.And according to the diagram sometimes P=NP and sometimes P!=NP. NP complete is a subset of NP. So, P=NP Complete is not correct equation.

- All categories
- General Aptitude 1.1k
- Engineering Mathematics 4.5k
- Digital Logic 1.9k
- Programming & DS 3.3k
- Algorithms 2.9k
- Theory of Computation 3.6k
- Compiler Design 1.4k
- Databases 2.7k
- CO & Architecture 2.4k
- Computer Networks 2.7k
- Non GATE 901
- Others 1.2k
- Admissions 246
- Exam Queries 433
- Tier 1 Placement Questions 17
- Job Queries 42
- Projects 4

32,330 questions

39,146 answers

108,246 comments

36,501 users