Computability and Complexity

 

Lecture in Winter Term 2020/2021

 
A turing machine Copyright: Rocky Acosta (CC BY 3.0)

Contact

Phone

work
+49 241 80 21703

Email

E-Mail
 

Schedule

Mon 15:00 general deadline
Mon 14:30-16:00 General exercise class
Wed 8:30-10:00 Question hour
Thu and Fri: Tutorial sessions

 

 
 

Content

What problems can be solved using a computer? And what problems can be solved efficiently? - These are the questions we consider in this course. We try to answer these questions mathematically. In order to do this, we define and model the terms problem, computer, and efficiency. We are then able to make definite and far-reaching statements concerning the efficiency of solving problems with computers. Basics for this course are mathematical models and methods such as Turing machines and reductions. The reference to realistic computers and practical problems will be evidently explained. A highlight is the NP-complete theory. The impact of this type of problems on theoretical and practical applications cannot be overrated. The course is structured as:

Part 1: Computability

  • Chapter 1: Introduction and background
  • Chapter 2: Modelling of machines and programming languages
  • Chapter 3: Non-computable problems

Part 2: Complexity

  • Chapter 4: The complexity classes P and NP
  • Chapter 5: NP-completeness
  • Chapter 6: Heuristics and approximation algorithms for NP-hard problems
 

Organization

Lecture will be held in german.

Lecturer

Martin Grohe

 

External Links