Computability and Complexity

Code 3.4.3254.8
Semester 8th
Flow L - Computer Software
Category Obligatory by selection
Credits 4
Class Hours - Lab Hours 3 - 0
Lecturers Nikos Leonardos, Stathis Zachos, Petros Potikas (T & R Associates)
Links Helios, Course's Website
Web Platform Class 1: Webex


Computability: Logical foundation of computer science, historical overview about the problem of decidability of mathematical propositions, solvability or computability of problems with an effective, i.e. algorithmic, way. Simple equivalent computational models: Turing machines, WHILE programs. Induction and recursion, encodings and semantics. Fix-point theory. Arithmetical hierarchy.
Complexity: Relations among complexity classes. Reductions and completeness. Oracles. Polynomial hierarchy. Probabilistic, interactive and counting classes. Advanced topics of formal grammar theory. Applications to the syntax of programming languages.