Introduction to Complexity Theory

Introduction to Complexity Theory

Course with SWS 2/1/0 (lecture/exercise/practical) in WS 2014

Lecturer

• Rafael Peñaloza Nyssen

Tutor

• Marcel Lippmann

SWS

• 2/1/0

Modules

• INF-B-510
• INF-B-520
• INF-BAS6
• INF-VERT6
• MCL-TCSL
• MCL-PI
• MCL-KR
• MCL-MV

Examination method

• Oral exam

Lecture series

• Complexity Theory

• Information
• Literature

Complexity Theory studies the computational properties of decision problems. In this course, we introduce some of the most important notions of complexity theory. We define the basic complexity classes (P, NP, PSpace, etc.) and provide tools for showing that a problem belongs to, or is as hard as any problem in these classes.

The course is aimed to students with little or no knowledge of the topic.

• Christos H. Papadimitriou. Computational Complexity, Addison Wesley, 1994.
• Michael Sipser. Introduction to the Theory of Computation, PWS, 1997.