Print LaTeX

Randomized k-SAT algorithm

Consider an instance of SAT with $m$ clauses, where every clause has exactly $k$ literals.

  • Give a Las Vegas algorithm that finds an assignment satisfying at least $m(1-2^{-k})$ clauses, and analyze its expected running time.
  • Give a derandomization of the randomized algorithm using the method of conditional expectation.
Source: from book "Probability and Computing: Randomized Algorithms and Probabilistic Analysis"
delete flag offensive retag edit Add to a Problem Set

Related books