Hard 3-CNF-SAT problems are in $P$ -- A first step in proving $NP=P$

Abstract

The relationship between the complexity classes $P$ and $NP$ is an unsolved question in the field of theoretical computer science. In the first part of this paper, a lattice framework is proposed to handle the 3-CNF-SAT problems, known to be in $NP$. In the second section, we define a multi-linear descriptor function ${\mathcal{H}}_{\phi }$ for any 3-CNF-SAT problem $\phi$ of size $n$, in the sense that ${\mathcal{H}}_{\phi }:\{0,1{\}}^n\to \{0,1{\}}^n$ is such that $Im{\mathcal{H}}_{\phi }$ is the set of all the solutions of $\phi$. A new merge operation ${\mathcal{H}}_{\phi }\bigwedge {\mathcal{H}}_{\psi }$ is defined, where $\psi$ is a single 3-CNF clause. Given ${\mathcal{H}}_{\phi }$ [but this can be of exponential complexity], the complexity needed for the computation of $Im{\mathcal{H}}_{\phi }$, the set of all solutions, is shown to be polynomial for hard 3-CNF-SAT problems, i.e. the one with few ($\le 2^k$) or no solutions. The third part uses the relation between ${\mathcal{H}}_{\phi }$ and the indicator function $1_{{\mathcal{S}}_{\phi }}$ for the set of solutions, to develop a greedy polynomial algorithm to solve hard 3-CNF-SAT problems.

First draft, comments and suggestion are welcome