4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ "Is there an official way to ..." - no, there is no central authority. Any algorithm that you prove correct is acceptable. $\endgroup$ – Juho May 10 at 9:52
  • $\begingroup$ I meant to do so in poly-time... $\endgroup$ – xYaelx May 10 at 13:04
  • $\begingroup$ The decider for $\text{2-SAT}$ is unlikely to be useful for deciding $\text{HALF-2-SAT}$. $\endgroup$ – Apass.Jack May 10 at 15:17
6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Not sure I understood your proof. Take the formula (a OR b) AND (not b OR not c). Neither f0 nor f1 as you suggested satisfy it $\endgroup$ – xYaelx May 10 at 15:45
  • $\begingroup$ @xYaelx I agreed and agree that neither f0 nor f1 satisfies (a OR b) AND (not b OR not c). However, what is an assignment that satisfies at least half of the clauses? Can you explain the meaning of "half"? It looks look you are confusing $\text{HALF-2-SAT}$ with $\text{2-SAT}$. Both f0 and f1 satisfy half of the clauses in (a OR b) AND (not b OR not c). $\endgroup$ – Apass.Jack May 10 at 15:55
  • $\begingroup$ @xYaelx Please check the definition of CNF and clause. "In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals." $\endgroup$ – Apass.Jack May 10 at 15:57
  • $\begingroup$ oh, you're right. In addition, your algorithm just accept if I understood it, right? $\endgroup$ – xYaelx May 10 at 15:58
  • 1
    $\begingroup$ Exactly, the simplest algorithm of all (not counting the validation of the input). $\endgroup$ – Apass.Jack May 10 at 15:58
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thanks. but how come there's a probability of 3/4 that the whole clause is satisfied? each clause has a probability of 1/4 to be satisfied so if there are m clauses isn't it a chance of (0,25)^m that the whole clause will be satisfied? $\endgroup$ – xYaelx May 10 at 10:46
  • $\begingroup$ One clause has the form of $l_i\lor l_j$ where $l_i,l_j$ are variables or the negation of variables. The clause is not satisfied iff both $l_i,l_j$ evaluate to false, which happens with probability $1/4$. Note that different clauses are not independent, so I can't go on to say that the probability that $m$ clauses are not satisfied is $\frac{1}{4}^m$, but I don't need independence since I'm only using linearity of expectation. $\endgroup$ – Ariel May 10 at 10:52
  • $\begingroup$ Why do you bet on random expectations ? You can just greedily assign the variables to satisfy the most remaining clauses. $\endgroup$ – Vince May 10 at 11:51
  • $\begingroup$ You're right. I got confused s.t. there's a 0.25 chance that the clause ISN'T satisfied. However, is it enough to claim that there is 0.75 that the formula is satisfied and hence it's in P? $\endgroup$ – xYaelx May 10 at 13:00
  • $\begingroup$ @Vince this is exactly what I assumed but bc there is a dependencies between the clauses, I didn't know how to do it in polynomial time $\endgroup$ – xYaelx May 10 at 13:03
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.