Μάθημα : Υπολογιστική Πολυπλοκότητα

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

Στις 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, είτε την ξανασυζητάμε την Πέμπτη.

Γ. Λ.