Courses
Diploma Theses
FHS Projects
Curriculum
Applications Forum Talks

Search:

Time and place:

Thursday 8:30-10:00, K 123A. The first lecture will be on March 11.

Contents:

This course is based on 326303: Computability Theory. The topics to be covered are:

Reducibility relations: Post's problem and the arithmetical hierarchy. This belongs to the area of classical recursion theory.
Undecidablity results in the realm of word problems and the theory of elementary arithmetic.
Abstract complexity theory: Blum's complexity theory, subrecursive hierarchies, and complexity theory for Turing machines.
Basic theory of NP-completeness.

Literature:

Lectures notes will be handed out.

This page is maintained by Heinrich Rolletschek .

Last updated on March 1, 2004