#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.
alphawedgegammavdashvarphi \
alphawedgedeltavdashvarphi \
(alphawedgegamma)vee (alphawedgedelta)modelsbetawedgegamma \

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!!!

Leave a Reply

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