VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

251-0496-01L 5 Credits BSC , DS , MSC D-INFK

Complexity Theory

Komplexitätstheorie

Lecturers & Examiners: Prof. em. Dr. Juraj Hromkovic, Dr. Christos Antonios Kapoutsis
VVZ CR n/a

Last Updated: 2026-02-05 15:29:33

Abstract

The main goal of the complexity theory is t to classify computing problems with respect to their hardness. The complexity theory develops methods and proof techniques for establishing lower and upper bounds on the complexity of concrete problemsand for investigating the fundamental propeties of abstract complexity measures and computing models.

General Information

Language
English
Levels
BSC , DS , MSC
Frequency
Yearly recurring

Examination

Type
session examination
Mode
written 120 minutes
Aids
Books: Introduction to the Theory of Computation, M. Sipser; Theoreti- cal Computer Science, J. Hromkovic / The problem sets (statements & so lutions) distributed during the semester / Personal notes from class.

Course Components

Type Title Time & Place Hours
lecture Komplexitätstheorie
  • Mon 10:15-12:00 (CAB H 52)
2 h weekly
exercise Komplexitätstheorie
  • Mon 13:15-14:00 (CAB G 52)
1 h weekly

Offered In