1
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

Your Answer

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

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