Finding a satisfying assignment for planted NAE-E3-SAT using a voting style algorithm
Siavash Bolourani · Summit (Simon Fraser University) · 2010
A random planted formula is constructed by, first, fixing a certain, planted assignment to the variables, and then adding only clauses that are satisfied by the planted assignment.The purpose of such approach is to generate a random-like formula that is guaranteed to have a satisfying assignment.The random planted 3-SAT has received significant attention.In particular, it has been shown through different approaches that when containing sufficiently many clauses such a problem is solvable with high probability in polynomial time.In this work we obtain a similar result for the random planted Not-All-Equal-SAT problem, which is defined in the same way except that the clauses added are the Not-All-Equal clauses.We follow one of the aforementioned approaches by Krivelevich and Vilenchik.Their algorithm first obtains an approximation of the planted solution by counting the number of occurrences of each variable positively and negatively, then unassigning 'unreliable' variables and searching an assignment for then by brute force.In the case of NAE-SAT the first step, voting, makes no sense.We show that the same result can be achieved by solving the MAX-CUT problem in the co-occurrence graph of the formula.iii Publication of this thesis was an interesting journey.It is my honor to thank those whom I was fortunate to work with in my MSc studies.First of all, I would like to that Andrei Bulatov and David Mitchell for being great supervisors and mentors.David has been strong guidance through out my MSc studies.He was patient with the unconventional research avenues I took.Andrei was an idle supervisor who made sure that I focused on the problem and gave invaluable insight that shaped my approach to the problems that arose in my research.He gave me the freedom to develop my own direction and writing style while teaching me a great deal of his own.I was fortunate doing my thesis under their