the following problem/question seems fundamental/hard. it appears in some circuit theory proofs, graph theory, and maybe elsewhere. looking for any nontrivial insight. will add various known/nearby diverse refs if there is sufficient interest.consider the problem of monotone k-CNF  k-DNF conversion by minimizing errors where $k$ is the maximum width of clauses (number of variables in the clause). let $f(x)$ be a k-CNF formula where $x$ is a bitvector (denoting the boolean values of all the variables). there exists a k-DNF approximation formula $g(x)$ that approximates $f(x)$ by minimizing total errors under the following metric. evaluate $f(x)$ and $g(x)$ on every $x$. if $g(x)=1$ while $f(x)=0$ then count one false positive. if $g(x)=0$ while $f(x)=1$ then count one false negative. the total errors are the sum of false positives and false negatives. another way of looking at this natural error metric is that its the Hamming distance between the two bitvectors of size $2^n, n=|x|$ composed of all corresponding values of $f(x)$ and $g(x)$ (eg function value column for both functions evaluated on the same truth table).there is a dual version k-DNF  k-CNF approximation in the opposite direction that has mirrored theory.how does one determine the optimal $g(x)$ given $f(x)$?which types of functions $f(x)$ are harder or easier to approximate in the  sense of errors (high vs low errors, respectively)?(note: suspect there may be some transition-point-like behavior associated with the problem.)
k-CNF  k-DNF conversion to minimize errors
cc.complexity theory;reference request;circuit complexity;approximation;boolean formulas