Computational Complexity

Tuesday, March 30, 2004

 
Changes in Introductory Theory

Posted by Lance

Comments to my last post basically ask how has the introductory courses in theory has changed over the years. My first reaction: remarkably little. Theoretical models of computation do not depend on the current hot technology, particularly at the undergraduate level. Many of the basic results we teach today were also taught say 25 years ago. But without doubt theory courses have changed their emphasis on various topics over the years.

Every professor teaches a theory course differently so there is no fixed answer to what has changed. But here are some trends that I have seen (from a distinctly American point of view):

• Less emphasis on automata theory, particularly for context-free languages. Many schools do away with automata theory all together.
• Less depth in computability theory. Most courses will cover undecidability but you'll less often see the recursion theory or even Rice's theorem taught.
• Does anybody still teach the Gap, Union and Speed-Up Theorems and Blum complexity measures anymore?
• Only one new theorem since the mid-70's has become a fundamental part of an undergraduate complexity course: The 1988 Immerman-Szelepcsényi Theorem stating that nondeterministic space is closed under complement.
• There has been a trend in adding some recent research in complexity as the end of a course based on the interests of the instructor: Randomized computation (though recent algorithms for primality might change how it gets taught), cryptography, interactive proofs, PCPs and approximation, quantum computing for example. Parallel computation has come and gone.

But remember these are exceptions. Basic topics like Turing machines, undecidability, NP-completeness, Savitch's theorem and time and space hierarchies still get taught much the way they were taught in the 70's.

5:49 PM # 0 comments

Comment Feeds: This Post All