0

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"

Related Content