Dr Rahul Santhanam – University of Edinburgh
The Complexity of the Satisfiability Problem
The Boolean satisfiability problem, which asks whether a given Boolean formula has a truth assignment of its variables for which the formula evaluates to true, is one of the most fundamental problems in computer science. Apart from being of immense practical relevance, it is intimately connected to the celebrated NP vs P question. In this survey talk, I will motivate the study of this problem, describe some of the known algorithms for it which are known to do better than the trivial brute-force enumeration of truth assignments, and tell you about some exciting recent developments which show that improved algorithms for the Satisfiability problem would lead to new complexity lower bounds.
School of Computing, Robert Gordon University, St Andrew Street, Aberdeen, Lecture Room A12, 14:00 – 15:00.