Computational Complexity

Type
Elective Required
Group
A
Course Description

Ορισμός κλάσεων πολυπλοκότητας με βάση τις ακόλουθες παραμέτρους: α) Το υπολογιστικό μοντέλο (προγράμματα σε γλώσσα υψηλής βαθμίδος, μηχανές Turing κτλ.), β) Τον τρόπο υπολογισμού (ντετερμινιστικό, μη ντετερμινιστικό, πιθανοτικό κτλ.), γ) Τον περιορισμό των πόρων (πολυωνυμικός χρόνος, λογαριθμικός χώρος, σταθερός αριθμός επεξεργαστών, κτλ.). Μελέτη κλάσεων πολυπλοκότητας και των μεταξύ τους σχέσεων. Σχέσεις μεταξύ κλάσεων πολυπλοκότητας. Ιεραρχίες, αναγωγές και πληρότητα, ΝΡ - πλήρη προβλήματα, Co-NP και κλάσεις συναρτήσεων. Πιθανοτικοί υπολογισμοί και πολυπλοκότητα κυκλωμάτων, κρυπτογραφία, μονόδρομες συναρτήσεις. Πρωτόκολλα, προσεγγισιμότητα και μη προσεγγισιμότητα, P vs. NP. Ισομορφισμός, μαντεία, μονότονα κυκλώματα, παράλληλοι υπολογισμοί. Κλάσεις NC και RNC, λογαριθμικός χώρος, κλάση L. Προσεγγιστικοί αλγόριθμοι. Η πολυωνυμική ιεραρχία. Προβλήματα βελτιστοποίησης, μετρητικές κλάσεις, η κλάση #P. Πολυωνυμικός χώρος, PSPACE. Παίγνια και διαλογικά πρωτόκολλα, εκθετικός χρόνος κ.α..

Name Year Semester Taught by
Computational Complexity 2022-2023 Fall Archontia C. Giannopoulou
Computational Complexity 2021-2022 Fall Archontia C. Giannopoulou
Computational Complexity 2020-2021 Fall Archontia C. Giannopoulou, Aris Pagourtzis, Stathis Zachos
Computational Complexity 2019-2020 Fall Archontia C. Giannopoulou, Aris Pagourtzis, Stathis Zachos
Computational Complexity 2018-2019 Fall Aris Pagourtzis, Stathis Zachos
Computational Complexity 2018-2019 Spring Dimitris Zoros
Computational Complexity 2017-2018 Fall Stathis Zachos, Aris Pagourtzis
Computational Complexity 2016-2017 Fall Stathis Zachos, Aris Pagourtzis