# #StackBounty: #algorithms #complexity-theory #graphs #np-complete #circuits What could we say about that conjecture that yields P != NP?

### Bounty: 250

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

Let $$x,yin F$$. We say that $$xvdash y$$ if $$xmodels y$$ and $$forall x’in F.begin{cases}x’models x\ x’notequiv xend{cases}Rightarrow x’notmodels y$$. This is, of course, different from the usual meaning of this notation.

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:

$$forall alpha,beta,gamma,deltain F. begin{cases} alphawedgegammavdashvarphi \ alphawedgedeltavdashvarphi \ betawedgegammavdashvarphi end{cases} Rightarrow begin{cases} (alphawedgegamma)vee (alphawedgedelta)modelsbetawedgegamma \ text{or}\ (alphawedgegamma)vee(betawedgegamma)modelsalphawedgedeltaend{cases}$$.

Intuitively, that means that $$varphi$$ could not be succinctly written as $$bigvee_i{(alpha_iveebeta_i)wedge(gamma_iveedelta_i)}$$.

============

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?

===========

The Half Clique problem (HCP) is: given a graph, does it contain a clique whose length is exactly half of the graph’s number of vertices?

HC is a formula that treats its variables as graph edges, and returns "true" iff the assignment to the variables represents a graph with half clique (as defined above).

Let $$xiin F$$ such that $$xivdash HC$$, so $$xi$$ represents exactly one half clique. We denote $$V(xi)$$ = the set of vertices that the edges in $$xi$$ touch. So clearly if $$xwedge yvdash HC$$, then either $$V(x)subseteq V(y)$$ or $$V(x)supseteq V(y)$$. Hence, either $$x$$ or $$y$$ uniquely defines the Half Clique. From this, the almost linearity trivially follows. Also, clearly HC is positive.

If the above conjecture is true, then we could apply it to $$HC$$ to get super polynomial lower bound on its size, so $$HCPnotin PSize$$. Since $$HCPin P$$, we get $$Pne PSize$$, which is known to imply $$Pne NP$$.

Get this bounty!!!

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