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