Difference between revisions of "CATS-Nov-22-2013"
From Theory
(Created page with "== Title == Pretty good, though still Exponential, algorithms for 3-SAT and Min Ind Set == Speaker == William Gasarch, University of Maryland == Abstract == SAT can clearly ...") |
(No difference)
|
Latest revision as of 20:37, 19 November 2013
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.
