Showing that HALF-2-SAT is in P

I need to show that the following problem is in P:
$$\begin{align*}\text{HALF-2-SAT} = \{ \langle \varphi \rangle \mid \, &\text{$\varphi$ is a 2-CNF formula and there exists an assignment} \\
& \text{that satisfies at least half of the clauses} \}\end{align*}$$

I know that 2-SAT is in P, hence it got a decider and I wanted to use it for HALF-2-SAT but got stuck to find how to extract the right half of the clauses that will be satisfied in a polynomial way.

Is there an official way to choose half of the clauses that satisfy the formula?

Is there an official way to choose half of the clauses that satisfy the formula?

There is no official way. As noted by Juho, "any algorithm that you prove correct is acceptable". Moreover, you do not have to choose that half of the clauses explicitly.

Here is the simplest algorithm to decide $\text{HALF-2-SAT}$ that runs in polynomial time. In fact, it runs in constant time. (If the algorithm should verify the given input is valid, it runs in linear time.)

• Input: $\varphi$ and $m$, where $\varphi$ is a 2-CNF formula with $m$ clauses.

• Output: True if there is an assignment of the variables such that at least $m/2$ clauses become 1.

• Procedure: Return true.

Why does the above algorithm work? Here is the reason.

Lemma. Let $\varphi$ be a 2-CNF formula. Then there exists an assignment that satisfies at least half of the clauses in $\varphi$.

Proof. Let $f_0$ assign 0 to all variables. Let $f_1$ assign 1 to all variables. Let $c$ be any one of the clauses in $\varphi$. Suppose variable $x$ appears in $c$.

• the literal $x$ is in $c$. Then $c$ becomes 1 under $f_1$.

• the literal $\neg{x}$ is in $c$. Then $c$ becomes 1 under $f_0$.

So every clause becomes 1 under $f_1$ or $f_0$. So the number of clauses is not greater than the sum of the number of clauses that becomes 1 under $f_1$ and the number of clauses that becomes 1 under $f_0$. Hence, at least half of the clauses in $\varphi$ are satisfied under $f_1$ or $f_0$. QED.

Here are several exercises.

Exercises 1. Show the following language is in P:
$$\begin{align*}\text{3-SAT}_{\ge\frac12} = \{ \langle \varphi \rangle \mid \, &\text{$\varphi$ is a 3-CNF formula and there exists an assignment} \\
& \text{that satisfies at least half of the clauses} \}\end{align*}$$

Exercises 2. Show that the following problem is in P:
$$\begin{align*}\text{2-SAT}_{\le\frac34} = \{ \langle \varphi, f \rangle \mid \, &\text{$\varphi$ is a 2-CNF formula and $f$ is an assignment} \\
& \text{that satisfies at most three fourth of the clauses} \}\end{align*}$$

Exercises 3. Let $\varphi$ be a 2-CNF formula such that none of its clause involves only one variable. Then there exists an assignment that satisfies at least three fourth of the clauses in $\varphi$.

StackExchange Computer Science Q#109177, answer score: 6