The Computer Science Colloquium

Thursday, May 20, 4:15pm, room 9204/05


Paul Schupp
(University of Illinois at Urbana-Champaign )

"Generic computability, complexity and Turing reducibility"

    We give the definitions of generic computability and generic-case complexity and recall some of the main results from group theory. We then discuss how generic computability interacts with classical concepts from computability theory: Turing reducibility, bi-immunity, 1-genericity and the Arithmetic Hierarchy.

The Colloquium is supported by generous contributions from the Bloomberg, Information Builders, Inc., and Netlogic, Inc.

       


365 Fifth Ave, New York City 10016 | Room 4319 | Phone: 212.817.8190 | Fax: 212.817.1510 | compsci@gc.cuny.edu