Υπολογιστική Πολυπλοκότητα — Φεβρουάριος 2022 — Θέματα (18/2/2022)¶
Μεταγραφή της φωτογραφίας IMG_7872.jpg της εξέτασης της 18/2/2022.
IMG_7872.jpg¶
ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ «ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ» - 18/2/2022 Διάρκεια Εξέτασης (2 ώρες)
-
(2 μονάδες) Να αποδείξετε ότι για όλες τις NP-πλήρεις γλώσσες A, B, C, A ≤_p B and B ≤_p C ⇒ A ≤_p C (όπου με ≤_p αναπαριστούμε την αντίστοιχη αναγωγή πολυωνυμικού χρόνου).
-
(2 μονάδες) Μία κυκλική TM είναι μία TM με μία ταινία άπειρου μήκους προς τη μία κατεύθυνση (δεξιά – όπως δηλαδή και στις κλασσικές TM) με τη διαφορά ότι συμπεριφέρεται διαφορετικά στο αριστερότερο άκρο. Όταν η κεφαλή της ταινίας βρίσκεται στο αριστερότερο άκρο και κάνει κίνηση προς τα αριστερά, στην κυκλική TM η κεφαλή μεταφέρεται στο δεξιότερο μη κενό κελί. Να αποδείξετε ότι η κλάση γλωσσών που διαγιγνώσκονται από την κυκλική TM είναι ίδια με την κλάση γλωσσών που διαγιγνώσκονται από την κλασσική TM (δηλαδή, είναι ισοδύναμα μοντέλα).
-
(2 μονάδες) Έστω η γλώσσα A = {⟨M⟩ | η L(M) περιέχει τη λέξη "CEID"}. Να αποδείξετε ότι η A είναι μη-διαγνώσιμη (μπορείτε – αν και δεν είναι υποχρεωτικό – να κάνετε αναγωγή από το πρόβλημα της ΑΠΟΔΟΧΗΣ, σύμφωνα με το οποίο το πρόβλημα του να βρούμε αν μία λέξη w γίνεται αποδεκτή από μία Turing μηχανή M είναι μη-διαγνώσιμο).
-
(2 μονάδες – έχει αρνητική βαθμολόγηση −0,2 ανά λάθος) Να αναφέρετε αν οι παρακάτω προτάσεις είναι Σωστές (Σ) ή Λάθος (Λ) χωρίς αιτιολόγηση.
i. Έστω N μία ανταιτιοκρατική TM που τρέχει σε χρόνο t(n) και διαγιγνώσκει τη γλώσσα L. Τότε υπάρχει μία αιτιοκρατική TM, D, που σε (542)^{O(t(n))} βήματα διαγιγνώσκει τη L. ii. Η κλάση των NP-πλήρων προβλημάτων εμπεριέχεται στην κλάση των NP-δυσχερών προβλημάτων. iii. Δοθέντος ενός υπερυπολογιστή με 100TB συνολική μνήμη και ενός προγράμματος για αυτόν, μπορούμε να διαγνώσουμε αν το πρόγραμμα τερματίζει. iv. Αν SAT ∈ P τότε και co-SAT ∈ P. v. Το αλφάβητο ταινίας Γ μίας TM μπορεί να έχει το πολύ ένα σύμβολο παραπάνω από το αλφάβητο εισόδου Σ. vi. Μία TM δεν μπορεί να γράψει το σύμβολο «κενό».
-
(2 μονάδες) Έστω το πρόβλημα ΔΙΠΛΟ_SAT = {⟨φ⟩ | ο λογικός τύπος φ έχει τουλάχιστον δύο αληθοποιούς τιμοδοσίες}. Να αποδείξετε ότι το πρόβλημα ΔΙΠΛΟ_SAT είναι NP-πλήρες (Υπόδειξη: μπορείτε να κάνετε την αναγωγή από το πρόβλημα SAT που είναι NP-πλήρες).
-
(2 μονάδες) Δώστε τη σχέση (αν περιέχονται ή είναι ίσες) των παρακάτω κλάσεων πολυπλοκότητας: [δυσανάγνωστο]CE, NP, co-NP, NPC, co-NPC, NPSPACE, co-P. (Μπορείτε να την δώσετε [δυσανάγνωστο]· αρκεί να αναφέρετε τους αυστηρούς εγκλεισμούς. NPC: η κλάση των [δυσανάγνωστο].)
-
[δυσανάγνωστο, αριθμός κομμένος] [Δ]είξετε ότι αν NP ≠ co-NP τότε κανένα NP-πλήρες πρόβλημα δεν μπορεί να [δυσανάγνωστο] co-NP-πλήρες πρόβλημα δεν μπορεί να ανήκει στο NP.
[Λείπει από τη φωτογραφία: τμήμα της διατύπωσης στο δεξί άκρο της σελίδας· δυσανάγνωστο]
Καλή Επιτυχία!!!
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2022-02.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):IMG_6114.png(διαφάνεια «Θέμα (Επί Διπλώματι 2022)» με διαφορετική διατύπωση του ερωτήματος 2· δεν είναι φωτογραφία της ίδιας σελίδας και δεν μεταφέρθηκε).