#StackBounty: #algorithms #complexity-theory #graphs #formal-languages #time-complexity First circuit size lower bound ever

Bounty: 250

Let $F$ be the set of all Boolean formulae.

Let $n>1$ and a formula $varphi:{0,1}^nto{0,1}$ that satisfies:

  • Positivity (=monotonicity):

$forall alphain F,ileq n$, if $alphawedgeneg x_imodelsvarphi$, then $alphamodelsvarphi$

  • Almost Linearity:

If $forall alpha,beta,gamma,deltain F.
alphawedgegammamodelsvarphi \
alphawedgedeltamodelsvarphi \

Then, $begin{cases}
exists beta’in F. (alphawedgegamma)vee (alphawedgedelta)modelsbeta’wedgegammamodelsbetawedgegamma \
exists delta’in F. (alphawedgegamma)vee(betawedgegamma)modelsalphawedgedelta’modelsalphawedgedeltaend{cases}$

Where the notation $xmodels ymodels z$ above means $xmodels y$ and $y models z$.

Intuitively, that means that $varphi$ could not be succinctly written as disjunction of conjunctions of the form $(alphaveebeta)wedge(gammawedgedelta)$.


Denoting by $||varphi||$ the number of conjunctions (=clauses) in the $varphi$‘s minimal DNF form (notice that since $varphi$ is positive, so its minimal DNF form is unique up to permutations).

Denoting by $|varphi|$ the number of logical gates (=connectives) in the minimal Boolean circuit $C$ representing $varphi$ over the connectives ${vee,wedge,neg}$.


I am looking for a lower bound on $|varphi|$ as a function of $||varphi||$ and $n$.

I conjecture that $|varphi|geq {||varphi||}^{1/log n}$, but is that true?
Could we say any better?

Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.