The 2-MAXSAT Problem Can Be Solved in Polynomial Time

By the MAXSAT problem, we are given a set
$V$
of
$m$
variables and a collection
$C$
of
$C$
clauses over
$V$
. We will seek a truth assignment to maximize the number of satisfied clauses. This problem is 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
$\mathrm{O}(n^{2}m^{3})$
. Hence, we provide a proof of
$P=NP$
.