My intuition is that it is not generally possible, but I cannot think of a proof.
1 Answer
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.
-
$\begingroup$ Interesting. So anyway it seems that the answer to the larger question is NO. $\endgroup$– apenNov 5, 2020 at 22:51