1
$\begingroup$

My intuition is that it is not generally possible, but I cannot think of a proof.

$\endgroup$
2
$\begingroup$

In "Renaming a Set of Clauses as a Horn Set" Harry Lewis showed that a CNF formula could be converted to Horn form iff a particular 2-CNF formula constructed from the original formula is satisfiable. The satisfying assignment to the 2-CNF formula tells you which literals to flip. The 2-CNF formula can be constructed in time quadratic to the number of literals appearing in the original formula. Faster algorithms have been published since which reduce the problem of Horn-renaming a CNF formula to linear-time if it is possible to do at all.

$\endgroup$
1
  • $\begingroup$ Interesting. So anyway it seems that the answer to the larger question is NO. $\endgroup$
    – apen
    Nov 5 '20 at 22:51

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.