I've been taking a look at the following question and came up with some answers but I'm wondering if there's more to it.
The Question is as follows:
Assume that there are proofs for the following four statments. Can you infer anything about A, B, C, and D? Explain your answer.
a) X is a polynomially solvable problem and A is polynomial reducible to X.
b) X is an NP-Hard problem and B is polynomially reducible to X.
c) X is a polynomially solvable problem and X is polynomially reducible to C.
d) X is an NP-Hard problem and X is polynomially reducible to D.
My Answers:
a) We can infer that since X is at least as hard as A and is polynomially solvable then A is polynomially solvable.
b) We can only infer that B is at most as hard as an NP-Hard problem.
c) We can infer that C is polynomially solvable as well. this is because if c was not polynomially solvable then X would not be either and would contradict the given proof.
d) We can infer that D is at least as hard as an NP-Hard problem (making it be in NP-Hard space). If we knew that it was in NP then we could say that it's also NP-Complete but we do not know.