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.)
