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

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

CC_Exams-12-9-2023.pdf (σελ. 1,2)

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

1. (30) (A) (8) Αποδείξτε ότι αν ένα πρόβλημα 𝐴 είναι NP-πλήρες τότε και το 𝑐𝑜𝐴 (συμπλήρωμα του 𝐴) είναι coNPπλήρες.

(B) (22) Ο Κωστίκας είναι ένας διάσημος διαρρήκτης και έβαλε στοίχημα με το φίλο του Γιωρίκα, που είναι ιδιοκτήτης κοσμηματοπωλείου, ότι μπορεί να κλέψει κοσμήματα συνολικής αξίας τουλάχιστον 𝑋 (αλλιώς δεν θα είχε νόημα να κάνει τη διάρρηξη), σε μία τσάντα που χωρά κοσμήματα βάρους το πολύ 𝑊 (αλλιώς θα σκιστεί η τσάντα και δεν θα μπορεί να τα κουβαλήσει) μέσα σε το πολύ χρόνο 𝑇 (διαφορετικά η αστυνομία θα τον πιάσει). Ο Γιωρίκας, λίγο πριν ξεκινήσει η διάρρηξη, δίνει τις εξής πληροφορίες στον Κωστίκα: για κάθε κόσμημα 𝑖 από τα 𝛮 κοσμήματα συνολικά, του δίνει την τιμή του 𝑥𝑖 καθώς και το βάρος του 𝑤𝑖. Επιπλέον, τον ενημερώνει ότι κάθε κόσμημα 𝑖 είναι μέσα σε κλειδωμένη διάφανη θήκη που απαιτεί χρόνο 𝑡𝑖 για να ξεκλειδώσει. Επομένως, ο Κωστίκας είναι αντιμέτωπος με το εξής πρόβλημα απόφασης που το ονομάζουμε ΔΙΑΡΡΗΞΗ. Υπάρχει υποσύνολο 𝑠⊆{1,2, … , 𝑁} κοσμημάτων έτσι ώστε: η συνολική τους τιμή να είναι ≥𝑋, το συνολικό τους βάρος να είναι ≤𝐵 και ο συνολικός χρόνος ξεκλειδώματος να είναι ≤𝑇 (άθροισμα τιμών, βαρών και χρόνων αντίστοιχα).

1) (15) Να αποδείξετε ότι το πρόβλημα ΔΙΑΡΡΗΞΗ είναι NP-πλήρες και άρα ο Κωστίκας μάλλον θα δυσκολευτεί να επιλέξει τα κατάλληλα κοσμήματα που να ικανοποιούν τους περιορισμούς.

2) (7) Ο Γιωρίκας ισχυρίζεται ότι αποκλείεται ο Κωστίκας να βρει σύνολο κοσμημάτων που να ικανοποιεί ταυτόχρονα όλους τους περιορισμούς (για συγκεκριμένες τιμές, βάρη και χρόνους). Να εξηγήσετε γιατί είναι υπολογιστικά ανέφικτο γενικά για τον Γιωρίκα να αποδείξει τον ισχυρισμό του στον Κωστίκα δεδομένου ότι 𝑁𝑃≠𝑐𝑜𝑁𝑃.

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

3. (30) Έστω η εξής γλώσσα: 𝛸𝑇𝑀 = {〈𝛭〉: 𝜂 𝛭 𝜀ί𝜈𝛼𝜄 𝛵𝛭 𝜅𝛼𝜄 𝜂 𝜆έ𝜉𝜂 001 ∈𝐿(𝑀)} για αλφάβητο εισόδου 𝛴= {0,1}. Σας ζητούνται τα εξής:

1. (15) Να αποδείξετε με αλγοριθμική αναγωγή ότι η γλώσσα 𝑋𝑇𝑀 είναι μη-διαγνώσιμη. Για την αναγωγή χρησιμοποιήστε τη μη-διαγνώσιμη γλώσσα της αποδοχής 𝛢𝑇𝑀 = {〈𝛭, 𝑤〉: 𝜂 𝛭 𝜀ί𝜈𝛼𝜄 𝛵𝛭 𝑤∈𝐿(𝑀)}. 2. (15) Θέλουμε να δείξουμε με απεικονιστική αναγωγή ότι η γλώσσα 𝑋𝑇𝑀 είναι αναγνωρίσιμη. Χρησιμοποιείστε για την αναγωγή τη γλώσσα 𝛵𝑇𝑀 = {〈𝛭, 𝑤〉:𝜂 𝛭 𝜀ί𝜈𝛼𝜄 𝛵𝛭 𝜅𝛼𝜄 𝜏𝜀𝜌𝜇𝛼𝜏ί𝜁𝜀𝜄 𝜎𝜀 𝜀ί𝜎𝜊𝛿𝜊 𝑤} (η γλώσσα του τερματισμού) που γνωρίζουμε ότι είναι αναγνωρίσιμη.

4. (10) Να βάλετε σε σειρά από τη μικρότερη προς τη μεγαλύτερη κλάση πολυπλοκότητας/υπολογισιμότητας (με την έννοια ότι η μεγαλύτερη κλάση εμπεριέχει πλήρως τη μικρότερη) τις παρακάτω κλάσεις δεδομένου ότι 𝑃≠𝑁𝑃: Αναγνωρίσιμες Γλώσσες, 𝑐𝑜−𝑃, 𝑁𝑇𝐼𝑀𝐸(𝑛⁵ ), 𝑁𝑃, 𝑇𝐼𝑀𝐸(𝑛^𝑛 ), 𝑇𝐼𝑀𝐸(𝑛² ), Διαγνώσιμες Γλώσσες, όπου 𝑛 είναι το μέγεθος της εισόδου.

5. (20) Να αναφέρετε αν οι παρακάτω προτάσεις είναι Σωστές (Σ) ή Λάθος (Λ) χωρίς αιτιολόγηση. Εφαρμόζεται αρνητική βαθμολογία (Σωστό: +0.2, Λάθος: -0.2 – τυχόν αρνητική βαθμολογία μεταφέρεται στον τελικό βαθμό.) i. Η κλάση των αναγνωρίσιμων γλωσσών είναι κλειστή ως προς την πράξη της τομής συνόλων.

• ii. Το γραμμικώς φραγμένο αυτόματο πάντα απαιτεί γραμμικό χρόνο για την αναγνώριση της εισόδου.

• iii. Αν 𝑃≠𝑁𝑃, η κλάση των NP-δυσχερών προβλημάτων εμπεριέχει την κλάση των NP-πλήρων προβλημάτων.

• iv. Αν KNAPSACK  P τότε και co-KNAPSACK  P.

• v. Το σύνολο όλων των γλωσσών στο αλφάβητο Σ={0,1} είναι αριθμήσιμο.

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

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

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

• ix. Αν A ≤ mB και η B είναι αναγνωρίσιμη τότε και η Α είναι αναγνωρίσιμη

• x. Οι γλώσσες της κλάσης P έχουν πιστοποιητικό τόσο για το ΝΑΙ όσο και για το ΟΧΙ.

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

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

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

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

2. (30) Έστω η εξής γλώσσα: 𝛸𝑇𝑀 = {〈𝛭〉: 𝜂 𝛭 𝜀ί𝜈𝛼𝜄 𝛵𝛭 𝜅𝛼𝜄 𝜂 𝜆έ𝜉𝜂 𝑎𝑎𝑏∈𝐿(𝑀)} για αλφάβητο εισόδου 𝛴= {𝑎, 𝑏}. Σας ζητούνται τα εξής:

1. (15) Να αποδείξετε με αλγοριθμική αναγωγή ότι η γλώσσα 𝑋𝑇𝑀 είναι μη-διαγνώσιμη. Για την αναγωγή χρησιμοποιήστε τη μη-διαγνώσιμη γλώσσα της αποδοχής 𝛢𝑇𝑀 = {〈𝛭, 𝑤〉: 𝜂 𝛭 𝜀ί𝜈𝛼𝜄 𝛵𝛭 𝑤∈𝐿(𝑀)}.

2. (15) Θέλουμε να δείξουμε με απεικονιστική αναγωγή ότι η γλώσσα 𝑋𝑇𝑀 είναι αναγνωρίσιμη. Χρησιμοποιείστε για την αναγωγή τη γλώσσα 𝛵𝑇𝑀 = {〈𝛭, 𝑤〉:𝜂 𝛭 𝜀ί𝜈𝛼𝜄 𝛵𝛭 𝜅𝛼𝜄 𝜏𝜀𝜌𝜇𝛼𝜏ί𝜁𝜀𝜄 𝜎𝜀 𝜀ί𝜎𝜊𝛿𝜊 𝑤} (η γλώσσα του τερματισμού) που γνωρίζουμε ότι είναι αναγνωρίσιμη.

3. (10) Να βάλετε σε σειρά από τη μικρότερη προς τη μεγαλύτερη κλάση πολυπλοκότητας/υπολογισιμότητας (με την έννοια ότι η μεγαλύτερη κλάση εμπεριέχει πλήρως τη μικρότερη) τις παρακάτω κλάσεις δεδομένου ότι 𝑃≠𝑁𝑃: Αναγνωρίσιμες Γλώσσες, 𝑐𝑜−𝑃, 𝑁𝑇𝐼𝑀𝐸(𝑛⁷ ), 𝑁𝑃, 𝑇𝐼𝑀𝐸(𝑛^2𝑛 ), 𝑇𝐼𝑀𝐸(𝑛³ ), Διαγνώσιμες Γλώσσες, όπου 𝑛 είναι το μέγεθος της εισόδου.

4. (20) Να αναφέρετε αν οι παρακάτω προτάσεις είναι Σωστές (Σ) ή Λάθος (Λ) χωρίς αιτιολόγηση. Εφαρμόζεται αρνητική βαθμολογία (Σωστό: +0.2, Λάθος: -0.2 – τυχόν αρνητική βαθμολογία μεταφέρεται στον τελικό βαθμό.)

• i. Το γραμμικώς φραγμένο αυτόματο πάντα απαιτεί γραμμικό χρόνο για την αναγνώριση της εισόδου.

• ii. Αν A ≤ mB και η B είναι αναγνωρίσιμη τότε και η Α είναι αναγνωρίσιμη

• iii. Αν 𝑃≠𝑁𝑃, η κλάση των NP-πλήρων προβλημάτων εμπεριέχει την κλάση των NP-δυσχερών προβλημάτων.

• iv. Το σύνολο όλων των γλωσσών στο αλφάβητο Σ={α,β} είναι αριθμήσιμο.

• v. Όλοι οι υπολογίσιμοι αριθμοί είναι περιγράψιμοι.

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

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

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

• ix. Οι γλώσσες της κλάσης NP έχουν πιστοποιητικό τόσο για το ΝΑΙ όσο και για το ΟΧΙ.

• x. Αν KNAPSACK  P τότε και co-KNAPSACK  P.

5. (30) (A) (8) Αποδείξτε ότι αν ένα πρόβλημα 𝐴 είναι NP-πλήρες τότε και το 𝑐𝑜𝐴 (συμπλήρωμα του 𝐴) είναι coNPπλήρες.

(B) (22) Ο Κωστίκας είναι ένας διάσημος διαρρήκτης και έβαλε στοίχημα με το φίλο του Γιωρίκα, που είναι ιδιοκτήτης κοσμηματοπωλείου, ότι μπορεί να κλέψει κοσμήματα συνολικής αξίας τουλάχιστον 𝑋 (αλλιώς δεν θα είχε νόημα να κάνει τη διάρρηξη), σε μία τσάντα που χωρά κοσμήματα βάρους το πολύ 𝑊 (αλλιώς θα σκιστεί η τσάντα και δεν θα μπορεί να τα κουβαλήσει) μέσα σε το πολύ χρόνο 𝑇 (διαφορετικά η αστυνομία θα τον πιάσει). Ο Γιωρίκας, λίγο πριν ξεκινήσει η διάρρηξη, δίνει τις εξής πληροφορίες στον Κωστίκα: για κάθε κόσμημα 𝑖 από τα 𝛮 κοσμήματα συνολικά, του δίνει την τιμή του 𝑥𝑖 καθώς και το βάρος του 𝑤𝑖. Επιπλέον, τον ενημερώνει ότι κάθε κόσμημα 𝑖 είναι μέσα σε κλειδωμένη διάφανη θήκη που απαιτεί χρόνο 𝑡𝑖 για να ξεκλειδώσει. Επομένως, ο Κωστίκας είναι αντιμέτωπος με το εξής πρόβλημα απόφασης που το ονομάζουμε ΔΙΑΡΡΗΞΗ. Υπάρχει υποσύνολο 𝑠⊆{1,2, … , 𝑁} κοσμημάτων έτσι ώστε: η συνολική τους τιμή να είναι ≥𝑋, το συνολικό τους βάρος να είναι ≤𝐵 και ο συνολικός χρόνος ξεκλειδώματος να είναι ≤𝑇 (άθροισμα τιμών, βαρών και χρόνων αντίστοιχα).

1) (15) Να αποδείξετε ότι το πρόβλημα ΔΙΑΡΡΗΞΗ είναι NP-πλήρες και άρα ο Κωστίκας μάλλον θα δυσκολευτεί να επιλέξει τα κατάλληλα κοσμήματα που να ικανοποιούν τους περιορισμούς.

2) (7) Ο Γιωρίκας ισχυρίζεται ότι αποκλείεται ο Κωστίκας να βρει σύνολο κοσμημάτων που να ικανοποιεί ταυτόχρονα όλους τους περιορισμούς (για συγκεκριμένες τιμές, βάρη και χρόνους). Να εξηγήσετε γιατί είναι υπολογιστικά ανέφικτο γενικά για τον Γιωρίκα να αποδείξει τον ισχυρισμό του στον Κωστίκα δεδομένου ότι 𝑁𝑃≠𝑐𝑜𝑁𝑃.

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

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2023-09

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

Θέμα Α1(Α) / Β5(Α): A NP-πλήρες ⇒ coA coNP-πλήρες

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

• Αφού \(A\in NP\), έχουμε \(\overline A\in coNP\) (εξ ορισμού \(coNP=\{\overline L: L\in NP\}\)).
• Δυσχέρεια: έστω \(L'\in coNP\). Τότε \(\overline{L'}\in NP\), άρα \(\overline{L'}\le_p A\) μέσω πολυωνυμικής \(f\): \(x\in\overline{L'}\iff f(x)\in A\). Άρα \(x\in L'\iff f(x)\notin A\iff f(x)\in\overline A\). Η ίδια \(f\) δίνει \(L'\le_p\overline A\).

Άρα το \(\overline A\) είναι coNP-πλήρες.

Θέμα Α1(Β) / Β5(Β): ΔΙΑΡΡΗΞΗ (σημείωση: στην εκφώνηση το όριο βάρους εμφανίζεται ως \(W\) και ως \(B\)· τα θεωρούμε το ίδιο μέγεθος)

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

1) NP-πλήρες. - NP: πιστοποιητικό το υποσύνολο \(S\)· υπολογισμός των τριών αθροισμάτων και σύγκρισή τους με \(X\), \(B\), \(T\) σε πολυωνυμικό χρόνο. - NP-δυσχέρεια (αναγωγή με περιορισμό από KNAPSACK): δοσμένου \(\langle v_i,w_i,k,W\rangle\) (αξίες \(v\), βάρη \(w\), όριο βάρους \(k\), ελάχιστη αξία \(W\)) κατασκευάζουμε: τιμές \(x_i=v_i\), βάρη \(w_i\), χρόνοι \(t_i=0\), \(X=W\), όριο βάρους \(B=k\), \(T=0\). Ο περιορισμός χρόνου ικανοποιείται πάντα, άρα τα στιγμιότυπα έχουν την ίδια απάντηση. Πολυωνυμική αναγωγή.

2) Ο ισχυρισμός του Γιωρίκα είναι ότι το συμπλήρωμα του προβλήματος (\(\overline{\Delta IARRHXH}\)) είναι «ΝΑΙ»-στιγμιότυπο. Αυτό το συμπλήρωμα είναι coNP-πλήρες (από το 1Α). Αν είχε σύντομο πολυωνυμικά επαληθεύσιμο πιστοποιητικό (δηλαδή ανήκε στην NP) τότε \(coNP\subseteq NP\) και \(NP=coNP\), αντίθετο της υπόθεσης \(NP\ne coNP\). Άρα δεν αναμένουμε γενικά πολυωνυμικό πιστοποιητικό «δεν υπάρχει λύση» που θα μπορούσε ο Γιωρίκας να δείξει και ο Κωστίκας να ελέγξει γρήγορα.

Θέμα Α2 / Β1: ΤΜ από διάγραμμα

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Στο επίσημο έγγραφο θεμάτων και λύσεων (CC_Exams-12-9-2023.pdf, σελίδες 1, 2 και 3) το διάγραμμα της αιτιοκρατικής Μηχανής Turing \(M\) δίνεται ευκρινώς:

Δομή και Μεταβάσεις της ΤΜ \(M\) (Ομάδα Α: \(\Sigma = \{0, 1\}, \Gamma = \{0, 1, \sqcup\}\))

• Καταστάσεις: \(q_0\) (αρχική), \(q_1, q_2, q_a\) (αποδοχής), \(q_r\) (απόρριψης).
• Μεταβάσεις:
• \(\delta(q_0, 1) = (q_1, \Delta)\)
• \(\delta(q_0, 0) = (q_r, A)\) και \(\delta(q_0, \sqcup) = (q_r, A)\)
• \(\delta(q_1, 0) = (q_0, A)\)
• \(\delta(q_1, 1) = (q_2, \Delta)\)
• \(\delta(q_1, \sqcup) = (q_a, A)\)
• \(\delta(q_2, 0) = (q_2, \Delta)\) και \(\delta(q_2, 1) = (q_2, \Delta)\)
• \(\delta(q_2, \sqcup) = (q_a, A)\) (Για την Ομάδα Β ισχύει ακριβώς το ίδιο διάγραμμα αντικαθιστώντας το 0 με \(x\) και το 1 με \(y\)).

Ερωτήματα

1. Είναι η \(M\) διαγνώστης; Όχι, η \(M\) δεν είναι διαγνώστης. Αιτιολόγηση: Σε είσοδο \(10\), η μηχανή ξεκινά από την αρχική διαμόρφωση \(q_0 10\).
2. Διαβάζει \(1\) στην \(q_0 \to\) μεταβαίνει στην \(q_1\) και κινείται δεξιά (\(\Delta\)): διαμόρφωση \(1 q_1 0\).
3. Διαβάζει \(0\) στην \(q_1 \to\) μεταβαίνει στην \(q_0\) και κινείται αριστερά (\(A\)): διαμόρφωση \(q_0 1 0\).

4. Διαβάζει \(1\) στην \(q_0 \to\) μεταβαίνει στην \(q_1\) και κινείται δεξιά (\(\Delta\)): διαμόρφωση \(1 q_1 0\). Επομένως, για είσοδο που περιέχει το πρόθεμα \(10\), η μηχανή εγκλωβίζεται σε ατέρμονα βρόχο (infinite loop) ταλαντευόμενη μεταξύ των διαμορφώσεων \(q_0 1 0\) και \(1 q_1 0\), χωρίς ποτέ να τερματίζει (ούτε σε \(q_a\) ούτε σε \(q_r\)). Συνεπώς, δεν τερματίζει για όλες τις εισόδους και δεν είναι διαγνώστης.

5. Ποια είναι η γλώσσα που αναγνωρίζει η \(M\);

6. Για την κενή λέξη \(\varepsilon\) ή λέξεις που ξεκινούν με \(0\): η \(M\) μεταβαίνει άμεσα στην \(q_r\) και απορρίπτει.
7. Για λέξεις που ξεκινούν με \(10\): η \(M\) εγκλωβίζεται σε ατέρμονα βρόχο.
8. Για λέξη \(1\) (ακολουθούμενη από κενό \(\sqcup\)): από \(q_0\) πάει \(q_1\), διαβάζει \(\sqcup \to\) μεταβαίνει στην \(q_a\) και αποδέχεται.
9. Για λέξεις που ξεκινούν με δύο άσσους \(11\): από \(q_0\) πάει \(q_1\) και μετά \(q_2\). Στην \(q_2\) σαρώνει όλα τα υπόλοιπα σύμβολα (\(0, 1\)) κινούμενη δεξιά και μόλις συναντήσει το πρώτο κενό \(\sqcup\) μεταβαίνει στην \(q_a\) και αποδέχεται. Επομένως, η γλώσσα που αναγνωρίζει η \(M\) είναι: $\(L(M) = \{1\} \cup \{11w \mid w \in \{0, 1\}^*\} = 1 + 11(0 + 1)^*\)$ (Για την Ομάδα Β: \(L(M) = y + yy(x + y)^*\)).

---

Θέμα Α3 / Β2: \(X_{TM}=\{\langle M\rangle: u\in L(M)\}\), με \(u=001\) (Ομάδα Α) ή \(u=aab\) (Ομάδα Β)

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

1) Μη διαγνώσιμη (αναγωγή από \(A_{TM}\)). \(\langle M,w\rangle\mapsto\langle M'\rangle\): η \(M'\) για είσοδο \(x\) προσομοιώνει την \(M\) στο \(w\) (αγνοώντας το \(x\)) και δέχεται ανν η \(M\) δέχεται. Αν \(w\in L(M)\) τότε \(L(M')=\Sigma^*\ni u\), αλλιώς \(L(M')=\varnothing\). Άρα \(\langle M,w\rangle\in A_{TM}\iff\langle M'\rangle\in X_{TM}\). Αν η \(X_{TM}\) ήταν διαγνώσιμη, θα ήταν και η \(A_{TM}\). Άτοπο.

2) Αναγνωρίσιμη (\(X_{TM}\le_m T_{TM}\)). \(\langle M\rangle\mapsto\langle M'',u\rangle\), όπου η \(M''\) προσομοιώνει την \(M\) στην είσοδο \(x\): αν η \(M\) δεχτεί, δέχεται· αν απορρίψει, μπαίνει σε ατέρμονο βρόχο. Τότε η \(M''\) τερματίζει στο \(u\) ανν η \(M\) δέχεται το \(u\). Η \(T_{TM}\) είναι αναγνωρίσιμη, άρα και η \(X_{TM}\).

Θέμα Α4 / Β3: διάταξη κλάσεων

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Στο επίσημο έγγραφο λύσεων (CC_Exams-12-9-2023.pdf, σελίδα 4) δίνεται η πλήρης διάταξη εγκλεισμού, καθώς και η επισήμανση του τυπογραφικού λάθους της εκφώνησης:

Διάταξη Εγκλεισμού

Δεδομένου ότι \(P \neq NP\) (και άρα \(P = \text{co-}P \subsetneq NP\)): $\(\text{TIME}(n^2) \subseteq \text{co-}P \subseteq NP \subseteq \text{TIME}(n^n) \subseteq \text{Διαγνώσιμες Γλώσσες} \subseteq \text{Αναγνωρίσιμες Γλώσσες}\)$ (Για την Ομάδα Β, με \(\text{TIME}(n^3)\) και \(\text{TIME}(n^{2n})\)): $\(\text{TIME}(n^3) \subseteq \text{co-}P \subseteq NP \subseteq \text{TIME}(n^{2n}) \subseteq \text{Διαγνώσιμες Γλώσσες} \subseteq \text{Αναγνωρίσιμες Γλώσσες}\)$

Σημείωση για την κλάση \(\text{NTIME}(n^5)\) [ή \(\text{NTIME}(n^7)\)]

Όπως αναφέρεται ρητά στη λύση των θεμάτων:

«Λάθος στην εκφώνηση: Το \(NTIME(n^5)\) [αντίστοιχα \(NTIME(n^7)\)] τέμνεται με το co-P και έχει γλώσσες που δεν περιέχονται στο co-P αλλά και αντίστροφα. Διορθώθηκε η βαθμολογία.»

Συγκεκριμένα, ισχύει \(P \subseteq NTIME(n^5) \subseteq NP\). Εφόσον \(P \neq NP\), η κλάση \(NTIME(n^5)\) δεν μπορεί να διαταχθεί γραμμικά ως προς την \(\text{co-}P\) (υπάρχουν γλώσσες στο \(\text{co-}P \setminus NTIME(n^5)\) και γλώσσες στο \(NTIME(n^5) \setminus \text{co-}P\)). Εξαιρώντας τον μη συγκρίσιμο όρο, η αλυσίδα γνήσιων εγκλεισμών είναι η παραπάνω.

Θέμα Α5: Σωστό/Λάθος

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη

Ομάδα Α: i Σ · ii Λ (ένα ΓΦΑ χρησιμοποιεί γραμμικό χώρο, όχι αναγκαστικά γραμμικό χρόνο) · iii Σ · iv Σ (το \(\overline{KNAPSACK}\) ∈ P αφού η P είναι κλειστή ως προς το συμπλήρωμα) · v Λ · vi Λ · vii Λ (η τομή, όχι η ένωση) · viii Σ · ix Σ · x Σ (πιστοποιητικό: το κενό· \(P\subseteq NP\cap coNP\)).

Ομάδα Β (Θέμα 4): i Λ · ii Σ · iii Λ (το αντίστροφο ισχύει: NPC ⊆ NP-hard) · iv Λ · v Σ · vi Σ · vii Σ (αναγνωρίσιμες: κλειστές ως προς ένωση) · viii Σ (ανοιχτό αν \(NP=coNP\)) · ix Λ (εικάζεται· πλήρης έλλειψη πιστοποιητικού «όχι» για NP-πλήρη) · x Σ.

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

---

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