# $P$-complete problems and Logspace reductions

It is known that HORN-3SAT is complete for $P$ under Logspace many-one reductions ($<_L^m$).

This implies that $\bar{A} <_L^m A$ for any $P$-complete problem $A$, where $\bar{A}$ means the complement of $A$. This immediately follows from that fact that $P$ is closed under complement and the $P$-hardness of $A$.

My question is to find such Logspace many-one reduction $\bar{A} <_L^m A$ for any $P$-complete problem $A$ (such as HORN-3SAT). The reduction must show the mapping between short certificates of $A$ and $\bar{A}$.

EDIT: As David stated in his comment on the case of HORN-3SAT problem, we know that Logspace function exists but it seems that it is hard to find explicitly.

• Note that $\bar{A} <_L^m A$ if and only if $A <_L^m \bar{A}$ – Mohammad Al-Turkistany Oct 9 '13 at 14:32

The reduction is to check that the input is well-formed. If so, output the negation of the formula, with the same truth assignment; if not, output either $X; X=\mathrm{t}$ or $X; X=\mathrm{f}$, depending on which way you're going.
• Because it just involves putting a $\neg$ symbol at the start of it! – David Richerby Oct 10 '13 at 16:25