A Beautiful, Derandomized Algorithm

Abstract

Appreciating the simplicity of powerful randomized algorithms comes easy to me. In the following I will try to describe a naive algorithm relying on a randomized argument. What I find particularly remarkable is that it can easily parry the critique I am so often encountered with when cherishing randomized algorithms: it can trivially be turned deterministic.

MAX-3SAT

Is a boolean satisfiability problem. Given a formula in 3-CNF, the goal to satisfy as many clauses as possible.

3-CNF means that the formula \(\mathcal{F}\) consists of \(m\) conjuncted clauses using \(n\) literals. Each clause is a disjunction of exactly three literals. An example with \(m=4\) and \(n=5\):

\[\begin{aligned} \mathcal{F} &= C_1 \wedge C_2 \wedge C_3 \wedge C_4 \\ &= (l_1 \vee \neg l_2 \vee l_4) \wedge (l_2 \vee l_4 \vee \neg l_5) \wedge (\neg l_1 \vee \neg l_3 \vee l_5) \wedge (l_2 \vee l_3 \vee l_4) \end{aligned}\]

This problem is \(\mathcal{NP}\)-hard and we will look into an approximation algorithm.

At least how many clauses can be satisfied, by any algorithm?

In order to show that at least a lot of the clauses can be satisfied for every formula, we employ the probabilistic method.

Let’s define a randomized algorithm.

Each literal \(l_i\) is i.i.d. from the uniform distribution over \(\{True, False\}\). This turns every clause, and thereby the number of satisfied clauses \(M\) into a random variable.

We observe that a clause is satisfied if any of is components, being either a literal or a negated literal, is \(True\). Hence it is \(True\) in all cases but the one in which all of its components are \(False\).

\[\Pr[C_i] = 1 - \Pr[\text{all components are }False] = 1 - \frac{1}{2}^3 = \frac{7}{8}\]

We need no more but our dearest linearity of expectation to show that for every formula, we satisfy \(\frac{7}{8}\) of its clauses, in expectaion.

\[\begin{aligned} \mathbb{E}[M] &= \mathbb{E}[\sum_{i=1}^m C_i] \\ &= \sum_{i=1}^m \mathbb{E}[C_i] = \sum_{i=1}^m \Pr[C_i] \quad \text{(L.O.E.)} \\ &= \frac{7}{8}m \end{aligned}\]

The probabilistic method allows us to draw an interesting conclusion from this. We have shown that \(\frac{7}{8}\) of all clauses are satisfied in expectation for a given formula. As the expected value is a sum of non-negative values, we know that one of the realizations the expected value sums over has to take on the value of the expectation, i.e. \(\frac{7}{8}m\). Hence one of the possible assignments will lead to the satisfaction of at least \(\frac{7}{8}m\) clauses, for every formula.

I find that this by itself is an interesting, not necessarily intuitive result. It is a proof of existence.

The probabilistic method is often used for proofs of existence or/i.e. non-zero success probabilities of randomized algorithms. In this particular scenario we will also use its insight for the synthesis of a deterministic algorithm. The plan is to assign truth values to literals as to approximate the maximum assignment. This approach is sometimes referred to as derandomization via conditional expectation.

Construction of deterministic algorithm

The high-level idea of the algorithm is that we look at one literal after another, calculate the expected value conditioned on a possible assignment and then set this literal to the truth value that yields the highest expected value.

The algorithm relies on two key properties:

• We don’t decrease the (conditional) expectation of \(M\) by conditioning on the assignment that maximizes the conditional expectation.
• We can compute the conditional expectation ’efficiently'.

Increasing expectation

Our random assignment process used to compute the expected value tells us that: \[\mathbb{E}[M|l_1=\alpha_1, …, l_{i-1}=\alpha_{i-1}] = \\ \frac{1}{2} \mathbb{E}[M|l_1=\alpha_1, …, l_{i-1}=\alpha_{i-1}, l_i=0] + \frac{1}{2} \mathbb{E}[M|l_1=\alpha_1, …, l_{i-1}=\alpha_{i-1}, l_i=1]\]

\[ \Rightarrow max(\mathbb{E}[M|l_1=\alpha_1, …, l_{i-1}=\alpha_{i-1}, l_i=0], \mathbb{E}[M|l_1=\alpha_1, …, l_{i-1}=\alpha_{i-1}, l_i=1]) \\ \geq \mathbb{E}[M|l_1=\alpha_1, …, l_{i-1}=\alpha_{i-1}] \]

Therefore we know that iteratively setting literals to the truth value maximizing the conditional expectation will always give us \(\mathbb{E}[M]|l=\alpha] \geq \mathbb{E}[M] = \frac{7}{8}m\).

Cost of computing conditional expectation

Given assignments \(l_1 = \alpha_1, \dots, l_i = \alpha_i\), computing \(\mathbb{E}[M|l_1 = \alpha_1, \dots, l_i = \alpha_i]\) is actually pretty easy. We go clause by clause, each containing 3 literals and hence requiring \(\mathcal{O}(1)\) time. If all literals of a clause are determined, we check whether the clause is satisfied or not and accordingly count it as 0 or 1. If some of the literals are set, we add the probability of it being satisfied, e.g. \(\Pr[False \vee l_{i+1} \vee \neg l_{i+2}] = 1 - \frac{1}{4} = \frac{3}{4}\). All clauses that have no determined literals keep their expected satisfaction of \(\frac{7}{8}\). Hence computing one conditional expectation takes us \(\mathcal{O}(m\cdot 1)\) time.

Bringing it together

Aforementioned properties can now directly be turned into a deterministic greedy algorithm.

for i = 1 to n:
  M_0 = E[M|l_1 = a_1, ... ,l_i-1 = a_i-1, l_i = 0]
  M_1 = E[M|l_1 = a_1, ... ,l_i-1 = a_i-1, l_i = 1]
  if M_0 >= M_1:
    a_i = 0
  else:
    a_i = 1
return a_1, ..., a_n

We obtain a literal assignment satisfying at least \(\frac{7}{8}\) of the clauses in \(\mathcal{O}(mn)\) time.

Closing notes

Håstad showed that finding a polynomial time algorithm satisfying more than \(\frac{7}{8}\) of the clauses for satisfiable formulas is impossible, unless… well unless \(\mathcal{P} = \mathcal{NP}\). Hence, given that the latter does not hold and a polynomial time constraint, this elegant algorithm is optimal with respect to fulfilling as many clauses as possible.

I discovered this through Angelika Steger’s graduate course Randomized Algorithms and Probabilistic Methods at ETH. It is among the top three courses I have attended during all of my studies.