CATS-Nov-22-2013
From Theory
Title[edit]
Pretty good, though still Exponential, algorithms for 3-SAT and Min Ind Set
Speaker[edit]
William Gasarch, University of Maryland
Abstract[edit]
SAT can clearly be solved in roughly 2^n steps. We would like to solve it in poly time, though this is unlikely. Even so, can we improve upon 2^n? YES! In this talk we show a sequence of algorithms that do BETTER than 2^n time for 3-SAT. (example: (1.5)^n).
We will (time permitting) also look at Maximum Ind Set. Here too we will get better, though still exponential time for this problem. Of interest- in some cases it is not the ALGORITHM we change but the ANALYSIS.
