Is it generally possible to convert CNF to Horn clauses?
In &quot;Renaming a Set of Clauses as a Horn Set&quot; 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.