1
$\begingroup$

Let a Boolean formula $\varphi$ in K-CNF with $m$ clauses be given as an input.

The goal of an algorithm is to find an assignment satisfying at least $m(1-2^{-k})$ clauses of $\varphi$.

I need to find:

  1. A randomized algorithm and estimate its expected time
  2. A deterministic algorithm and argue about its correctness using the method of conditional expectations

Here are my thoughts about approaching the design of algorithms for this purpose:

Randomized algorithm:

  • assigning Boolean values randomly to Boolean variables, counting satisfied clauses
  • Finding the expected number of satisfied clauses
  • Iterate through as much as is needed

Deterministic algorithm:

  • Considering Boolean variables one by one
  • For a given variable $p$, count how many clauses, that have not been made true yet, are made true by setting $p$ true, and how many by setting $p$ false

  • Act "greedily"

Does anybody have an example of what such an algorithm would look like in both cases? I don't really have an idea of where to start.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.