181.142 Complexity theory Canceled
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2019S, VU, 2.0h, 3.0EC, to be held in blocked form

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise

Aim of course

Introduction to Complexity Theory: Understanding of basic notions, concepts, methods, and results.

Subject of course

Basic notions of complexity theory, deterministic und non-deterministic complextiy classes, NP-complete problems, logarithmic space, the polynomal hierarchy, exponentially hard probleme, applications.

Additional information

ECTS Breakdown

  2 h quiz 
 30 h lecture (12 classes including preparation)
 40 h exam preparation 
  3 h written + oral exam
-----------------------------------------------------------
 75 h = 3 Ects

Lecturers

Institute

Examination modalities

quiz,
written exam,
oral exam

 

Course registration

Begin End Deregistration end
11.02.2019 00:00 05.03.2019 23:55 19.03.2019 23:55

Curricula

Literature

C. Papadimitriou. "Computational Complexity". Addison-Wesley, 1994. M. R. Garey and D. S. Johnson. "Computers and Intractability". Freeman, 1979.

Previous knowledge

  • Students are assumed to have a basic knowledge in mathematical logic and to be familiar with basic concepts of complexity theory (to the extent taught in the course "Formale Methoden der Informatik").
  • Moreover, students should have basic mathematical skills (like carrying out proofs by induction) as taught in the mathematics courses in the bachelor studies.

Miscellaneous

Language

English