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?
$\begingroup$
$\endgroup$
-
2$\begingroup$ 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.) $\endgroup$ – Raphael♦ Sep 26 '14 at 19:07
$\begingroup$
$\endgroup$
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.
Generalizing, this sort of argument always works as long as the composition of two legal reductions is a legal reduction. This is the case for both polynomial time reductions and logspace reductions.
answered Sep 26 '14 at 19:20
