Probabilistic Methods in 3-SAT Problem and Max 3-SAT Problem

Randomized Algorithms CS648 Lecture 23 Probabilistic methods - II 1

3-SAT PROBLEM Its solution can be viewed as an application of Probabilistic method. 2

3-SAT Problem Notations: A Boolean variable: a variable that can take value true or false. A term: a Boolean variable or its negation. A clause: Disjunction of 3 disjoint terms. Let ??, ,?? be ? Boolean variables. Examples of a term: ?? ?? Examples of a clause: ?? ?? ??? ?? ?? ?? Note that ?? ?? ?? is not a clause. 3

3-SAT Problem Problem: Given? clauses ??, ,?? defined over ? Boolean variables ??, ,??, is there any assignment of true/false to the variables that will satisfy each clause. Why is this problem difficult ? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? Setting ?? and ?? to true and ?? to false the first 3 clauses get satisfied but 4th clause is notsatisfied. So trying to satisfy a subset of clause, one might render many others dissatisfied. 4

3-SAT Problem Problem: Given? clauses ??, ,?? defined over ? Boolean variables ??, ,??, is there any assignment of true/false to the variables that will satisfy each clause. Results known: 3-SAT Problem NP-complete. It is unlikely to have any polynomial time solution. 5

Max 3-SAT Problem Problem: Given? clauses ??, ,?? defined over ? Boolean variables ??, ,??, compute the maximum number of clauses that can be satisfied simultaneously ? Results known: Max3-SAT Problem NP-complete. It is unlikely to have any polynomial time solution. The power of Randomization An approximation algorithm: There is a very simple randomized algorithm that will satisfy at least ? ?? clauses. 6

Max 3-SAT Problem Monte Carlo Algorithm: For each ? = ? to ? assign value true/false to ?? randomly uniformly and independently; return all the clauses that are satisfied. Analysis: ?: the number of clauses that are satisfied. ??= ? if ?????? ?? is satisfied ? otherwise ? = ??? ? ? = ??[??] = ??[??= ?] =? ? ? ?? = ? 7

Max 3-SAT Problem Las Vegas Algorithm: Repeat { For each ? = ? to ? { assign value true/false to ?? randomly uniformly and independently; } Let ? be the number of clauses that are satisfied. } Until? ? ?? Analysis: ?: the probability that a single iteration of Repeat loop is successful Expected running time: ?(?+? ?) 8

Getting a lower bound on ? ?: the number of clauses that are satisfied. ??= ? if ?????? ?? is satisfied ? otherwise ? = ??? ? ? =? ?? Alternate formulation of ? ? : Let ??: probability that there are exactly ? clauses that are satisfied. ? ? = ?? ?? Question: What is the relation between ? and ?? s ? Answer: ? = ? ? ???? 9

Getting a lower bound on ? ? = ? ? ???? Express ? as ?? + ? where? ? < ?. So? ?? = ?? + ??/?. If ? = ? then ? ?? ? is 1. For all other cases, ? fraction with denominator ?,?,or ?. So ? ?? ? ?/? Aim: To get a lower bound on ? ? ???? ? ? =? ?? = ?? ?? ?? ? is a Let? be the largest integer <? ?? = ? ? ? ?? + ? ? ??? ?? ?<? ? ?? + ? ? ????? = ? ?<? ?? + ? ? ? ? + ?? ? ???? ? ?? ? ? ? ?? ? + ?? ? ?? ? 10

Max 3-SAT Problem Las Vegas Algorithm: Repeat { For each ? = ? to ? { assign value true/false to ?? randomly uniformly and independently; } Let ? be the number of clauses that are satisfied. } Until? ? ?? Analysis: ?: the probability that a single iteration of Repeat loop is successful Expected running time: ?(?+? ?) = ?( ? + ??) 11

Max 3-SAT Problem Theorem: There is an ?( ? + ??) time Las Vegas algorithm for approximate Max 3-SAT Problem. It computes an assignment which satisfies at least ? ?fraction of clauses. Question: Is ? ?the best approximation factor that can be achieved for this problem ? Answer: Yes, indeed. It has also been proved that if P NP, then there can not be any approx. algorithm that can achieve a factor better than ? ? . So the simple randomized algorithm is also the best possible algorithm. Isn t it very inspiring ? 12

PROBABILISTIC METHOD: ALTERATION 13

Alteration Suppose we wish to show the existence of a structure with desired properties. The following method is sometimes quite useful Form a random instance of the structure. This structure will not have the desired property but it will be very close to having the desired property. Slightly alter the random instance and the resulting structure will have the desired property. 14

AN INTERESTING PROBLEM IN COMBINATORIAL GEOMETRY 15

? A conjecture: If? points are placed in a unit square, the smallest of the ? triangles will have area?(?/??). 3 The conjecture was disproved in 1982. Theorem: It is possible to place ? points in a unit square so that each triangle has area ?(??? ? ??). 16

? Theorem (we shall prove): It is possible to place ? points in a unit square so that each triangle has area at least ?????. ? 17

? 1. Select ? points randomly uniformly. 2. ? : the no. of triangles with area less than ?????. 3. Calculate ?[?]and make useful inference Suppose ?,?,?are3 points selected randomly uniformly from unit square. Let ?: probability that triangle ???has area less than ?????. ? ? Question: What is relation between ? ? and ? ? ? Answer: ? ? = 3.? 18

Probability(triangle ??? has area less than ?) ? Question: Given that |??|= ?, what is the prob. that triangle ??? has area < ? ? Answer: less than ? ? ? ? ? ? ? ?? ? ? ?? ? 19

Probability(triangle ??? has area less than ?) ? Question: Given that |??|= ?, what is the prob. that triangle ??? has area < ? ? Answer: less than ? ? ? ? ? ? + ?? Question: P(|??| [?,? + ??]) = ? Answer: ??? ?? ? ? Question: What is P(triangle ???has area < ?)? 2 ? ? ? ? ??? ?? Answer: 0 2 =???? = ? ? ???? 0 20

Probability(triangle ??? has area less than ?) ? Lemma: If Suppose ?,?,?are3 points selected randomly uniformly from unit square, then the prob. that triangle ??? has area less than ? is bounded by ????. ? ? ? : the no. of triangles with area less than ?????. ? ? ??? ??? ?? ? 3. ? ? = < ?.? ? Question: What is ? ? if 2? points are selected ? Answer: < ? 21

? 1. Select 2? points randomly uniformly. 2. ? : the no. of triangles with area less than ?????. 3. Note that ? ? <? 4. Remove one point from each triangle with area less than ? ? ?????. Expected number of points left: > ?. There is no triangle formed by these ? points with area less than ? ????? . 22

AN INTERESTING PROBLEM IN GRAPH THEORY 23

Dense graphs with large girth ? = ?,? : undirected unweighted graph on ?vertices and ? edges. Girth of ?: Length of smallest cycle in ?. It can be observed that if a graph is dense, its girth will be small. For example, a complete graph has girth ?. In fact the following result is well known in graph theory. Theorem: If a graph has ??+?/?or more edges, its girth must be at most 2?. Question: Is the result mentioned in the theorem above tight ? Answer: Yes, there are graphs which have ?(??+?/?) edges and girth at least ?. 24

Dense graphs with large girth Theorem: For each ? , there are graphs on ? vertices having at least 1 edges and girth at least ?. 4??+?/? We shall prove this theorem using the method of alteration. We shall provide just a sketch. The remaining details are straightforward and you are encouraged to fill in these details. The following Lemma will be useful. Lemma: The number of cycles of length ?in a complete graph on ?vertices is ? ? ? ? ! ? 25

Dense graphs with large girth Construct a random graph where we add each edge randomly independently with probability ?. What should be the value of ?so that expected number of edges is close to 1 choose? = ? 2??+?/?? Show that the expected number of cycles of length ? in the random graph will be less than ????. Show that expected number of cycles of length less than ? is less than ??? ?/?. Remove one edge from each cycle of length less than ?. Show that there will still be 1 value of ?). We are done. ? ? ? 4??+?/? edges left (choose sufficiently large 26