Μηχανές Turing. Ειδικοί τύποι και συνδυασμοί μηχανών Turing. Μη ντετερμινιστικές μηχανές Turing. Καθολικές μηχανές Turing. Αλγοριθμικά επιλύσιμα προβλήματα. Η θέση του Church. Αλγοριθμικά μη επιλύσιμα προβλήματα. Το πρόβλημα της περάτωσης. Η έννοια της υπολογιστικής πολυπλοκότητας αλγορίθμων. Προβλήματα επιλύσιμα με αποδοτικό τρόπο. Κλάσεις πολυπλοκότητας. Οι κλάσεις P και NP. Αναγωγές μεταξύ προβλημάτων. Προβλήματα πλήρη στην κλάση NP. Η σχέση των κλάσεων P και NP. Η πολυωνυμική ιεραρχία κλάσεων πολυπλοκότητας. Πολυπλοκότητα ως προς χώρο.
