____________________________________________________________________________ ** Note Day: Monday ** ** Note Day: Monday ** ____________________________________________________________________________ B O S T O N U N I V E R S I T Y Computer Science Department C O L L O Q U I U M MONDAY, FEBRUARY 20 3:00pm (Coffee served at 2:30pm) Seminar Room / MCS 135 ____________________________________________________________________________ Klaus Ambos-Spies University of Heidelberg will speak on Resource Bounded Genericity Concepts ABSTRACT The close relation between finite extension arguments, a central proof technique in computation theory, and the topological Baire category concept was observed already in the early days of recursion theory. The advantage of the nonconstructive category approach is its modularity which greatly simplifies some proofs; the nonconstructivity, however, is also a great disadvantage since there are no complexity bounds on the objects obtained by this approach. The latter defect can be eliminated, however, by effectivizing the category concept. Effective Baire Category and the corresponding generic sets have been extensively studied in recursion theory. In our talk we discuss further refinements of bounded category and genericity in computational complexity theory. These concepts are very powerful and elegant tools in structural complexity theory. A first resource bounded genericity concept for the deterministic time (or space) classes was introduced by Ambos-Spies, Fleischhack and Huwig in 1985. While this concept was directly based on finite extension arguments, somewhat later Lutz introduced a resource bounded Baire category concept and a corresponding genericity notion. Lutz's concept and an improvement of it by Fenner, however, is incomparable with the previous concept. We discuss the advantages and short comings of both concepts and introduce a new concept which subsumes both of them. This new concept seems to be adequate for the typical diagonalization arguments. As we also point out, however, this concept also has its limitations. To overcome these limitations we define a hierarchy of still stronger genericity concepts,thereby showing that it is impossible to give optimal genericity concepts for the standard complexity classes. Finally, we shortly compare the resource bounded genericity concepts with Lutz's resource bounded measure theory. Host: Prof. Steve Homer ------------------------------------------------------------------------------- For colloquium info, including directions, see http://cs-www.bu.edu/colloquium For more information contact Prof. Mark Crovella -------------------------------------------------------------------------------