Friday 18th Mar 2011 – Dr Rahul Santhanam

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.

About Admin

School of Computing Science and Digital Media, Robert Gordon University, Aberdeen, Scotland
This entry was posted in Research Seminar. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s