Μάθημα : Υπολογιστική Πολυπλοκότητα

Καλησπέρα σε όλα,

Η ύλη του μαθήματος για τις εξετάσεις αποτελείται από τα κεφάλαια 7 και 8 του βιβλίου Sipser. Συγκεκριμένα, για κόσμο που μελετάει από άλλες πηγές:

1) Ασυμπτωτικός συμβολισμός (Big-O notation). Όχι εξειδικευμένα πράγματα.

2) Ντετερμινιστικές και μη ντετερμινιστικές μηχανές Turing. Πολυταινιακές μηχανές. Όχι αποδείξεις ισοδυναμίας μοντέλων, κυρίως να ξέρετε τι είναι και να μπορείτε να χειριστείτε τέτοιες μηχανές.

3) Κλάσεις χρονικής πολυπλοκότητας P, NP, EXP. Συμπληρωματικές κλάσεις (πχ coNP).

4) Αναγωγές πολυωνυμικού χρόνου. NP-πληρότητα. NP-πλήρη προβλήματα σχετιζόμενα με λογικούς τύπους, γραφήματα και σύνολα ακεραίων. Όχι θεώρημα Cook-Levin.

5) Κλάσεις χωρικής πολυπλοκότητας PSPACE, L, NL. Θεώρημα Savitch.

6) PSPACE πληρότητα, NL πληρότητα και αντίστοιχα προβλήματα. NL=coNL. 

Αν υπάρξει χρόνος να καλυφθούν περισσότερα πράγματα από αυτά στο μάθημα (μάλλον δύσκολο), τα όποια έξτρα πράγματα δούμε δεν θα περιλαμβάνονται στην εξεταστέα ύλη. 

Γ.Λ.