论文标题
硬3-CNF-SAT问题是$ P $ - 证明$ NP = P $的第一步
Hard 3-CNF-SAT problems are in $P$ -- A first step in proving $NP=P$
论文作者
论文摘要
复杂性类别$ p $和$ np $之间的关系是理论计算机科学领域未解决的问题。在本文的第一部分中，提出了一个格子框架来处理3-CNF-SAT问题，已知为$ NP $。在第二部分中，我们为任何3-CNF-SAT问题$ {\ cal H} _或{\ cal H} _或{\ cal H}_φ$是$φ$的所有解决方案的集合。定义了一个新的合并操作$ {\ cal H}_φ\ bigWedge {\ cal H}_ψ$，其中$ψ$是一个单个3-CNF子句。给定$ {\ cal h}_φ$ [但这可以是指数复杂性]，计算$ im \的复杂性; {\ cal H}_φ$，所有解决方案的集合，对于硬3-CNF-SAT问题而言是多项式的，即很少的（$ \ leq 2^k $）或没有解决方案。第三部分使用$ {\ cal H}_φ$与指示器函数$ \ mathbb {1} _ {{{\ cal s}_φ} $用于一组解决方案，以开发一种贪婪的多项式算法来解决解决硬性3-CNF-cnf-sat问题。
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 ${\cal H}_φ$ for any 3-CNF-SAT problem $φ$ of size $n$, in the sense that ${\cal H}_φ: \{0,1\}^n \rightarrow \{0,1\}^n$ is such that $Im \; {\cal H}_φ$ is the set of all the solutions of $φ$. A new merge operation ${\cal H}_φ\bigwedge {\cal H}_ψ$ is defined, where $ψ$ is a single 3-CNF clause. Given ${\cal H}_φ$ [but this can be of exponential complexity], the complexity needed for the computation of $Im \; {\cal H}_φ$, the set of all solutions, is shown to be polynomial for hard 3-CNF-SAT problems, i.e. the one with few ($\leq 2^k$) or no solutions. The third part uses the relation between ${\cal H}_φ$ and the indicator function $\mathbb{1}_{{\cal S}_φ}$ for the set of solutions, to develop a greedy polynomial algorithm to solve hard 3-CNF-SAT problems.
