Graduate Research Forum Details
Determining the Scope of Alorithms
| Author: | Katrina Ray |
|---|---|
| Date: | January 09, 2007 |
| Time: | 15:00 |
| Location: | 220 Deschutes |
Abstract
Algorithms that are known to work well in practice are often applied to problems besides the one that they were originally designed to solve. This is accomplished by transforming the input and output into the appropriate format. Applying an algorithm to other problems is only useful when these transformations are efficient, hence there are limits on the scope of an algorithm.
In this paper we define the capability of an algorithm in terms of the complexity of the problems that it can be used to solve. This definition can be used to establish exact bounds on the capability of the well known DPLL algorithm for solving the boolean satisfiability problem.