Υπολογιστική Πολυπλοκότητα (M171 και ΘΠ20)

Υπολογισιμότητα:

• Μηχανές Turing (πολυταινιακές Μ.Τ., μη-ντετερμινιστικές Μ.Τ.)
• Η θέση Church-Turing.

Χρονική πολυπλοκότητα:

• Σχέση πολυπλοκότητας μεταξύ μοντέλων (Μ.Τ., πολυταινιακών Μ.Τ. και μη-ντετερμινιστικών Μ.Τ.).
• Χρονική πολυπλοκότητα μη-ντετερμινιστικών Μ.T..
• Η κλάση P.
• Η κλάση NP.
• Το θεώρημα προβολής.
• Η κλάση coNP.
• Η κλάση EXP.
• Αναγωγές και πληρότητα, η έννοια της NP-δυσκολίας.
• Το θεώρημα Cook-Levin.
• NP-πλήρεις γλώσσες.
• Ψευδοπολυωνυμικότητα και ισχυρά NP-πλήρεις γλώσσες.

Χωρική πολυπλοκότητα:

• Το θεώρημα του Savitch.
• H κλάση PSPACE.
• PSPACE πληρότητα.
• Οι κλάσεις L, NL και EXPSPACE.
• NL πληρότητα.

Θεωρήματα Ιεραρχίας:

• Το Θεώρημα Χωρικής Ιεραρχίας.
• Το Θεώρημα Χρονικής Ιεραρχίας.

Οι φοιτητές θα πρέπει να έχουν αποκτήσει εξοικείωση με την έννοια του αλγορίθμου και την ανάλυση της πολυπλοκότητάς του. Πέραν αυτού, καλό θα ήταν να έχουν στοιχειώδεις γνώσεις από τα Διακριτά Μαθηματικά, τη Λογική, τη Θεωρία Συνόλων και τη Θεωρία Γραφημάτων.

Oι φοιτητές θα κληθούν να επιλύσουν 2 πακέτα ασκήσεων που θα λειτουργούν βελτιωτικά στον συνολικό βαθμό που θα επιτύχουν στο μάθημα (1.5 μονάδα το κάθε πακέτο για τους προπτυχιακούς και 1 μονάδα το κάθε πακέτο για τους μεταπτυχιακούς). Οι παρουσιάσεις αυτές θα γίνουν τις ώρες διεξαγωγής των διαλέξεων εφόσον ο χρόνος το επιτρέπει, ή σε κάποιο έξτρα δίωρο.


Τελικός βαθμός = min{βαθμός εξέτασης+βαθμός ασκήσεων, 10} εφόσον ο βαθμός της εξέτασης είναι προβιβάσιμος.

• Michael Sipser, Εισαγωγή στην Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης (Κωδικός βιβλίου στον Εύδοξο: 86195794)
• Harry R. Lewis, Χρήστος Παπαδημητρίου: Στοιχεία Θεωρίας Υπολογισμού, Εκδόσεις Κριτική (Κωδικός Βιβλίου στον Εύδοξο: 11776)

• Christos H. Papadimitriou: Computational Complexity, Pearson publications
• Michael R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Company
• Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press
• John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman: Introduction to automata theory, languages, and computation, Addison-Wesley