Take the 2-minute tour ×
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.

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\}$.

share|improve this question
(plus: thx @martini) –  meshuai Nov 20 '12 at 12:47
Duplicate of math.stackexchange.com/questions/241229/… –  Joel Reyes Noche Nov 20 '12 at 12:48
I see that you deleted your earlier question, as well as the comments made by others. Some will consider this rude. In the future, please refrain from deleting your question and reposting it again. Editing it is fine. –  Joel Reyes Noche Nov 20 '12 at 12:51
@Joel Reyes Noche thx –  meshuai Nov 20 '12 at 12:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.