Bureaucrats, editor, Administrators
373
edits
Changes
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 ..."
== Title ==
Pretty good, though still Exponential, algorithms for 3-SAT and Min Ind Set
== Speaker ==
William Gasarch, University of Maryland
== Abstract ==
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.
Pretty good, though still Exponential, algorithms for 3-SAT and Min Ind Set
== Speaker ==
William Gasarch, University of Maryland
== Abstract ==
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.
