Cheap and Secure Web Hosting Provider : See Now

[Solved]: IF A is reduced to B and B belongs to NPC then where does A belongs to?

, , No Comments
Problem Detail: 

i came across a question with no proper explnation. IF A is reduced to B and B belongs to NPC then we cant say anything about A since it can be as harder a NPH and as easier as P. i know why it is as harder as NHP but i am not able to figure out about P class.

according to me if A > B(A polynomial time reducible to B) and B belongs to NPH then A is as easier as NPC and as harder as NPH. A cannot belong to P since if A belongs to P then then in polynomial time i can solve P and in additional polynomial time i can reduce the results of A to suffice results of B.but as given B belongs to NPH and thus no polynomial time algorithm exists to solve B. which is contradiction to the assumption of A belongs to P. can someone explain what mistake am i making?

Asked By : Vivek Barsopia

Answered By : Mithlesh Upadhyay

If A reduce to B and B belongs to NPC, then surely A is in NP, but may or may not be NPC. A belongs to P is another question. If there given P = NP, then A would be belongs in P also.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52141

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback