# What could we say about that conjecture that yields P != NP?

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

We say that a Boolean formula $$\varphi$$ is positive (=monotone) if $$\forall \alpha\in F,i\leq n$$, if $$\alpha\wedge\neg x_i\models\varphi$$, then $$\alpha\models\varphi$$.

Let $$\psi,\xi\in F$$. We say that $$\psi\vdash \xi$$ if $$\psi\models \xi$$ and $$\psi$$ is equivalent to a formula $$\psi'$$ over the connective $$\wedge$$ only (for example, $$\psi'$$ could be $$x_1\wedge x_2$$ but not $$x_1\vee x_3$$). This is, of course, different from the usual meaning of this notation.

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

• Positivity

• Almost Linearity
That is:

$$\forall \alpha,\beta,\gamma,\delta\in F. \begin{cases} \alpha\wedge\gamma\vdash\varphi \\ \alpha\wedge\delta\vdash\varphi \\ \beta\wedge\gamma\vdash\varphi \end{cases} \Rightarrow \begin{cases} (\alpha\wedge\gamma)\vee (\alpha\wedge\delta)\models\beta\wedge\gamma \\ \ \ \ \ \ \text{or}\\ (\alpha\wedge\gamma)\vee(\beta\wedge\gamma)\models\alpha\wedge\delta\end{cases}$$.

Intuitively, that means that $$\varphi$$ could not be succinctly written as $$\bigvee_i{(\alpha_i\vee\beta_i)\wedge(\gamma_i\vee\delta_i)}$$.

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

Let us denote $$||\varphi||=\#\{\xi\in F|\xi\vdash\varphi\}$$, where here $$\#$$ stands for set cardinality.

Let us denote by $$|\varphi|$$ the number of logical gates (=connectives) in the minimal Boolean circuit $$C$$ representing $$\varphi$$ over the connectives $$\{\vee,\wedge,\neg\}$$. This is, of course, the usual definition of minimal circuit size.

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

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 $$\xi\in F$$ such that $$\xi\vdash HC$$, so $$\xi$$ represents exactly one half clique. We denote $$V(\xi)$$ = the set of vertices that the edges in $$\xi$$ touch. For example, if $$\xi=E_{12}\wedge E_{25}\wedge E_{15}$$ then $$V(\xi)=\{1,2,5\}$$. So clearly if $$x\wedge y\vdash 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 $$HCP\notin PSize$$. Since $$HCP\in NP$$, we get $$NP\ne PSize$$, which is known to imply $$P\ne NP$$.