1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ I think you're confused about the direction of the reduction. If you reduce A to B, then A < B, not the other way around. The reason is that if you reduce A to B, you can use any algorithm deciding B to also decide A by first applying the reduction, then the decider for B. However, the decider for B might be far more powerful than is necessary to decide A. An example: if you have a regular language $L$ and want to decide whether a word $w \in L$, then you can build a SAT instance that is satisfiable iff $w \in L$. But: regular languages are super simple, SAT is not (known to be). $\endgroup$ – G. Bach Jan 22 '16 at 13:08
  • 1
    $\begingroup$ Another example: you can reduce shortest path problems to integer linear programming, but we have Floyd-Warshall to tell us that shortest paths is easy, and we know integer linear programming is NP-hard. $\endgroup$ – G. Bach Jan 22 '16 at 13:12
  • 1
    $\begingroup$ Welcome to Computer Science! Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Jan 22 '16 at 13:20
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

As G. Bach explained the reduction is just to show the upper bound. If A reduces to B then A can not be harder then B. For example if we had a Hamiltonian cycle and set it up in such a way that if we start from a certain node and follow the cycle we will be able to also sort a group of numbers. then that would mean that sorting can't be harder then finding a Hamiltonian cycle and in fact we can solve it in $O(N\log N)$ but that isn't the point here. we have shown a sorting problem can be reduced to a Hamiltonian cycle and that would mean if we converted a sorting problem to this Hamiltonian cycle we can use a Hamiltonian cycle algorithm to solve it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.