Εισαγωγή στην παραμετρική πολυπλοκότητα, ισοδυναμίες μέτρων πολυπλοκότητας. Αλγοριθμικές τεχνικές: φραγμένα δέντρα αναζήτησης, επαναληπτική συμπίεση, άπληστος εντοπισμός, αναδρομική κατανόηση, σημαντικοί διαχωριστές, κανόνες αναγωγής, η τεχνική της ασήμαντης κορυφής. Πιθανοτικές μέθοδοι, πυρηνοποίηση, πυρηνοποίηση Turing. Δεντροπλάτος, το θεώρημα του Courcelle, δυναμικός προγραμματισμός, διδιαστατότητα, εναλλακτικές παράμετροι πλάτους, παραμετρικές αναγωγές, μετααλγοριθμικά θεωρήματα. Οι κλάσεις para-NP και XP, η W-ιεραρχία: FPT, W[1],W[2],...,W[SAT], W[P] και ορισμοί της μέσω κυκλωμάτων, λογικών τύπων και μοντέλων μηχανών Turing. Κάτω φράγματα και υπόθεση εκθετικού χρόνου, ισχυρή υπόθεση εκθετικού χρόνου, παραμετρική πολυπλοκότητα πολυωνυμικά επιλύσιμων προβλημάτων.
Τύπος
Επιλογής
Περιγραφή μαθήματος