Showing that HALF-2-SAT is in P

Question

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?

Answer 1

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$.

Answer 2

Your language consists of all valid encodings of a 2-CNF formula. Consider a random assignment to the variables of $\varphi$, i.e. each variable is assigned True/False with probability $\frac{1}{2}$, then the expected portion of satisfied clauses is $\frac{3}{4}$ (use linearity of expectation and note that each clause is not satisfied with probability $\frac{1}{4}$) , which means that there exists an assignment which satisfies at least $\frac{3}{4}$ of the clauses.

The above observation yields a simple deterministic algorithm for finding such an assignment. Let $S_{\varphi}$ denote the random variable counting the number of satisfied clauses relative to a random assignment.

Note that for any variable $x_i$ we have: $\mathbb{E}\big[S_\varphi\big]= \frac{1}{2}\mathbb{E}\big[S_\varphi\big| x_i = 1 \big]+ \frac{1}{2}\mathbb{E}\big[S_\varphi\big| x_i = 0 \big]$.

Now, you can simply pick the assignment $b\in\{0,1\}$ to $x_i$ which maximizes $\mathbb{E}\big[S_\varphi | x_i = b\big]$ (you can compute the expectation in linear time). To see why, suppose that $\mathbb{E}\big[S_\varphi| x_i = 1 \big] \ge \mathbb{E}\big[S_\varphi| x_i = 0 \big]$, then since $\mathbb{E}[S_\varphi]=\frac{3}{4}m$, it must hold that $\mathbb{E}\big[S_\varphi| x_i = 1 \big]\ge\frac{3}{4}m$, which means that there exists an assignment for the variables of $\varphi$ which assigns $1$ to $x_i$ and satisfies $\ge\frac{3}{4}m$ clauses.

Answer 3

Complementing the statement in the post, let us consider the following generalization of HALF-2SAT: for a constant $c$, the language $c$-2SAT consists of all 2SAT instances on $m$ clauses such that some assignment satisfies at least $cm$ clauses. HALF-2SAT is the special case $c = 1/2$.

We have seen above that when $c \leq 1/2$, the answer is always YES. When $c = 1$, this is just 2SAT, which can be solved in polynomial time. Complementing these results, let us show that if $1/2 < c < 1$, the language $c$-2SAT is NP-complete.

Our starting point is the PCP theorem, which states that there is a function $f$ mapping 3SAT instances to 3SAT instances such that:

• If $\phi$ is satisfiable then $f(\phi)$ is satisfiable.
• If $\phi$ is unsatisfiable then at most a $1-\epsilon$ fraction of the clauses of $f(\phi)$ can be simultaneously satisfied.

We compose this with a simple reduction of Garey, Johnson and Stockmeyer, which converts a 3SAT instance $\psi$ to a 2SAT instance $g(\psi)$ by mapping each original clause to 10 new clauses such that:

• For every assignment satisfying an original clause, 7 of the 10 new clauses can be satisfied.
• For every assignment not satisfying an original clause, at most 6 of the 10 new clauses can be satisfied.

Composing the two reductions, we obtain:

• If $\phi$ is satisfiable then a $0.7$ fraction of the clauses of $g(f(\phi))$ can be satisfied.
• If $\phi$ is unsatisfiable then at most a $0.7(1-\epsilon) + 0.6\epsilon = 0.7 - 0.1\epsilon$ fraction of the clauses of $g(f(\phi))$ can be satisfied.

This shows that $0.7$-2SAT is NP-hard. The astute reader will notice that the PCP theorem is not needed for this step – we could just use a direct reduction from 3SAT.

In order to boost this to arbitrary $c$, we either add lots of pairs of clauses of the form $x, \lnot x$ to push $c$ down, or add lots of clauses of the form $x$ to push $c$ up. This is where we use the gap provided by the PCP theorem, for technical reasons.

Let us start with the second case. Suppose that $g(f(\phi))$ contains $m$ clauses. For integers $a,b$, we duplicate $a$ times the formula $g(f(\phi))$, and add $b m$ clauses of the form $x$, where $x$ is a new variable. If $\phi$ is satisfiable, then in the new formula we can satisfy a fraction of $\frac{0.7 a + b}{a+b}$ of the clauses, whereas if $\phi$ is unsatisfiable, we can satisfy at most a fraction of $\frac{(0.7 - 0.1\epsilon)a + b}{a+b}$. We choose $a,b$ so that $$ \frac{(0.7 - 0.1\epsilon)a + b}{a+b} < c \le \frac{0.7a + b}{a+b}. $$ To do this, suppose that $c = 0.7 + \delta$. Take $a$ to be large and $b = \lfloor \delta a \rfloor$. The right-hand side tends (as $a\to\infty$) to $c$ (from below) and the left-hand side tends to $0.7-0.1\epsilon+\delta$, so for large enough $a$ the inequality above will be satisfied.

When $c < 0.7$, in addition to adding $bm$ clauses of the form $x$, we also add $bm$ clauses of the form $\lnot x$. Instead of $\frac{0.7a+b}{a+b}$ we now get $\frac{0.7a+b}{a+2b}$; we let the reader complete the proof from here.