Υπολογιστική Πολυπλοκότητα — Ιούνιος 2026 (09/06/2026) — Θέματα¶
Μεταγραφή της φωτογραφίας 2026.jpg (ΕΞΕΤΑΣΗ 09/06/2026).
2026.jpg¶
[το άνω μέρος της κεφαλίδας κόβεται· φαίνεται «ΣΤΟ ΜΑΘΗΜΑ «ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ»»]
ΣΤΟ ΜΑΘΗΜΑ «ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ» 09/06/2026 – Διάρκεια Εξέτασης (2 ώρες και 30 λεπτά) Όλες οι απαντήσεις θα δοθούν στην κόλλα σας και όχι στα θέματα
1. (2) Έστω η αιτιοκρατική ΤΜ M όπου Σ = {α} και Γ = {α, ⊔} με τη διπλανή συνάρτηση μετάβασης. Έστω ότι η αρχική κατάσταση είναι η q₀, η κατάσταση απόρριψης είναι η q_r και η κατάσταση αποδοχής είναι η q_α. Είναι η M διαγνώστης; Ποια είναι η γλώσσα που αναγνωρίζει η M; Αιτιολογήστε τις απαντήσεις σας.
[Σχήμα: διάγραμμα μεταβάσεων με καταστάσεις q₀, q₁, q₂, q_r, q_α· ετικέτες που διακρίνονται: α→Δ (δύο φορές), ⊔→A (δύο φορές), ⊔→α,A· η ακριβής αντιστοίχιση ακμών σε καταστάσεις είναι εν μέρει δυσανάγνωστη]
2. (2) α) (1,5) Για κάθε σταθερά k, στο πρόβλημα του k-χρωματισμού μας δίνεται ένα ακατεύθυντο γράφημα του οποίου οι κορυφές θα πρέπει να χρωματισθούν με το πολύ k χρώματα έτσι ώστε κανένα ζευγάρι γειτονικών κορυφών να μην έχει ίδιο χρώμα. Έστω ότι γνωρίζετε ότι το πρόβλημα του 2-χρωματισμού ανήκει στο P ενώ το πρόβλημα του 3-χρωματισμού είναι NP-πλήρες. Να δείξετε ότι το πρόβλημα του 4-χρωματισμού είναι και αυτό NP-πλήρες με αναγωγή από το πρόβλημα του 3-χρωματισμού.
β) (0.5) Το πρόβλημα του k-χρωματισμού, για k≥3, είναι NP-πλήρες ή υπάρχει κάποιο μεγάλο k για το οποίο το πρόβλημα λύνεται σε πολυωνυμικό χρόνο (αιτιολογήστε διαισθητικά);
3. (2) Έστω η εξής γλώσσα: \(E_{TM} = \{\langle M\rangle : \eta\ M \text{ είναι TM και } \varepsilon \in L(M)\}\), όπου \(\varepsilon\) η κενή λέξη. Να αποδείξετε με αλγοριθμική αναγωγή ότι η γλώσσα \(E_{TM}\) είναι μη-διαγνώσιμη. Για την αναγωγή χρησιμοποιήστε τη μη-διαγνώσιμη γλώσσα της αποδοχής \(A_{TM} = \{\langle M,w\rangle : \eta\ M \text{ είναι TM } w \in L(M)\}\).
4. (2) α) (1) Να αποδείξετε ότι η κλάση P είναι κλειστή ως προς την πράξη του συμπληρώματος.
β) (1) Να δώσετε με σχήμα όσες σχέσεις γνωρίζετε που έχουν (αν περιέχονται ή είναι ίσες) οι παρακάτω κλάσεις πολυπλοκότητας δεδομένου ότι \(P \neq NP\): \(P\), \(TIME(n)\), Διαγνώσιμες Γλώσσες, \(co-P\), \(NP\), \(co-NP\), \(NPC\), \(TIME(n^3)^1\).
5. (2) Να αναφέρετε αν κάθε μία από τις παρακάτω προτάσεις είναι Αληθής (Α) ή Ψευδής (Ψ). Εφαρμόζεται αρνητική βαθμολόγηση σε αυτό το θέμα που μεταφέρεται στον τελικό βαθμό του γραπτού. (Σωστή απάντηση: +0.2, Λάθος απάντηση: −0.2)
i. Μια ανταιτιοκρατική Turing Μηχανή (TM) μπορεί να λύσει περισσότερα προβλήματα από μια αιτιοκρατική TM.
ii. Μια γλώσσα L είναι μη-διαγνώσιμη εάν υπάρχει αναγωγή από την L στο πρόβλημα Τερματισμού.
iii. Αν \(P = NP\) τότε κάθε πρόβλημα στην κλάση NPC μπορεί να λυθεί σε πολυωνυμικό χρόνο με μια αιτιοκρατική TM.
iv. Η κλάση των NP-δυσχερών προβλημάτων εμπεριέχει την κλάση NPC.
v. Αφού το \(2SAT \in P\) τότε και το \(co\text{-}2SAT \in P\).
vi. Το αλφάβητο ταινίας Γ είναι υπερσύνολο του αλφάβητου εισόδου Σ.
vii. Αν \(A \leq_m B\) και η A είναι αναγνωρίσιμη τότε και η B είναι αναγνωρίσιμη.
viii. Δοθέντος ενός Η/Υ με 100TB συνολική μνήμη και ενός προγράμματος για αυτόν τον Η/Υ, δεν μπορούμε να διαγνώσουμε αν το πρόγραμμα τερματίζει.
ix. Το θεώρημα των Cook-Levin αναφέρει ότι οποιοσδήποτε αλγόριθμος μπορεί να αναπαρασταθεί από μία TM.
x. Υπάρχουν αριθμοί υπολογίσιμοι που δεν είναι περιγράψιμοι.
Καλή Επιτυχία!!!
Υποσημείωση: Το πρόβλημα co σημαίνει συμπλήρωμα της κλάσης ενώ NPC είναι η κλάση των NP-πλήρων προβλημάτων.