search
Log In
12 votes
3.6k 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)?

in Theory of Computation
recategorized by
3.6k views
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. 

5 Answers

19 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
1
Sir, why not option C?
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?
3
yes, and that is the "a polynomial time algorithm" from the beginning.
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.
4

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

0
i got it , huhhhhh!  this is the correct answer of correct question
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$

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

Answer is option C. 

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

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


edited by
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

Answer:

Related questions

9 votes
3 answers
1
2k views
Consider the decision problem $2CNFSAT$ defined as follows: $\left\{ \phi \mid \phi \text{ is a satisfiable propositional formula in CNF with at most two literals per clause}\right\}$ ... polynomial time by reduction to directed graph reachability. solvable in constant time since any input instance is satisfiable. NP-hard but not NP-complete.
asked Sep 28, 2014 in Theory of Computation jothee 2k views
8 votes
2 answers
2
2.8k views
For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE? If X can be solved in polynomial time, then so can Y X is NP-complete X is NP-hard X is in NP, but not necessarily NP-complete
asked Oct 28, 2014 in Algorithms Ishrat Jahan 2.8k views
8 votes
4 answers
3
6.4k views
Consider a token ring network with a length of 2 km having 10 stations including a monitoring station. The propagation speed of the signal is $2 \times10^8m/s$ and the token transmission time is ignored. If each station is allowed to hold the token for $2 µsec$, the minimum time for which the monitoring station should wait (in $µsec$) before assuming that the token is lost is _______.
asked Sep 26, 2014 in Computer Networks jothee 6.4k views
14 votes
2 answers
4
3k views
Consider two decision problems $Q_1, Q_2$ such that $Q_1$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_2$. Then which one of the following is consistent with the above statement? $Q_1$ is in NP, $Q_2$ is NP hard. $Q_2$ is in NP, $Q_1$ is NP hard. Both $Q_1$ and $Q_2$ are in NP. Both $Q_1$ and $Q_2$ are in NP hard.
asked Feb 12, 2015 in Theory of Computation jothee 3k views
...