in Theory of Computation recategorized by
6,779 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)?

in Theory of Computation recategorized by
6.8k views

1 comment

edited by

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
3

5 Answers

22 votes
22 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

selected by
by

4 Comments

i got it , huhhhhh!  this is the correct answer of correct question
0
0

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
0
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
1
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
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

edited by
1 vote
1 vote

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