Υπολογιστική Πολυπλοκότητα — 31 Αυγούστου 2022 — Ομάδα Α¶

Μεταγραφή της φωτογραφίας IMG20220831192256.jpg (Ομάδα Α, 31/08/2022).

IMG20220831192256.jpg¶

ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ «ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ» 31/08/2022 Διάρκεια Εξέτασης (2 ώρες και 30 λεπτά) – Ομάδα Α

1. (15 μονάδες)

α) (7) Έστω ότι σας δίνεται μία TM \(M\), μία είσοδος \(x\) (που βρίσκεται στην αρχή της ταινίας) και ένας φυσικός αριθμός \(k\). Ορίζουμε το εξής πρόβλημα:

\[BSC = \{\langle M, x, k\rangle : H\ TM\ M\ τερματίζει\ σε\ είσοδο\ x\ χρησιμοποιώντας\ το\ πολύ\ k\ θέσεις\ μνήμης\}\]

Είναι το \(BSC\) διαγνώσιμο; Αιτιολογήστε την απάντησή σας.

β) (8) Έστω η γλώσσα \(A = \{a^n b^n : n \geq 0\}\), που ανήκει στο \(P\). Θα δείξουμε ότι \(3SAT \leq_P A\). Η αναγωγή είναι η εξής:

\[f(\langle\varphi\rangle) = \begin{cases} aabb & \text{αν η } \varphi \text{ έχει αληθοποιό τιμοδοσία} \\ aab & \text{διαφορετικά} \end{cases}\]

όπου \(\varphi\) λογικός τύπος. Αφού \(3SAT \in NPC\), \(3SAT \leq_P A\) και \(A \in P\) συνεπάγεται ότι \(P = NP\). Να δείξετε ποιο είναι το «λάθος» σε αυτή την απόδειξη ότι \(P = NP\) εστιάζοντας στην αναγωγή.

2. (30 μονάδες)

(Α) (8) Έστω οι εξής γλώσσες:

\[2SAT = \{\langle\varphi\rangle : o\ λογικός\ τύπος\ \varphi\ σε\ 2-κανονική\ συζευκτική\ μορφή\ είναι\ αληθεύσιμος\}\]

\[KNAPSACK = \{(\langle v_1, \ldots, v_n\rangle, \langle w_1, \ldots, w_n\rangle, k, W) : \exists I \subseteq \{1, \ldots, n\}\ \text{έτσι ώστε}\ \sum_{j\in I} v_j \geq W\ \text{και}\ \sum_{j \in I} w_j \leq k\}\]

Χαρακτηρίστε ως αληθείς ή ψευδείς τις παρακάτω δηλώσεις και δώστε σύντομη αιτιολόγηση. Για τις απαντήσεις σας θεωρήστε ότι \(P \neq NP\).

α. (2) Το πρόβλημα \(2SAT\) ανήκει στην κλάση \(NP\).
β. (3) Υπάρχει αναγωγή του προβλήματος \(2SAT \leq_P KNAPSACK\).
γ. (3) Υπάρχει αναγωγή του προβλήματος \(KNAPSACK \leq_P 2SAT\).

(Β) (22) Έστω μία μηχανή και ένα σύνολο εργασιών \(\{q_1, q_2, \ldots, q_n\}\) προς εκτέλεση στη μηχανή. Κάθε εργασία \(q_i\) \((1 \leq i \leq n)\) απαιτεί χρόνο επεξεργασίας \(p_i\), έχει κέρδος \(w_i\) και έχει μία προθεσμία \(d_i\). Θα πρέπει να δρομολογήσουμε τις εργασίες στη μηχανή με τον περιορισμό ότι η μηχανή εκτελεί το πολύ μία εργασία σε κάθε χρονική στιγμή και από τη στιγμή που μία εργασία \(q_i\) ξεκινήσει να εκτελείται θα πρέπει να εκτελεσθεί για χρόνο \(p_i\). Οι εργασίες \(q_i\) που ολοκληρώνονται πριν την προθεσμία τους, μας δίνουν κέρδος \(w_i\), αλλιώς το κέρδος που αποκομίζουμε είναι \(0\). Δείξτε ότι το πρόβλημα απόφασης πρόγραμμα δρομολόγησης με συνολικό κέρδος τουλάχιστον \(W\) είναι NP-πλήρες.

Υπόδειξη: Χρησιμοποιήστε (χωρίς να είναι δεσμευτικό) αναγωγή με περιορισμό από το κατάλληλο πρόβλημα.

3. (30 μονάδες) Θα ονομάζουμε άχρηστη μία κατάσταση σε μία TM \(M\) αν για οποιαδήποτε είσοδο η \(M\) δεν διέρχεται από αυτή την κατάσταση ποτέ. Έστω το πρόβλημα καθορισμού του αν μία δοθείσα κατάσταση είναι άχρηστη.

α) (4) Να εκφράσετε τυπικά το συγκεκριμένο πρόβλημα ως γλώσσα (ονομάστε τη γλώσσα ως \(UL\) – δείτε ως παράδειγμα την εκφώνηση της άσκησης 2(Α)).
β) (15) Να αποδείξετε ότι η συγκεκριμένη γλώσσα είναι μη-διαγνώσιμη (προτείνεται – χωρίς να είναι δεσμευτικό – να χρησιμοποιήσετε για την αναγωγή τη γλώσσα \(ΚΕΝΟΤΗΤΑ_{TM} = \{\langle M\rangle : L(M) = \emptyset\}\)).
γ) (4) Η συμπληρωματική γλώσσα \(co\text{-}UL\) είναι διαγνώσιμη ή μη-διαγνώσιμη (με αιτιολόγηση);
δ) (7) Η \(UL\) είναι αναγνωρίσιμη, συμπληρωματικά αναγνωρίσιμη ή τίποτα από τα δύο (με αιτιολόγηση);

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2022-08-a.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): ap.png

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