Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Changes in Introductory Theory

Expand Messages
  • Lance Fortnow
    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
    Message 1 of 2 , Mar 30, 2004
    • 0 Attachment
      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.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 3/30/2004 05:49:00 PM

    • Lance Fortnow
      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
      Message 2 of 2 , Mar 31, 2004
      • 0 Attachment
        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.

        --
        Posted by Lance Fortnow to My Computational Complexity Web Log at 3/30/2004 05:49:00 PM

      Your message has been successfully submitted and would be delivered to recipients shortly.