# Proof of P-Hardness by reduction

I want to proof the P-Hardness of a language. Why is it enough to make a reduction-proof from an other, already P-Complete known language?

• Check the definitions of both notions; our reference questions should be of use. (Note that the question is the same if you write NP instead of P everywhere.) – Raphael Sep 26 '14 at 19:07

By definition, a language $L$ is P-complete if for every language $M \in P$ there is a logspace reduction $f_M$ such that $x \in M$ iff $f_M(x) \in L$. Now suppose that $L$ is P-complete and that for some language $L' \in P$ there exists a logspace reduction $g$ such that $x \in L$ iff $g(x) \in L'$. Then for every language $M \in P$, $x \in M$ iff $g(f_M(x)) \in L'$, and so $L'$ is P-hard since the composition of logspace reductions is a logspace reduction.