By the MAXSAT problem, we are given a set $V$ of $m$ variables and a collection $C$ of $n$ clauses over $V$. We will seek a truth assignment to maximize the number of satisfied clauses. This problem is $\textit{NP}$-hard even for its restricted version, the 2-MAXSAT problem by which every clause contains at most 2 literals. In this paper, we discuss a polynomial time algorithm to solve this problem. Its time complexity is bounded by O($n^2m^3$). Hence, we provide a proof of $P$ = $\textit{NP}$.
翻译：通过MAXSAT问题，我们给出一个包含$m$个变量的集合$V$和一个包含$n$个从属于$V$的子句$C$的集合。我们将寻找一个真值分配使得满足的子句数最大化。即便是限制了每个子句的字面量不能超过2个的2-MAXSAT问题，它也是NP难问题。在本文中，我们讨论了一个多项式时间算法来解决此问题，其时间复杂度被O($n^2m^3$)所限制，从而我们提供了一个$P$=$NP$的证明。
相关内容
Arxiv
0+阅读 · 2023年6月13日
相关VIP内容
相关资讯
相关论文
Arxiv
0+阅读 · 2023年6月13日
微信扫码咨询专知VIP会员