# #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. begin{cases} alphawedgegammamodelsvarphi \ alphawedgedeltamodelsvarphi \ betawedgegammamodelsvarphi end{cases}$$

Then, $$begin{cases} exists beta’in F. (alphawedgegamma)vee (alphawedgedelta)modelsbeta’wedgegammamodelsbetawedgegamma \ text{or}\ 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!!!

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