Θεωρία Υπολογισμού και Πολυπλοκότητα

Σύντομη περιγραφή

Το μάθημα «Υπολογιστική Πολυπλοκότητα» εξετάζει τι μπορεί και τι δεν μπορεί να υπολογιστεί, αλλά και με τι κόστος (χρόνος/χώρος). Ξεκινά με μηχανές Turing και βασικές έννοιες υπολογισιμότητας (διαγνώσιμες/μη διαγνώσιμες γλώσσες, αποδείξεις μη-διαγνωσιμότητας) και προχωρά στην πολυπλοκότητα: χρονική πολυπλοκότητα, κλάσεις P, NP, coNP και το ερώτημα P vs NP. Έμφαση δίνεται στις αναγωγές και στην NP-πληρότητα, δηλαδή στο πώς δείχνουμε ότι πολλά πρακτικά προβλήματα είναι “δύσκολα” όχι επειδή δεν λύνονται, αλλά επειδή απαιτούν απαγορευτικούς πόρους.

Tip – Τι χρειάζεται προσοχή

• Αναγωγές (κατεύθυνση & “τι αποδεικνύουν”): σωστή επιλογή προβλήματος-πηγής και σωστός προσανατολισμός, γιατί από ένα λάθος βήμα “γκρεμίζεται” όλη η απόδειξη.
• Ορισμοί κλάσεων & μοντέλων: καθαρή διάκριση αποφασισιμότητας vs πολυπλοκότητας και χρόνου vs χώρου, καθώς και ακρίβεια σε P/NP/coNP και έννοιες πιστοποιητή/μη-ντετερμινισμού

Τι κερδίζεις από αυτό το μάθημα

• Σαφές κριτήριο εφικτότητας: δυνατότητα να αναγνωρίζεται πότε ένα πρόβλημα είναι ρεαλιστικά επιλύσιμο και πότε χρειάζεται προσεγγίσεις, ευρετικές ή αλλαγή μοντελοποίησης.
• Ισχυρή θεωρητική “γλώσσα” για αλγορίθμους: ικανότητα να τεκμηριώνεται αυστηρά η δυσκολία ενός προβλήματος (μέσω αναγωγών/NP-πληρότητας) και να διαβάζεται πιο ώριμα βιβλιογραφία/θεωρία αλγορίθμων.