elen
Alumni
elen
Alumni
  2. /
  3. Computational Complexity

Computational Complexity

Course ID
CEID_NY302
Department
Division of Applications and Foundations of Computer Science
Professor
KAKLAMANIS CHRISTOS, TSICHLAS KOSTAS
Semester
6
ECTS
4
  • Turing machines.
  • Special types and combinations of Turing machines.
  • Non-deterministic Turing machines.
  • Universal Turing Machines.
  • Algorithmically solvable problems.
  • Church’s position.
  • Algorithmically unsolvable problems.
  • The closure problem.
  • The concept of computational complexity of algorithms.
  • Problems solvable in an efficient manner.
  • Classes of complexity.
  • The P and NP classes.
  • Reductions between problems.
  • Problems complete in class NP.
  • The relation of classes P and NP.
  • The polynomial hierarchy of complexity classes.
  • Spatial complexity.
WebsiteCourse Outline
Skip to content