recategorized by
7,996 views
13 votes
13 votes

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?

recategorized by

5 Answers

Best answer
22 votes
22 votes

Clique is in NPC. By definition of NPC, all NP problems can be reduced to Clique in polynomial time. So, if clique can be solved in polynomial time, any NP problem can also be solved in polynomial time making P=NP and hence P=NP=NPC. 

http://gatecse.in/wiki/NP,_NP_Complete,_NP_Hard

selected by
6 votes
6 votes
if there is a polynomial time algorithm is  discovered for clique , then there is polynomial time algo for all NP complete problems.

hence option D is correct
1 votes
1 votes

NPC should be a subset of P=NP.

If P=NP=NPC then that means that all P and NP problems are NP Complete and thus NP Hard. This means that every P and NP problem is polynomial time reducible to every other problem. This is not true.

Hence C.

Answer:

Related questions

10 votes
10 votes
3 answers
3
Ishrat Jahan asked Oct 27, 2014
7,046 views
For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?If X can be solved in polynomial time, then so can YX is NP-c...