Ανακοινώσεις μαθήματος Υπολογιστική Πολυπλοκότητα

Ύλη εξετάσεων ακαδημαϊκού έτους 2025-26

Tue, 05 May 2026 13:58:19 +0300

Καλησπέρα σε όλα,

Η ύλη του μαθήματος για τις εξετάσεις αποτελείται από τα κεφάλαια 7 και 8 του βιβλίου Sipser. Συγκεκριμένα, για κόσμο που μελετάει από άλλες πηγές:

1) Ασυμπτωτικός συμβολισμός (Big-O notation). Όχι εξειδικευμένα πράγματα.

2) Ντετερμινιστικές και μη ντετερμινιστικές μηχανές Turing. Πολυταινιακές μηχανές. Όχι αποδείξεις ισοδυναμίας μοντέλων, κυρίως να ξέρετε τι είναι και να μπορείτε να χειριστείτε τέτοιες μηχανές.

3) Κλάσεις χρονικής πολυπλοκότητας P, NP, EXP. Συμπληρωματικές κλάσεις (πχ coNP).

4) Αναγωγές πολυωνυμικού χρόνου. NP-πληρότητα. NP-πλήρη προβλήματα σχετιζόμενα με λογικούς τύπους, γραφήματα και σύνολα ακεραίων. Όχι θεώρημα Cook-Levin.

5) Κλάσεις χωρικής πολυπλοκότητας PSPACE, L, NL. Θεώρημα Savitch.

6) PSPACE πληρότητα, NL πληρότητα και αντίστοιχα προβλήματα. NL=coNL.

Αν υπάρξει χρόνος να καλυφθούν περισσότερα πράγματα από αυτά στο μάθημα (μάλλον δύσκολο), τα όποια έξτρα πράγματα δούμε δεν θα περιλαμβάνονται στην εξεταστέα ύλη.

Γ.Λ.

Αναβολη διαλεξης 26/3

Wed, 25 Mar 2026 20:50:03 +0300

Καλησπερα σε ολα,

Λογω ζητηματος υγειας, η αυριανη διαλεξη αναβαλλεται. Θα συζητησουμε για αναπληρωση την επομενη εβδομαδα.

Γ.

Για το μάθημα στις 5/3

Sun, 08 Mar 2026 05:54:04 +0300

Καλημέρα σε όλα,

Στις 5/3 αναφέραμε κάποια παραδείγματα αλγοριθμικών προβλημάτων (πολλαπλασιασμός ακεραίων, εύρεση μεγίστου σε πίνακα, REACHABILITY, TSP) και ο τρόπος με τον οποίο μας ενδιαφέρει να τα μελετήσουμε. Στην συνέχεια μιλήσαμε για γλώσσες, ορίσαμε τις Μηχανές Turing και κάναμε ένα παράδειγμα στην γλώσσα L={0^n 1^n | n φυσικός}.

Τα διάφορα που είπαμε πάρθηκαν από τα παρακάτω:

1) Papadimitriou Christos, "Computational Complexity", Addison-Wesley Publishing Company, Inc., 1994 [Sections 1.1, 1.3]

2) Sanjeev Arora, Boaz Barak, "Computational Complexity, A Modern Approach", Cambridge University Press, 2007 [Chapter 0]

3) Δημήτρης Ζώρος, "(Πρόχειρες) σημειώσεις στη ΘΕΩΡΙΑ ΑΝΑΔΡΟΜΗΣ" [παρ. 0.2]

4) Βιβλίο Sipser. [Κ. 3.1]

Για την Μ.Τ. που κάναμε, ίσως είχε λάθος όπως μου υπέδειξε συμφοιτητής σας. Δεν είμαι σίγουρος πλέον γι αυτό (δεν μπορώ να αναπαράξω το λάθος δλδ), αλλά σε κάθε περίπτωση, η προτινόμενη Μ.Τ. που αποφασίζει την γλώσσα L = {w = 0^n 1^n | n στο n}, είναι η M =(Q,Σ,Γ,δ,q0,qa,qf) όπου:

Q={q0,q1,qb,qa,qf}

Σ={0,1}, Γ={0,1,|>, _ , 0',1'}, |> αρχή ταινίας, _ κενό κελί ταινίας

q0 αρχική κατάσταση, qa αποδοχής, qf απόρριψης

και δ:QxΓ --> QxΓx{A,Δ}, με

δ(q0,0)=(q1,0',Δ), δ(q0,1)=(qf,1,Δ), δ(q0,0')=(q0,0',Δ), δ(q0,1')=(q0,1',Δ), δ(q0,_)=(qy,_,Δ)

δ(q1,0)=(q1,0,Δ), δ(q1,1)=(qb,1',A), δ(q1,1')=(q1,1',Δ), δ(q1,_)=(qf,_,Δ)

δ(qb,0)=(qb,0,A), δ(qb,0')=(qb,0',A), δ(qb,1')=(qb,1',A), δ(qb,|>)=(q0,|>,Δ)

Για όλα τα inputs που δεν όρισα την δ, σημαίνει ότι δεν προκύπτουν ποτέ στην λειτουργία της μηχανής οπότε δεν μας ενδιαφέρουν. Μπορούμε είτε να αφήσουμε την δ να είναι μερική συνάρτηση, μέχρι να ορίσουμε ότι βλακεία να ναι.

Έστω λέξη 0^n 1^m, με n>m. Τότε, όταν σημαδευτεί το m+1-οστό 0, η Μ.Τ. θα μπει στην κατάσταση q1 και η κεφαλή θα κινείται δεξιά, βρίσκοντας στο διάβα της μόνον 0 και 1'. Κάποαι στιγμή θα δει το πρώτο _, κι επειδή είναι στην q1, θα περάσει στην κατάσταση απόρριψης qf.

Έστω λέξη 0^n 1^m, με n<m. Τότε, όταν σημαδευτεί τo n-οστό 1, η Μ.Τ. θα μπει στην κατάσταση qb, θα γυρίσει στην αρχή της ταινίας, θα επανέλθει στην κατάσταση q0, και μετά η κεφαλή θα κινείται δεξιά, βρίσκοντας στο διάβα της μόνον 0' και 1'. Κάποαι στιγμή θα δει το πρώτο 1, κι επειδή είναι στην q0, θα περάσει στην κατάσταση απόρριψης qf.

Δείτε την, σκεφτείτε την, και αν διαφωνείτε είτε γράψτε μου e-mail, είτε την ξανασυζητάμε την Πέμπτη.

Γ. Λ.

Έναρξη μαθημάτων 5/3

Thu, 26 Feb 2026 11:40:12 +0300

Λόγω του σημερινού "μπλεξίματος" (δεν κρίνω, απλώς δεν έχω λάβει κάποια πιο κανονική ενημέρωση για να το ονομάσω αλλιώς), οι διαλέξεις στην Υπολογιστική Πολυπλοκότητα θα ξεκινήσουν στις 5/3.

Γ. Λ.

Τελικοί βαθμοί εξέτασης Φεβρουαρίου '26

Mon, 16 Feb 2026 03:04:53 +0300

Καλησπέρα σε όλα,

Οι τελικοί βαθμοί της εξέτασης του Φεβρουαρίου '26, όπως θα κατατεθούν στο my-uni, βρίσκονται στα έγγραφα.

Γιάννης