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.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

+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.

+13 votes

Best answer

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

+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

hence option D is correct

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 447
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,939 questions

45,453 answers

131,195 comments

48,209 users