Oral Comprehensive Exam Details
Complexity of Problems in Algorithms
| Author: | Katie Ray |
|---|---|
| Date: | October 04, 2006 |
| Time: | 09:30 |
| Location: | 220 Deschutes |
| Committee: | Matt Ginsberg (Chair) David Etherington Chris Wilson Gene Luks |
Abstract
Complexity theory has attempted to explain why some computational tasks are harder to solve than others. This involves providing a measurement of the computational resources required to solve problems and grouping problems together that have similar resource requirements.
The algorithms used to solve problems are analyzed in terms of their asymptotic runtimes. Sometimes algorithms are also analyzed by the amount of memory required by the computation. The study of algorithms is closely tied to the study of complexity theory because a problem is characterized into a particular complexity class based on the resource requirements of the best known algorithm for solving the problem. Furthermore, an algorithm for one problem should be able to solve problems that have similar resource requirements without a substantial loss in efficiency.
The current relationship between these two fields is that the complexity of a problem is based on the best known algorithm for solving it. I would like to define the capability of an algorithm in terms of the complexity of the problems that it can be applied to. I will also discuss why this may be a useful concept as well as one application of this idea.