6
$\begingroup$

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.

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

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.

$\endgroup$
  • $\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$ – Mohammad Al-Turkistany Oct 10 '13 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$ – David Richerby Oct 10 '13 at 7:51
  • $\begingroup$ Can you explain why finding the negation of a formula can be done in Logspace? $\endgroup$ – Mohammad Al-Turkistany Oct 10 '13 at 16:23
  • $\begingroup$ Because it just involves putting a $\neg$ symbol at the start of it! $\endgroup$ – David Richerby Oct 10 '13 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$ – David Richerby Oct 10 '13 at 16:36

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.