<p>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.</p>

<p>consider the problem of <em>monotone</em> k-CNF ←→ k-DNF conversion by minimizing errors where $k$ is the <em>maximum</em> 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. </p>

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

<p>there is a dual version k-DNF → k-CNF approximation in the opposite direction that has mirrored theory.</p>

<blockquote>
  <ol>
  <li>how does one determine the optimal $g(x)$ given $f(x)$?</li>
  <li>which "types" of functions $f(x)$ are harder or easier to approximate in the
  sense of errors (high vs low errors, respectively)?</li>
  </ol>
</blockquote>

<p>(note: suspect there may be some transition-point-like behavior associated with the problem.)</p>

CC BY-SA 3.0
2013-04-12T16:40:30.017Z
If you don't mind introducing new variables then DNF->CNF is easy: http://en.wikipedia.org/wiki/Tseitin-Transformation
Huck Bennett
CC BY-SA 3.0
2013-04-12T16:59:02.300Z
@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.
vzn
<cc.complexity-theory><reference-request><circuit-complexity><approximation><boolean-formulas>
k-CNF ←→ k-DNF conversion to minimize errors
vzn
# k-CNF ←→ k-DNF conversion to minimize errors

(Asked by: username_0 on 2013-04-12)

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

**Tags:** cc.complexity-theory, reference-request, circuit-complexity, approximation, boolean-formulas

> **Comments:**
> **username_1**: If you don't mind introducing new variables then DNF->CNF is easy: http://en.wikipedia.org/wiki/Tseitin-Transformation  
> **username_0**: @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.  

---

## 0 answers

