Θεωρία Υπολογισμού και Πολυπλοκότητα — Σεπτέμβριος 2024 (Υπολογιστική Πολυπλοκότητα)

Μεταγραφή από τις σελίδες θεμάτων του κειμένου του PDF «CC_Exams-13-09-2024.pdf» (πλήρες text layer).

CC_Exams-13-09-2024.pdf (σελ. 1,2)

ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ « ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ » 13/09/2024

Διάρκεια Εξέτασης (2 ώρες και 30 λεπτά)

1. (2) Έστω η αιτιοκρατική ΤΜ 𝛭 όπου 𝛴= {0,1} και 𝛤= {0,1, ⌴} με τη διπλανή συνάρτηση μετάβασης. Έστω ότι η αρχική κατάσταση είναι η 𝑞0, η κατάσταση απόρριψης είναι η 𝑞𝑟 και η κατάσταση αποδοχής είναι η 𝑞𝛼. Είναι η 𝛭 διαγνώστης; Ποια είναι η γλώσσα που αναγνωρίζει η 𝛭; Αιτιολογήστε τις απαντήσεις σας.

⌴ →A
qα
qr q 1
⌴ →A
0 →Δ 0 →Δ
1,⌴ →A
1 →Α
q0 q 2 0,1 →Δ

2. (2) Να αποδείξετε ότι το 4SAT είναι NP-πλήρες πρόβλημα, όπου το 4SAT είναι το πρόβλημα SAT με τον περιορισμό ότι κάθε φράση έχει 4 ακριβώς λεξιγράμματα. Σας προτείνεται να κάνετε αναγωγή από το 3SAT.

3. (2) Σας δίνεται η εξής γλώσσα:

𝐿𝐴𝑅𝐺𝐸𝑅𝑇𝑀 = {〈𝑀1, 𝑀2〉: 𝜂 𝛾𝜆ώ𝜎𝜎𝛼 𝐿(𝑀1) 𝜀ί𝜈𝛼𝜄 𝛾𝜈ή𝜎𝜄𝜊 𝜐𝜋𝜊𝜎ύ𝜈𝜊𝜆𝜊 𝜏𝜂𝜍 𝐿(𝑀2), 𝛿𝜂𝜆. 𝐿(𝑀1) ⊂𝐿(𝑀2)} Να συμπληρώσετε την παρακάτω απόδειξη (τα κενά κουτιά) για τη μη διαγνωσιμότητα της 𝐿𝐴𝑅𝐺𝐸𝑅𝑇𝑀. Απόδειξη: Θα δείξουμε ότι η γλώσσα 𝐿𝐴𝑅𝐺𝐸𝑅𝑇𝑀 είναι μη διαγνώσιμη κάνοντας αναγωγή από τη γνωστή μη διαγνώσιμη γλώσσα της αποδοχής 𝛢𝛵𝛭. Έστω ότι η γλώσσα 𝐿𝐴𝑅𝐺𝐸𝑅𝑇𝑀 είναι διαγνώσιμη και έστω 𝑅 μια TΜ που τη διαγιγνώσκει. Χρησιμοποιώντας την 𝑅, κατασκευάζουμε την TM 𝑆 που διαγιγνώσκει τη γλώσσα 𝛢𝛵𝛭 ως εξής:

𝑆 = για είσοδο 〈𝑀, 𝑤〉, όπου 𝑀 είναι μια TM και 𝑤 μια συμβολοσειρά:

1. Κατασκεύασε την TM 𝑀1, η οποία για είσοδο 𝑥 πάντοτε απορρίπτει.

2. Κατασκεύασε την ΤΜ 𝑀2, η οποία για είσοδο 𝑥:

3. Εκτέλεσε την ΤΜ 𝑅 με είσοδο 〈𝑀1, 𝑀2〉

4. Αν η 𝑅 αποδεχτεί, τότε αποδοχή

5. Αν η 𝑅 απορρίψει, τότε απόρριψη

Πράγματι, η 𝑆 αποτελεί διαγνώστη της γλώσσας 𝛢𝛵𝛭 αφού:

Καθώς γνωρίζουμε ότι η γλώσσα 𝛢𝛵𝛭 είναι μη διαγνώσιμη, καταλήγουμε σε άτοπο. Έτσι, έχουμε αποδείξει ότι, αντίθετα με την υπόθεσή μας, η γλώσσα 𝐿𝐴𝑅𝐺𝐸𝑅𝑇𝑀 είναι μη διαγνώσιμη.

4. (3) (α) (1) Να αποδείξετε ότι αν NP≠co-NP τότε P≠NP.

(β) (1) Να αποδείξετε ότι μία γλώσσα ανήκει στην κλάση NP αν και μόνο αν έχει πολυωνυμικό επαληθευτή. (γ) (1) Να δώσετε όσες σχέσεις γνωρίζετε που έχουν (αν περιέχονται ή είναι ίσες) των παρακάτω κλάσεων πολυπλοκότητας δεδομένου ότι 𝑃≠𝑁𝑃 : 𝑃, 𝑐𝑜−𝑃, 𝑁𝑃, 𝑐𝑜−𝑁𝑃 , 𝑁𝑃𝐶, 𝑐𝑜−𝑁𝑃𝐶, Διαγνώσιμες Γλώσσες, Συμπληρωματικά Αναγνωρίσιμες Γλώσσες, 𝛵𝛪𝛭𝛦(𝑛² ) . (Μπορείτε να χρησιμοποιήσετε και σχήμα – το πρόθεμα co σημαίνει συμπλήρωμα της κλάσης ενώ 𝑁𝑃𝐶 είναι η κλάση των 𝑁𝑃-πλήρων προβλημάτων)

5. (2) Να αναφέρετε αν κάθε μία από τις παρακάτω προτάσεις είναι Αληθής ή Ψευδής. Εφαρμόζεται αρνητική βαθμολόγηση σε αυτό το θέμα που μεταφέρεται στον τελικό βαθμό του γραπτού. (Σωστή απάντηση: +0.25 , Λάθος απάντηση: −0.25 )

• i. Αν ένα πρόβλημα μπορεί να λυθεί σε αιτιοκρατικό πολυωνυμικό χρόνο τότε μπορεί και να επαληθευτεί σε αιτιοκρατικό πολυωνυμικό χρόνο.

• ii. Το πρόβλημα του Τερματισμού είναι NP-πλήρες.

• iii. Κάθε διαγνώσιμη γλώσσα είναι συμπληρωματικά αναγνωρίσιμη.

• iv. Η γλώσσα μίας ΤΜ που τερματίζει σε κάθε είσοδο μπορεί να είναι μόνο κανονική (regular).

• v. Το συμπλήρωμα κάθε αναγνωρίσιμης γλώσσας είναι επίσης αναγνωρίσιμη.

• vi. Κάθε γλώσσα που διαγιγνώσκεται από μία ανταιτιοκρατική ΤΜ μπορεί να διαγνωσθεί επίσης και από μία αιτιοκρατική ΤΜ.

• vii. Η ΤΜ είναι ένα μοντέλο υπολογισμού που μπορεί να προσομοιώσει οποιοδήποτε άλλο ρεαλιστικό μοντέλο γνωρίζουμε μέχρι τώρα.

• viii. To 3-SAT ως NP-πλήρες χρειάζεται εκθετικό χρόνο άρα και εκθετικό χώρο.

Καλή Επιτυχία!!!

---

✖ Βρήκα λάθος στη μεταγραφή