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.

  • $\begingroup$ Note that $\bar{A} <_L^m A$ if and only if $A <_L^m \bar{A}$ $\endgroup$ Commented Oct 9, 2013 at 14:32

1 Answer 1


The circuit value problem: input is a Boolean formula and a truth assignment to its variables; accept if, and only if, the input is well-formed and the formula evaluates to true under the given assignment. The complement is to accept iff the input is malformed or the formula is false.

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.

  • $\begingroup$ isn't this a Turing reduction? I am looking for many-to-one reduction because P and NP are closed under this reduction. $\endgroup$ Commented Oct 10, 2013 at 0:02
  • $\begingroup$ No, it's many-one: given an instance to CVP, we compute an instance that's in coCVP iff the original was in CVP. $\endgroup$ Commented Oct 10, 2013 at 7:51
  • $\begingroup$ Can you explain why finding the negation of a formula can be done in Logspace? $\endgroup$ Commented Oct 10, 2013 at 16:23
  • $\begingroup$ Because it just involves putting a $\neg$ symbol at the start of it! $\endgroup$ Commented Oct 10, 2013 at 16:25
  • $\begingroup$ I've given a logspace reduction between a P-complete problem (CVP) and its complement. All the logspace function has to do is determine whether a string is a syntactically correct Boolean formula: it doesn't have to solve CVP. $\endgroup$ Commented Oct 10, 2013 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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