How to prove that $$ C_1(f) = \min\{k : f \text{ is a $k$-DNF}\} $$ and $$ C_0(f) = \min \{ k: f \text{ is a $k$-CNF}\} $$ fulfill $$ C_1(f) = \max\{C(f,x):f(x)=1\}， \qquad C_0(f)=\max\{C(f,x):f(x)=0\} $$ where $C$ is the certificate complexity of a function $f\colon \{0,1\}^n \to \{0,1\}$.
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
