|
The study of the theory of computing began in the 1930s with the work of Turing and Gödel, and has continued since then through the work of researchers too numerous to name.
Early researchers primarily asked what could be computed if resources such as time and memory were unbounded, and how the computability of one problem related to the computability of another problem.
Some computational problems that you might initially think are relatively straightforward were shown to be unsolvable.
Results from this theory of computability have some important practical significance, but some of them are rather esoteric for the practicing computer scientist.
Mainly beginning in the 1960s, emphasis among computer scientists shifted from unbounded resources to cases where the available resources were bounded by some function of the size of the problem.
Results having to do with bounded-resource computation generally fall under the heading of complexity theory.
It was found that some of the methods of computability theory applied quite nicely to complexity theory, while others did not seem to travel well.
Complexity theory has matured over time and is now a cornerstone of computer science, where its results are of greater significance to the practicing computer scientist than those of computability theory.
Knowledge of the basic results of complexity theory are now recognized as part of the core of computer science.
There is another body of work that is also called complexity theory. It is concerned with common characteristics among "complex systems," and has nothing to do with the complexity theory discussed here.
It is worth mentioning that a large piece of software can be considered a "complex system."
Here, we are not interested in that aspect of software. For us, complexity is concerned with the resources that software uses when it runs.
Before the mid 1970s, most of the more important results of both computability and complexity theory were impossibility results. They stated that certain problems could not be solved, or could not be solved within given resource constraints.
Beginning in the 1970s, and continuing through the present day, there have been some remarkable results that show how the difficulty of solving one problem can be turned into the possibility of solving another.
Techniques have been developed that are so subtle, they solve problems that you would initially conclude could not possibly be solved.
This course will explore important results in the theory of computing.
You will be expected to do proofs relating to the material covered.
We will hit the high points of computability theory, then study the basics of complexity theory, and then examine how complexity theory makes tools available to the working software designer.
|