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.

  1. how does one determine the optimal $g(x)$ given $f(x)$?
  2. 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.)

  • 1
    $\begingroup$ If you don't mind introducing new variables then DNF->CNF is easy: en.wikipedia.org/wiki/Tseitin-Transformation $\endgroup$ Commented Apr 12, 2013 at 16:40
  • 1
    $\begingroup$ @huck the tseitin transform is interesting/relevant in the area but its kind of the exact opposite of what is desired in that it adds many variables and this problem requires no change in the variables. the transform however does give a hint of the idea/design pattern of "equivalent constructions" which might be useful. $\endgroup$
    – vzn
    Commented Apr 12, 2013 at 16:59


Your Answer

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