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?

  • 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

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.