The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+7 votes
1.2k views

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)?

asked in Theory of Computation by Veteran (99.8k points)
recategorized by | 1.2k views
+1

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 Answers

+13 votes
Best answer

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

answered by Veteran (355k points)
selected by
0
Sir, why not option C?
+1
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.
+1
"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
yes, and that is the "a polynomial time algorithm" from the beginning.
+5 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
answered by Boss (11.5k points)
0 votes

Answer is option C. 

No problem can be reduced to either $\emptyset $ or $\Sigma^*$.

http://cs.stackexchange.com/q/7453/15154

answered by Active (1.6k points)
edited by
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,939 questions
45,453 answers
131,195 comments
48,209 users