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.


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.