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)? Theory of Computation gatecse-2014-set1 algorithms p-np-npc-nph normal out-of-syllabus-now + – go_editor asked Sep 28, 2014 • recategorized Aug 10, 2017 by srestha go_editor 8.1k views answer comment Share Follow See 1 comment See all 1 1 comment reply Pranav Kant Gaur commented Feb 6, 2017 i edited by Pranav Kant Gaur Feb 12, 2017 reply Follow Share http://cs.stackexchange.com/q/7453/15154 Shouldn't the answer be (C) instead? Considering the nature of $\Sigma^*$ and $\emptyset$ which belong to class P but no other problem can be reduced to them. 3 votes 3 votes Please log in or register to add a comment.
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 Arjun answered Oct 3, 2014 • selected Oct 8, 2014 by Arjun Arjun comment Share Follow See all 9 Comments See all 9 9 Comments reply Shreya Roy commented Nov 4, 2016 reply Follow Share Sir, why not option C? 1 votes 1 votes Arjun commented Nov 4, 2016 reply Follow Share If D is true, C can't be true :) IT says NPC is a subset of NP=P, which is not possible as if 1 NPC problem is reduced to a P problem, then all NPC problem can also be reduced to P. 5 votes 5 votes Shreya Roy commented Nov 4, 2016 reply Follow Share "a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph.".this means this NPC problem is polynomial solvable hence all NP are polynomial solvable since all NP reduces to NPC so NP=P.. But Sir, does it mean this NPC problem(or P problem since NP=P) can be reduced to some another P problem.. Solving in Polynomial time means it is reducible to another P problem? 2 votes 2 votes Arjun commented Nov 4, 2016 reply Follow Share yes, and that is the "a polynomial time algorithm" from the beginning. 3 votes 3 votes gmrishikumar commented Sep 11, 2018 i edited by gmrishikumar Sep 11, 2018 reply Follow Share NPC should be a subset of P=NP. If P=NP=NPC then that means that all P and NP problems are also NP Hard i.e. every P and NP problem can be converted to every other problem. This cannot be true. Hence C should the answer. 2 votes 2 votes Divy Kala commented Oct 6, 2018 reply Follow Share P is not a subset of NPC, and this is unconditionally true. Answer is C https://cs.stackexchange.com/questions/94201/if-p-np-why-is-p-a-subset-of-npc 4 votes 4 votes Aks9639 commented Sep 8, 2019 reply Follow Share i got it , huhhhhh! this is the correct answer of correct question 0 votes 0 votes JashanArora commented Jan 19, 2020 reply Follow Share According to D, $P=NP=NPC$ 3SAT is $NPC$. Can 3SAT be reduced to $\phi$ ? (which is in P) The answer is no. Hence, C is the correct choice. D is the correct choice iff we exclude $\phi$ and $\Sigma^*$ from $P$ 0 votes 0 votes Ayush271 commented Oct 31, 2021 reply Follow Share All NPC can be reduced to P but all the P problems are not NPC.Means every other problem cannot be reduced to a P problem. If it is true now then it could have been true earlier also . There are only some set of problems which are NPC and now they all can be solved in polynomial time by solving clique problem .So they comes inside P set.But the number of NPC problems are still fix. 1 votes 1 votes Please log in or register to add a comment.
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 Sankaranarayanan P.N answered Oct 3, 2014 Sankaranarayanan P.N comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes Answer is option C. No problem can be reduced to either $\emptyset $ or $\Sigma^*$. http://cs.stackexchange.com/q/7453/15154 Pranav Kant Gaur answered Feb 6, 2017 • edited Feb 12, 2017 by Pranav Kant Gaur Pranav Kant Gaur comment Share Follow See all 0 reply Please log in or register to add a comment.
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. gmrishikumar answered Sep 11, 2018 gmrishikumar comment Share Follow See all 0 reply Please log in or register to add a comment.