发帖
雷达卡
Consider an instance of SAT with m clauses, where every clause has exactly k literals.
(a) Consider a simple randomized algorithm that assigns each variable to TRUE or FALSE
uniformly at random. What exactly is the expected number of clauses that are satisfied?
(b) Give a derandomization of the above randomized algorithm using the method of conditional
expectations. Show your reasoning.
京公网安备 11010802022788号
