Θεωρία Υπολογισμού και Πολυπλοκότητα — Ιούνιος 2025 (Υπολογιστική Πολυπλοκότητα, 12/6)

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

CC_Exams-12-06-2025.pdf (σελ. 1)

ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ « ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ » 12/06/2025

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

Όλες οι απαντήσεις θα δοθούν στην κόλλα σας και όχι στα θέματα – Τα θέματα επιστρέφονται

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

2. (2) Να αποδείξετε ότι το πρόβλημα ΑΝΕΞΑΡΤΗΤΟ_ΣΥΝ ={  G,k  | το G είναι ακατεύθυντο γράφημα και έχει ανεξάρτητο σύνολο μεγέθους k } είναι NP-πλήρες. Ένα ανεξάρτητο σύνολο σε ένα γράφημα είναι ένα σύνολο κορυφών έτσι ώστε κανένα ζευγάρι κορυφών να μην είναι γειτονικές. (Υπόδειξη: μία πιθανή αναγωγή είναι από το πρόβλημα της ΚΛΙΚΑΣ – κλίκα μεγέθους k σε ένα γράφημα είναι ένα υπογράφημα με k κορυφές έτσι ώστε να υπάρχουν όλες οι δυνατές ακμές μεταξύ τους.)

3. (2) Να αποδείξετε ότι η γλώσσα 𝛬= {〈𝑀〉| 𝐿(𝛭) = 𝛴^∗ } είναι μη διαγνώσιμη. Είναι αναγνωρίσιμη ή συμπληρωματικά αναγνωρίσιμη; (Για την αναγωγή χρησιμοποιείστε τη γλώσσα ΑΠΟΔΟΧΗΤΜ).

4. (2) (α) (1) Έστω μία γλώσσα L της οποίας η μεγαλύτερη συμβολοσειρά που περιέχει έχει μήκος m > 0. Αποδείξτε ότι η γλώσσα αυτή είναι διαγνώσιμη (Υπόδειξη: λόγω της ιδιότητας αυτής η γλώσσα L είναι πεπερασμένη).

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

5. (2) Να αναφέρετε αν κάθε μία από τις παρακάτω προτάσεις είναι Αληθής ή Ψευδής.

Εφαρμόζεται αρνητική βαθμολόγηση σε αυτό το θέμα που μεταφέρεται στον τελικό βαθμό του γραπτού. ( Σωστή απάντηση: +0.2 , Λάθος απάντηση: −0.1)

• i. Το αλφάβητο ταινίας Γ μπορεί να συμπίπτει με το αλφάβητο εισόδου Σ.

• ii. To 2-SAT ανήκει στο P.

• iii. Αν το B είναι NP-πλήρες, C ∈ NP , και B ≤P C , τότε και το C είναι NP-πλήρες.

• iv. Αν ΚΛΙΚΑ  P τότε και co-ΚΛΙΚΑ  P.

• v. Αν ένα NP-δυσχερές πρόβλημα λυνόταν σε πολυωνυμικό χρόνο τότε P=NP.

• vi. Η θέση των Church-Turing έχει αποδειχτεί.

• vii. Δεν γνωρίζουμε αν η κλάση NP είναι κλειστή ως προς την πράξη του συμπληρώματος.

• viii. Ένα γραμμικώς φραγμένο αυτόματο διαγιγνώσκει ακριβώς τις ίδιες γλώσσες με μία ΤΜ.

• ix. Η κλάση των διαγνώσιμων γλωσσών δεν είναι κλειστή ως προς την πράξη της ένωσης.

• x. Υπάρχουν αριθμοί υπολογίσιμοι που δεν είναι περιγράψιμοι.

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

---

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