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.

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

2

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.

19 votes

Best answer

5

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.

2

"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

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.

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.

4

*P* is not a subset of *N**P**C*, and this is unconditionally true.

**Answer is C**

https://cs.stackexchange.com/questions/94201/if-p-np-why-is-p-a-subset-of-npc

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

0 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**.

0 votes

**P is not a subset of NPC, and this is unconditionally true.**

Reason: if P=NP, every NP-C problem is solvable in polynomial time, hence

**1. NPC is a subset of P**

For P = NPC, we need to prove that P is a subset of NP-C. In other words, an NP-C problem can be reduced to every deterministically polynomial time problem.

i.e A <= B, for all B belongs to P, and any A that belongs to NP-C

Proving the above statement would mean that every problem in P is at least as hard as every other problem in P (and NP, since P=NP). Then, by definition, every problem in P is an NPC problem.

Now say I pick A to be an NP-C problem namely the Hamiltonian Path problem, according to the question I have a way of solving this in deterministically polynomial time. So for a given graph, I solve the problem in polynomial time. For a "yes" output to the Hamiltonian path problem, I create a "yes" input to a P problem (for eg. an even input for the P problem "Is the input number even?") and for a "no" output to the Hamiltonian path problem, I create a "no" input to a problem P. A "yes" or "no" input here means an input which will always output "yes" or "no" respectively.

This effectively means that a reduction that reduces an NP complete problem to every other P problem exists, **except **for **only **two languages in P given below:

i) Language that accepts everything.

ii) Language that accepts nothing.

(i) has no "no" answer and (ii) has no "yes" answer so the reduction described above is not valid for these 2 cases.

This means,

**2. P- {Sigma*, Phi} is a subset of NPC
and therefore P=NPC cannot be followed from 1 and 2 as other answers suggest, the only conclusion is:
P-{Sigma*, Phi} = NPC
Answer is C**

https://cs.stackexchange.com/questions/94201/if-p-np-why-is-p-a-subset-of-npc