Υπολογιστική Πολυπλοκότητα — Ιούνιος 2025 (12/06/2025) — Θέματα¶
Μεταγραφή της φωτογραφίας IMG_20250612_162331.jpg (ΕΞΕΤΑΣΗ 12/06/2025).
IMG_20250612_162331.jpg¶
ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ «ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ»¶
12/06/2025 Διάρκεια Εξέτασης (2 ώρες και 30 λεπτά) Όλες οι απαντήσεις θα δοθούν στην κόλλα σας και όχι στα θέματα – Τα θέματα επιστρέφονται
1. (2) Έστω η αιτιοκρατική ΤΜ \(M\) όπου \(\Sigma = \{x, y\}\) και \(\Gamma = \{x, y, \sqcup\}\) με τη διπλανή συνάρτηση μετάβασης. Έστω ότι η αρχική κατάσταση είναι η \(q_0\), η κατάσταση απόρριψης είναι η \(q_r\) και η κατάσταση αποδοχής είναι η \(q_a\). Είναι η \(M\) διαγνώστης; Ποια είναι η γλώσσα που αναγνωρίζει η \(M\); Αιτιολογήστε τις απαντήσεις σας.
[Σχήμα: Διάγραμμα καταστάσεων αιτιοκρατικής TM M με καταστάσεις \(q_0, q_1, q_2, q_r, q_a\). Μεταβάσεις: από \(q_0\) σε \(q_1\) με \(y \to \Delta\), σε \(q_r\) με \(x, \sqcup \to A\). Από \(q_1\) σε \(q_0\) με \(x \to A\), σε \(q_2\) με \(y \to \Delta\), σε \(q_r\) με \(\sqcup \to A\). Από \(q_2\) προς τον εαυτό της με \(x, y \to \Delta\), και προς \(q_a\) με \(\sqcup \to A\).]
2. (2) Να αποδείξετε ότι το πρόβλημα \(\text{ΑΝΕΞΑΡΤΗΤΟ\_ΣΥΝ} = \{\langle G, k \rangle \mid \text{το } G \text{ είναι ακατεύθυντο γράφημα και έχει ανεξάρτητο σύνολο μεγέθους } k\}\) είναι NP-πλήρες. Ένα ανεξάρτητο σύνολο σε ένα γράφημα είναι ένα σύνολο κορυφών έτσι ώστε κανένα ζευγάρι κορυφών να μην είναι γειτονικές. (Υπόδειξη: μία πιθανή αναγωγή είναι από το πρόβλημα της ΚΛΙΚΑΣ – κλίκα μεγέθους \(k\) σε ένα γράφημα είναι ένα υπογράφημα με \(k\) κορυφές έτσι ώστε να υπάρχουν όλες οι δυνατές ακμές μεταξύ τους.)
3. (2) Να αποδείξετε ότι η γλώσσα \(A = \{\langle M \rangle \mid L(M) = \Sigma^*\}\) είναι μη διαγνώσιμη. Είναι αναγνωρίσιμη ή συμπληρωματικά αναγνωρίσιμη; (Για την αναγωγή χρησιμοποιείστε τη γλώσσα \(\text{ΑΠΟΔΟΧΗ}_{\text{TM}}\)).
4. (2) (α) (1) Έστω μία γλώσσα \(L\) της οποίας η μεγαλύτερη συμβολοσειρά που περιέχει έχει μήκος \(m > 0\). Αποδείξτε ότι η γλώσσα αυτή είναι διαγνώσιμη (Υπόδειξη: λόγω της ιδιότητας αυτής η γλώσσα \(L\) είναι πεπερασμένη).
(β) (1) Να δώσετε όσες σχέσεις γνωρίζετε που έχουν (αν περιέχονται ή είναι ίσες) οι παρακάτω κλάσεις πολυπλοκότητας/υπολογισιμότητας δεδομένου ότι \(P \neq NP\): \(P\), Διαγνώσιμες Γλώσσες, \(\text{co}-P\), \(NP\), \(\text{co}-NP\), \(NPC\), \(\text{co}-NPC\), Μη – Διαγνώσιμες Γλώσσες, \(TIME(n^3)\). (Μπορείτε να χρησιμοποιήσετε και σχήμα – το πρόθεμα co σημαίνει συμπλήρωμα της κλάσης ενώ \(NPC\) είναι η κλάση των \(NP\)-πλήρων προβλημάτων)
5. (2) Να αναφέρετε αν κάθε μία από τις παρακάτω προτάσεις είναι Αληθής ή Ψευδής.
Εφαρμόζεται αρνητική βαθμολόγηση σε αυτό το θέμα που μεταφέρεται στον τελικό βαθμό του γραπτού. (Σωστή απάντηση: +0.2, Λάθος απάντηση: -0.1)
i. Το αλφάβητο ταινίας \(\Gamma\) μπορεί να συμπίπτει με το αλφάβητο εισόδου \(\Sigma\).
ii. Το 2-SAT ανήκει στο \(P\).
iii. Αν το \(B\) είναι NP-πλήρες, \(C \in NP\), και \(B \le_P C\), τότε και το \(C\) είναι NP-πλήρες.
iv. Αν \(\text{ΚΛΙΚΑ} \in P\) τότε και \(\text{co-ΚΛΙΚΑ} \in P\).
v. Αν ένα NP-δυσχερές πρόβλημα λυνόταν σε πολυωνυμικό χρόνο τότε \(P=NP\).
vi. Η θέση των Church-Turing έχει αποδειχτεί.
vii. Δεν γνωρίζουμε αν η κλάση NP είναι κλειστή ως προς την πράξη του συμπληρώματος.
viii. Ένα γραμμικώς φραγμένο αυτόματο διαγιγνώσκει ακριβώς τις ίδιες γλώσσες με μία TM.
ix. Η κλάση των διαγνώσιμων γλωσσών δεν είναι κλειστή ως προς την πράξη της ένωσης.
x. Υπάρχουν αριθμοί υπολογίσιμοι που δεν είναι περιγράψιμοι.
Καλή Επιτυχία!!!
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2025-06.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):IMG_3813.jpg