Showing that HALF-2-SAT is in P
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 \, &amp;\text{$\varphi$ is a 3-CNF formula and there exists an assignment} \\
&amp; \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 \, &amp;\text{$\varphi$ is a 2-CNF formula and $f$ is an assignment} \\
&amp; \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$.