The Random SAT framework formulas are generated as follows. Given the number of

Question

The Random SAT framework formulas are generated as follows. Given the number of variables n, several clauses m, and a number of literals per clause k, repeatedly select k out of n literals uniformly at random, and for each selected literal, choose whether it is negated or not with probability 1/2. Repeat this process until there are m distinct clauses (provided m is small enough). For each of the following sub-questions, give both the number for the numeric part of the sub-question, and a formula for the general part.

(a) Suppose there are n = 5 variables x1, x2, x3, x4, x5, and you select one clause with k = 5 literals in it. How many assignments to these variables would satisfy this clause? Now give a formula for a number of assignments satisfying an arbitrary clause with n = k literals.

(b) Now suppose that n = 8, k = 5. How many assignments to all n = 8 variables satisfy one clause with k = 5 literals? Give a formula for a number of assignments satisfying an arbitrary clause with n > k literals.

(c) Now suppose that n = 8, k = 5 and m = 3. What is the average (that is, expected) number of assignments satisfying a randomly generated formula with these parameters? Give a formula for arbitrary n, k, m, where n > k and m ? n for some constant c ? 0

(d) Now, consider the following randomized algorithm: on a given formula ? generated as above with parameters n, k, m, pick a random assignment and check if it satisfies ?. If so, accept, otherwise fail. What is the probability that this algorithm will succeed, on average, for a formula ? generated with n = 8, k = 5 and m = 3? Give a bound on m such that the probability of this algorithm succeeding on formulas generated with parameters n, k, m is at least 1/2.

(e) How large should m be for n = 8, k = 5 to guarantee that the resulting formula is always unsatisfiable? Give a general formula for m as a function of arbitrary n and k.

Explanation / Answer

SAT is an NP-complete problem, so we do not expect to have a polynomial-time algorithm (deterministic or randomized) for it. Today’s topic is on just trying to beat the bruteforce 2n -work algorithm of trying all possible solutions. We will discuss a randomized algorithm with work roughly 1.733n , then we’ll reduce that to 1.5 n , then we’ll reduce that to 1.33n . The current best bound is roughly 1.31n . Note that this has to do with guarantees on worst-case instances. There are a number of heuristic strategies that work extremely well on instances that arise in many applications, but today’s topic is not on those.

The 3-SAT problem is the following. You are given a 3-CNF formula (an AND of ORs, where each OR contains at most 3 literals) over n Boolean variables. Your goal is to find an assignment to the n variables that satisfies the formula, if one exists. For example, consider n = 4 and the formula: (x1 ? x¯2 ? x3)(¯x1 ? x2 ? x4)(x2 ? x¯4)(x3 ? x4)(x1 ? x¯3). This formula has three satisfying assignments. Using bit-vector notation (1=true, 0=false), assignments 1110, 1101, and 1111 satisfy the formula, and the rest do not. If we add the clause (¯x1 ? x¯2) to it, getting: (x1 ? x¯2 ? x3)(¯x1 ? x2 ? x4)(x2 ? x¯4)(x3 ? x4)(x1 ? x¯3)(¯x1 ? x¯2) then the formula is unsatisfiable. We typically use m to denote the number of clauses. Note that m = O(n 3 ).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.