If A is not NP-hard, but not NP-complete, then prove that A in not in P.
A is NP-hard if there is an NP-complete problem B such that B is reducible to A in polynomial time. A is NP-complete if A is in NP and all NP problems are reducible to A in polynomial time. But A is not NP-complete, so one one or both of those conditions must be false. If A is not in NP, then A is not in P. The other case is that there exists at least one NP problem that is not reducible to A in polynomial time. This is where I am stuck. How do I get from knowing that there is an NP-complete problem that is reducible and an NP problem that is not reducible to A is not in P?
If a problem A is NP-hard, then all NP problems are reducible to A in polynomial time.
Proof: Since the problem A is not NP-Complete, then there exists problem B as defined above. All problems C in NP can be reduced to B in polynomial time, then B can be reduced to A in polynomial time. Composition of polynomial time algorithms is polynomial, so C can be reduced to A in polynomial time.
--
Since A is NP-Hard but not NP-Complete, A must not be in NP, therefore A is not in P either.