Determining the Scope of Alorithms

Date and time: 
Tue, Jan 9 2007 - 3:00pm to Wed, Jan 10 2007 - 2:45pm
220 Deschutes
Katrina Ray
University of Oregon

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.