Assume that . Then:
is is
is is
is -hard is -hard
A<B
means A is as hard as B
A & B can be either P,NP,NP-Complete or NP-Hard.
We knw P < NP but not NP-Complete < NP-Complete < NP-hard
So if A is reducible to B ... A<B
if A is NP-Hard then it means A is as hard as B. NP-hard is the maximum case of complexity. So if A itself is NP-hard then B has to be NP-Hard.
Same way we can explain the others also.
if B is P then A has to be P as nothing less than P is there. But if A is P then since A<B, B can be either P, NP NP-Complete or NP -Hard .
if B is NP then A can be P or NP . But P is a subset of NP. So there is nothing wrong saying A is NP.But if you take the other way round..if A is NP then B can be either NP-complete or NP-Hard.
Correct me if I am wrong.
-tho_mee
@aliceinwonderland: If i've understood, a problem -hard is a problem, which has not to be , such that every problem in can be reduced to it (it is as hard as every problem).
Maybe do you know problems called -complete. A problem is -complete if it is -hard to it and if it is .
(so -complete -hard, but not conversely)
Therefore we have: is -hard is -hard , like with -complete problems.
@tho_mee: Yep that's right. All that can be written using the polynomial reduction.
.
So, for instance, if is , checking a solution for the problem is the same that checking for .
is so the time used to check wether or not is in is polynomial, and is calculated in a polynomial time from , hence checking if is in is done in a polynomial time (the composition of polynomials is a polynomial).
(sorry for my english)