Given a CNF formula phi over n variables with m clauses where each clause contains exactly k literals We need to give an assignment alpha: {x_1,..., x_n} rightarrow {0,1} that satisfies at least 2^k - 1/2^k clauses. The algorithm that we use to find solution is a familiar version of random assignment: Repeat the following 2^k m In n-times: Assign to each variable x_1,..., x_n values 0 or 1 with equal probability Substitute the assigned values for variables into 4> (i.e. simplify 0 on a given assignment) Compute the number of satisfied clauses (i.e. m - t, where t is the number of remaining after simplification clauses, including the empty ones). If computed number of satisfied clauses is over clauses then return the assignment and stop Return " Failure" Show that this algorithm finds an assignment that satisfies at least 2^k - 1/2^k m clauses with probability at least. Given a CNF formula phi over n variables with m clauses where each clause contains exactly k literals We need to give an assignment alpha: {x_1,..., x_n} rightarrow {0,1} that satisfies at least 2^k - 1/2^k clauses. The algorithm that we use to find solution is a familiar version of random assignment: Repeat the following 2^k m In n-times: Assign to each variable x_1,..., x_n values 0 or 1 with equal probability Substitute the assigned values for variables into 4> (i.e. simplify 0 on a given assignment) Compute the number of satisfied clauses (i.e. m - t, where t is the number of remaining after simplification clauses, including the empty ones). If computed number of satisfied clauses is over clauses then return the assignment and stop Return " Failure" Show that this algorithm finds an assignment that satisfies at least 2^k - 1/2^k m clauses with probability at least