Department of Computer Science & Engineering

University of Ioannina

Computability and Complexity

Course Feature
Class Description

Course_ID: MYE 036

Weekly Hours: 5

Semester: >=6

ECTS Credits: 5

Course Homepage:

Description: Computational problems and formal languages.

Primitive recursive functions.

Recursive functions.

Turing machines and equivalent models of computation.

Church’s Thesis.

Kleene normal form.


Recursive and recursively enumerable sets.

The arithmetic hierarchy.

Non-deterministic Turing machines.

Complexity classes.

The classes P, NP and PSPACE.

Reductions and Completeness.

NP-complete problems.

Grammars and the Chomsky Hierarchy.