Υπολογιστική Πολυπλοκότητα — Σεπτέμβριος 2024 — Θέματα¶
Μεταγραφή της φωτογραφίας IMG_20240913_091626.jpg (θέματα Σεπτεμβρίου 2024).
IMG_20240913_091626.jpg¶
[φωτογραφία σελίδας θέματος· το επάνω μέρος της σελίδας κόβεται, η κεφαλίδα δεν φαίνεται· το κείμενο στο κάτω μέρος είναι αχνό]
1. (2) Έστω η αιτιοκρατική TM M όπου Σ = {0,1} και Γ = {0,1,⊔} με τη διπλανή συνάρτηση μετάβασης. Έστω ότι η αρχική κατάσταση είναι η q₀, η κατάσταση απόρριψης είναι η q_r και η κατάσταση αποδοχής είναι η q_α. Είναι η M διαγνώστης; Ποια είναι η γλώσσα που αναγνωρίζει η M; Αιτιολογήστε τις απαντήσεις σας.
[Σχήμα: διάγραμμα μεταβάσεων με καταστάσεις q₀, q₁, q₂, q_r, q_α· ετικέτες που διακρίνονται: 1,⊔→A, ⊔→A, 0→Δ (δύο φορές), 1→A, 0,1→Δ· οι ακριβείς συνδέσεις δεν είναι όλες καθαρές]
2. (2) Να αποδείξετε ότι το 4SAT είναι NP-πλήρες πρόβλημα, όπου το 4SAT είναι το πρόβλημα SAT με τον περιορισμό ότι κάθε φράση έχει 4 ακριβώς λεξιγράμματα. Σας προτείνεται να κάνετε αναγωγή από το 3SAT.
3. (2) Σας δίνεται η εξής γλώσσα: \(LARGER_{TM} = \{\langle M_1, M_2\rangle : \eta\ \gamma\lambda\omega\sigma\sigma\alpha\ L(M_1) \text{ είναι γνήσιο υποσύνολο της } L(M_2),\ \delta\eta\lambda.\ L(M_1) \subset L(M_2)\}\). Να συμπληρώσετε την παρακάτω απόδειξη (τα κενά κουτιά) για τη μη διαγνωσιμότητα της \(LARGER_{TM}\).
Απόδειξη: Θα δείξουμε ότι η γλώσσα \(LARGER_{TM}\) είναι μη διαγνώσιμη κάνοντας αναγωγή από τη γνωστή μη διαγνώσιμη γλώσσα \(A_{TM}\). Έστω ότι η γλώσσα \(LARGER_{TM}\) είναι διαγνώσιμη και έστω R μια TM που τη διαγνώσκει. Χρησιμοποιώντας την R, κατασκευάζουμε την TM S που διαγνώσκει τη γλώσσα \(A_{TM}\) ως εξής:
S = για είσοδο \(\langle M, w\rangle\), όπου M είναι μια TM και w μια συμβολοσειρά:
- Κατασκεύασε την TM \(M_1\), η οποία για είσοδο x πάντοτε απορρίπτει.
- Κατασκεύασε την TM \(M_2\), η οποία για είσοδο x: [κενό πλαίσιο συμπλήρωσης]
- Εκτέλεσε την TM R με είσοδο \(\langle M_1, M_2\rangle\)
- Αν η R αποδεχτεί, τότε αποδοχή
- Αν η R απορρίψει, τότε απόρριψη
Πράγματι, η S αποτελεί διαγνώστη της γλώσσας \(A_{TM}\) αφού: [κενό πλαίσιο συμπλήρωσης]
Καθώς γνωρίζουμε ότι η γλώσσα \(A_{TM}\) είναι μη διαγνώσιμη, καταλήγουμε σε άτοπο. Έτσι, έχουμε αποδείξει ότι, αντίθετα με την υπόθεσή μας, η γλώσσα \(LARGER_{TM}\) είναι μη διαγνώσιμη.
4. (3) α) (1) Να αποδείξετε ότι αν \(NP \neq co\text{-}NP\) τότε \(P \neq NP\).
β) (1) Να αποδείξετε ότι μία γλώσσα ανήκει στην κλάση NP αν και μόνο αν έχει πολυωνυμικό επαληθευτή.
γ) (1) Να δώσετε όσες σχέσεις γνωρίζετε που έχουν (αν περιέχονται ή είναι ίσες) των παρακάτω κλάσεων πολυπλοκότητας δεδομένου ότι \(P \neq NP\): \(P\), \(co\text{-}P\), \(NP\), \(co\text{-}NP\), \(NPC\), \(co\text{-}NP\) [Λείπει από τη φωτογραφία: το τέλος της γραμμής κόβεται από το άκρο της φωτογραφίας], Διαγνώσιμες Γλώσσες, Συμπληρωματικά Αναγνωρίσιμες Γλώσσες, \(TIME(n^2)\). (Μπορείτε χρησιμοποιήσετε και σχήμα – το πρόθεμα co σημαίνει συμπλήρωμα της κλάσης ενώ NPC είναι η κλάση των NP-πλήρων προβλημάτων)
5. (2) Να αναφέρετε αν κάθε μία από τις παρακάτω προτάσεις είναι Αληθής ή Ψευδής. Εφαρμόζεται αρνητική βαθμολόγηση σε αυτό το θέμα που μεταφέρεται στον τελικό βαθμό του γραπτού. (Σωστή απάντηση: +0.25, Λάθος απάντηση: −0.25)
i. Αν ένα πρόβλημα μπορεί να λυθεί σε αιτιοκρατικό πολυωνυμικό χρόνο τότε μπορεί και επαληθευτεί σε αιτιοκρατικό πολυωνυμικό χρόνο.
ii. Το πρόβλημα του Τερματισμού είναι NP-πλήρες.