Μετάβαση στο περιεχόμενο

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

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

CC_Exams-12-6-2023.pdf (σελ. 1,4,7,10)

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

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

2. (30) (Α) (10) Έστω οι εξής γλώσσες:

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

𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨= {〈𝐺,𝑠, 𝑡〉: 𝜐𝜋ά𝜌𝜒𝜀𝜄 𝛿𝜄𝛼𝛿𝜌𝜊𝜇ή 𝛼𝜋ό 𝜏𝜊𝜈 𝜅ό𝜇𝛽𝜊 𝑠 𝜎𝜏𝜊𝜈 𝜅ό𝜇𝛽𝜊 𝑡 𝜎𝜏𝜊 𝛼𝜅𝛼𝜏𝜀ύ𝜃𝜐𝜈𝜏𝜊 𝛾𝜌ά𝜑𝜂𝜇𝛼 𝐺} 𝛫𝛬𝛪𝛫𝛢= {〈𝐺, 𝑘〉: 𝜏𝜊 𝛼𝜅𝛼𝜏𝜀ύ𝜃𝜐𝜈𝜏𝜊 𝛾𝜌ά𝜑𝜂𝜇𝛼 𝐺 έ𝜒𝜀𝜄 𝜐𝜋𝜊𝛾𝜌ά𝜑𝜂𝜇𝛼 𝜋𝜊𝜐 𝜀ί𝜈𝛼𝜄 𝜅𝜆ί𝜅𝛼 𝜇𝜀 𝑘 𝜅ό𝜇𝛽𝜊𝜐𝜍} Χαρακτηρίστε ως αληθείς ή ψευδείς τις παρακάτω δηλώσεις και δώστε σύντομη αιτιολόγηση. Για τις απαντήσεις σας θεωρήστε ότι 𝑃≠𝑁𝑃.

α. (2) Το πρόβλημα 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨 ανήκει στην κλάση 𝑁𝑃.

β. (3) Υπάρχει η απεικονιστική αναγωγή πολυωνυμικού χρόνου 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨≤𝑃 𝛫𝛬𝛪𝛫𝛢.

γ. (5) Υπάρχει η απεικονιστική αναγωγή πολυωνυμικού χρόνου 𝛫𝛬𝛪𝛫𝛢≤𝑃 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨.

Υπόδειξη: Στα (β,γ) δεν χρειάζεται να κάνετε την αναγωγή. Μπορείτε πιο εύκολα να επιχειρηματολογήσετε σχετικά. (Β) (20) Ορίζουμε το εξής πρόβλημα προσεγγιστικής κλίκας 𝛱𝛫: Ένα γράφημα 𝐺 έχει μία 𝑟-προσεγγιστική κλίκα με 𝑘 κόμβους αν το γράφημα 𝐺 έχει ένα υπογράφημα ℎ με 𝑘 κόμβους έτσι ώστε με την πρόσθεση ακριβώς 𝑟 κατάλληλων ακμών στο ℎ αυτό να γίνεται κλίκα. Επομένως, ορίζουμε:

𝛱𝛫= {〈𝐺,𝑘, 𝑟〉: 𝜏𝜊 𝛼𝜅𝛼𝜏𝜀ύ𝜃𝜐𝜈𝜏𝜊 𝛾𝜌ά𝜑𝜂𝜇𝛼 𝐺 έ𝜒𝜀𝜄 𝜇ί𝛼 𝑟−𝜋𝜌𝜊𝜎𝜀𝛾𝛾𝜄𝜎𝜏𝜄𝜅ή 𝜅𝜆ί𝜅𝛼 𝜇𝜀 𝑘 𝜅ό𝜇𝛽𝜊𝜐𝜍} Να αποδείξετε ότι το πρόβλημα 𝛱𝛫 είναι NP-πλήρες. Υπόδειξη: Χρησιμοποιήστε (χωρίς να είναι δεσμευτικό) αναγωγή με περιορισμό από το κατάλληλο πρόβλημα.

3. (40) Έστω η εξής γλώσσα: 𝐸𝑇𝑀 = {〈𝛭〉: 𝜂 𝛭 𝜀ί𝜈𝛼𝜄 𝛵𝛭 𝜅𝛼𝜄 𝜖∈𝐿(𝑀)}, όπου 𝜖 η κενή λέξη και 𝐿(𝑀) είναι η γλώσσα της ΤΜ Μ. Σας ζητούνται τα εξής:

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

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

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

  • ii. Το θεώρημα των Cook-Levin αναφέρει ότι οποιοσδήποτε αλγόριθμος μπορεί να αναπαρασταθεί από μία ΤΜ.

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

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

  • v. Αν 3SAT  P τότε και co-3SAT  P.

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

  • vii. Η κλάση των NP-δυσχερών προβλημάτων εμπεριέχει την κλάση NPC.

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

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

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

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

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

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

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

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

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

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

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

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

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

  • v. Η κλάση των NP-δυσχερών προβλημάτων δεν εμπεριέχει την κλάση NPC.

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

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

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

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

  • x. Το θεώρημα των Cook-Levin αναφέρει ότι οποιοσδήποτε αλγόριθμος μπορεί να αναπαρασταθεί από μία ΤΜ.

4. (30) (Α) (10) Έστω οι εξής γλώσσες: 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨= {〈𝐺,𝑠, 𝑡〉: 𝜐𝜋ά𝜌𝜒𝜀𝜄 𝛿𝜄𝛼𝛿𝜌𝜊𝜇ή 𝛼𝜋ό 𝜏𝜊𝜈 𝜅ό𝜇𝛽𝜊 𝑠 𝜎𝜏𝜊𝜈 𝜅ό𝜇𝛽𝜊 𝑡 𝜎𝜏𝜊 𝛼𝜅𝛼𝜏𝜀ύ𝜃𝜐𝜈𝜏𝜊 𝛾𝜌ά𝜑𝜂𝜇𝛼 𝐺} 𝛢𝛴= {〈𝐺, 𝑘〉: 𝜏𝜊 𝛼𝜅𝛼𝜏𝜀ύ𝜃𝜐𝜈𝜏𝜊 𝛾𝜌ά𝜑𝜂𝜇𝛼 𝐺 έ𝜒𝜀𝜄 𝛼𝜈𝜀𝜉ά𝜌𝜏𝜂𝜏𝜊 𝜎ύ𝜈𝜊𝜆𝜊 𝜇𝜀 𝑘 𝜅ό𝜇𝛽𝜊𝜐𝜍} Χαρακτηρίστε ως αληθείς ή ψευδείς τις παρακάτω δηλώσεις και δώστε σύντομη αιτιολόγηση. Για τις απαντήσεις σας θεωρήστε ότι 𝑃≠𝑁𝑃.

α. (2) Το πρόβλημα 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨 ανήκει στην κλάση 𝑁𝑃.

β. (3) Υπάρχει η απεικονιστική αναγωγή πολυωνυμικού χρόνου 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨≤𝑃 𝛢𝛴.

γ. (5) Υπάρχει η απεικονιστική αναγωγή πολυωνυμικού χρόνου 𝛢𝛴≤𝑃 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨.

Υπόδειξη: Στα (β,γ) δεν χρειάζεται να κάνετε την αναγωγή. Μπορείτε πιο εύκολα να επιχειρηματολογήσετε σχετικά. (Β) (20) Ορίζουμε το εξής πρόβλημα προσεγγιστικού ανεξάρτητου συνόλου 𝛱𝛢𝛴: Ένα γράφημα 𝐺 έχει ένα 𝑟- προσεγγιστικό ανεξάρτητο σύνολο με 𝑘 κόμβους αν το γράφημα 𝐺 έχει ένα υπογράφημα ℎ με 𝑘 κόμβους έτσι ώστε με την αφαίρεση ακριβώς 𝑟 ακμών στο ℎ αυτό να γίνεται ανεξάρτητο σύνολο. Επομένως, ορίζουμε:

𝛱𝛢𝛴= {〈𝐺, 𝑘, 𝑟〉: 𝜏𝜊 𝛼𝜅𝛼𝜏𝜀ύ𝜃𝜐𝜈𝜏𝜊 𝛾𝜌ά𝜑𝜂𝜇𝛼 𝐺 έ𝜒𝜀𝜄 έ𝜈𝛼 𝑟−𝜋𝜌𝜊𝜎𝜀𝛾𝛾𝜄𝜎𝜏𝜄𝜅ό 𝛼𝜈𝜀𝜉. 𝜎ύ𝜈𝜊𝜆𝜊 𝜇𝜀 𝑘 𝜅ό𝜇𝛽𝜊𝜐𝜍} Να αποδείξετε ότι το πρόβλημα 𝛱𝛢𝛴 είναι NP-πλήρες.

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

5. (40) Έστω η εξής γλώσσα: 𝛬𝑇𝑀 = {〈𝛭〉: 𝜂 𝛭 𝜀ί𝜈𝛼𝜄 𝛵𝛭 𝜅𝛼𝜄 𝜖∈𝐿(𝑀)}, όπου 𝜖 η κενή λέξη και 𝐿(𝑀) είναι η γλώσσα της ΤΜ Μ. Σας ζητούνται τα εξής:

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

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

ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ « ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ » - 12/6/2023

Διάρκεια Εξέτασης (2 ώρες και 40 λεπτά) – Ομάδα Γ

1. (30) (Α) (10) Έστω οι εξής γλώσσες:

𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨= {〈𝐺,𝑠, 𝑡〉: 𝜐𝜋ά𝜌𝜒𝜀𝜄 𝛿𝜄𝛼𝛿𝜌𝜊𝜇ή 𝛼𝜋ό 𝜏𝜊𝜈 𝜅ό𝜇𝛽𝜊 𝑠 𝜎𝜏𝜊𝜈 𝜅ό𝜇𝛽𝜊 𝑡 𝜎𝜏𝜊 𝛼𝜅𝛼𝜏𝜀ύ𝜃𝜐𝜈𝜏𝜊 𝛾𝜌ά𝜑𝜂𝜇𝛼 𝐺} 𝛫𝛬= {〈𝐺, 𝑘〉: 𝜏𝜊 𝛼𝜅𝛼𝜏𝜀ύ𝜃𝜐𝜈𝜏𝜊 𝛾𝜌ά𝜑𝜂𝜇𝛼 𝐺 έ𝜒𝜀𝜄 𝜐𝜋𝜊𝛾𝜌ά𝜑𝜂𝜇𝛼 𝜋𝜊𝜐 𝜀ί𝜈𝛼𝜄 𝜅𝜆ί𝜅𝛼 𝜇𝜀 𝑘 𝜅ό𝜇𝛽𝜊𝜐𝜍} Χαρακτηρίστε ως αληθείς ή ψευδείς τις παρακάτω δηλώσεις και δώστε σύντομη αιτιολόγηση. Για τις απαντήσεις σας θεωρήστε ότι 𝑃≠𝑁𝑃.

α. (2) Το πρόβλημα 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨 ανήκει στην κλάση 𝑁𝑃.

β. (3) Υπάρχει η απεικονιστική αναγωγή πολυωνυμικού χρόνου 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨≤𝑃 𝛫𝛬.

γ. (5) Υπάρχει η απεικονιστική αναγωγή πολυωνυμικού χρόνου 𝛫𝛬≤𝑃 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨.

Υπόδειξη: Στα (β,γ) δεν χρειάζεται να κάνετε την αναγωγή. Μπορείτε πιο εύκολα να επιχειρηματολογήσετε σχετικά. (Β) (20) Ορίζουμε το εξής πρόβλημα προσεγγιστικής κλίκας 𝛱𝛫𝛬: Ένα γράφημα 𝐺 έχει μία 𝑟-προσεγγιστική κλίκα με 𝑘 κόμβους αν το γράφημα 𝐺 έχει ένα υπογράφημα ℎ με 𝑘 κόμβους έτσι ώστε με την πρόσθεση ακριβώς 𝑟 κατάλληλων ακμών στο ℎ αυτό να γίνεται κλίκα. Επομένως, ορίζουμε:

𝛱𝛫𝛬= {〈𝐺, 𝑘, 𝑟〉: 𝜏𝜊 𝛼𝜅𝛼𝜏𝜀ύ𝜃𝜐𝜈𝜏𝜊 𝛾𝜌ά𝜑𝜂𝜇𝛼 𝐺 έ𝜒𝜀𝜄 𝜇ί𝛼 𝑟−𝜋𝜌𝜊𝜎𝜀𝛾𝛾𝜄𝜎𝜏𝜄𝜅ή 𝜅𝜆ί𝜅𝛼 𝜇𝜀 𝑘 𝜅ό𝜇𝛽𝜊𝜐𝜍} Να αποδείξετε ότι το πρόβλημα 𝛱𝛫𝛬 είναι NP-πλήρες. Υπόδειξη: Χρησιμοποιήστε (χωρίς να είναι δεσμευτικό) αναγωγή με περιορισμό από το κατάλληλο πρόβλημα.

2. (40) Έστω η εξής γλώσσα: 𝛯𝑇𝑀 = {〈𝛭〉: 𝜂 𝛭 𝜀ί𝜈𝛼𝜄 𝛵𝛭 𝜅𝛼𝜄 𝜖∈𝐿(𝑀)}, όπου 𝜖 η κενή λέξη και 𝐿(𝑀) είναι η γλώσσα της ΤΜ Μ. Σας ζητούνται τα εξής:

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

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

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

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

  • ii. Το θεώρημα των Cook-Levin αναφέρει ότι υπάρχει πρόβλημα που δεν λύνεται από μία ΤΜ.

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

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

  • v. Η κλάση των NP-δυσχερών προβλημάτων εμπεριέχει την κλάση NPC.

  • vi. Όλοι οι πραγματικοί αριθμοί είναι περιγράψιμοι.

  • vii. Η κλάση NP δεν είναι κλειστή ως προς την πράξη της ένωσης.

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

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

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

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

b →Δ
b →Δ
q0
⌴ →A q 1 q 2
⌴ →A
b →Δ
qr ⌴ →b,A qα

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

ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ « ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ » - 12/6/2023

Διάρκεια Εξέτασης (2 ώρες και 40 λεπτά) – Ομάδα Δ

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

2. (40) Έστω η εξής γλώσσα: 𝛲𝑇𝑀 = {〈𝛭〉: 𝜂 𝛭 𝜀ί𝜈𝛼𝜄 𝛵𝛭 𝜅𝛼𝜄 𝜖∈𝐿(𝑀)}, όπου 𝜖 η κενή λέξη και 𝐿(𝑀) είναι η γλώσσα της ΤΜ Μ. Σας ζητούνται τα εξής:

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

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

4. (30) (Α) (10) Έστω οι εξής γλώσσες:

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

𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨= {〈𝐺,𝑠, 𝑡〉: 𝜐𝜋ά𝜌𝜒𝜀𝜄 𝛿𝜄𝛼𝛿𝜌𝜊𝜇ή 𝛼𝜋ό 𝜏𝜊𝜈 𝜅ό𝜇𝛽𝜊 𝑠 𝜎𝜏𝜊𝜈 𝜅ό𝜇𝛽𝜊 𝑡 𝜎𝜏𝜊 𝛼𝜅𝛼𝜏𝜀ύ𝜃𝜐𝜈𝜏𝜊 𝛾𝜌ά𝜑𝜂𝜇𝛼 𝐺} 𝛢𝛮𝛴𝛶= {〈𝐺, 𝑘〉: 𝜏𝜊 𝛼𝜅𝛼𝜏𝜀ύ𝜃𝜐𝜈𝜏𝜊 𝛾𝜌ά𝜑𝜂𝜇𝛼 𝐺 έ𝜒𝜀𝜄 𝛼𝜈𝜀𝜉ά𝜌𝜏𝜂𝜏𝜊 𝜎ύ𝜈𝜊𝜆𝜊 𝜇𝜀 𝑘 𝜅ό𝜇𝛽𝜊𝜐𝜍} Χαρακτηρίστε ως αληθείς ή ψευδείς τις παρακάτω δηλώσεις και δώστε σύντομη αιτιολόγηση. Για τις απαντήσεις σας θεωρήστε ότι 𝑃≠𝑁𝑃.

α. (2) Το πρόβλημα 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨 ανήκει στην κλάση 𝑁𝑃.

β. (3) Υπάρχει η απεικονιστική αναγωγή πολυωνυμικού χρόνου 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨≤𝑃 𝛢𝛮𝛴𝛶.

γ. (5) Υπάρχει η απεικονιστική αναγωγή πολυωνυμικού χρόνου 𝛢𝛮𝛴𝛶≤𝑃 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨.

Υπόδειξη: Στα (β,γ) δεν χρειάζεται να κάνετε την αναγωγή. Μπορείτε πιο εύκολα να επιχειρηματολογήσετε σχετικά. (Β) (20) Ορίζουμε το εξής πρόβλημα προσεγγιστικού ανεξάρτητου συνόλου 𝛱𝛢𝛮𝛴𝛶: Ένα γράφημα 𝐺 έχει ένα 𝑟-προσεγγιστικό ανεξάρτητο σύνολο με 𝑘 κόμβους αν το γράφημα 𝐺 έχει ένα υπογράφημα ℎ με 𝑘 κόμβους έτσι ώστε με την αφαίρεση ακριβώς 𝑟 ακμών στο ℎ αυτό να γίνεται ανεξάρτητο σύνολο. Επομένως, ορίζουμε:

𝛱𝛢𝛮𝛴𝛶= {〈𝐺, 𝑘, 𝑟〉: 𝜏𝜊 𝛼𝜅𝛼𝜏𝜀ύ𝜃𝜐𝜈𝜏𝜊 𝛾𝜌ά𝜑𝜂𝜇𝛼 𝐺 έ𝜒𝜀𝜄 έ𝜈𝛼 𝑟−𝜋𝜌𝜊𝜎𝜀𝛾𝛾𝜄𝜎𝜏𝜄𝜅ό 𝛼𝜈. 𝜎ύ𝜈𝜊𝜆𝜊 𝜇𝜀 𝑘 𝜅ό𝜇𝛽𝜊𝜐𝜍} Να αποδείξετε ότι το πρόβλημα 𝛱𝛢𝛮𝛴𝛶 είναι NP-πλήρες.

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

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

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

  • iii. Αν 4SAT  P τότε και co-4SAT  P.

  • iv. Η κλάση των NP-δυσχερών προβλημάτων εμπεριέχει την κλάση NPC.

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

  • vi. Η κλάση NP φαίνεται ότι δεν είναι κλειστή ως προς την πράξη του συμπληρώματος.

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

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

  • ix. Το θεώρημα των Cook-Levin αναφέρει ότι κάποιοι αλγόριθμοι μπορούν να αναπαρασταθούν από μία ΤΜ.

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

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

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

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

Προσοχή

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

AI λύσεις — 2023-06

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

ΤΜ από διάγραμμα (Ομάδες Α1, Β2, Γ5, Δ3)

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

Εκφώνηση & Παρατήρηση από το πρωτότυπο PDF

Στο αρχικό έγγραφο θεμάτων και λύσεων (CC_Exams-12-6-2023.pdf): - Το θέμα εμφανίζεται ως: - Ομάδα Α (Θέμα 1): \(\Sigma = \{\alpha\}, \Gamma = \{\alpha, \sqcup\}\) - Ομάδα Β (Θέμα 2): \(\Sigma = \{0\}, \Gamma = \{0, \sqcup\}\) - Ομάδα Γ (Θέμα 5): \(\Sigma = \{b\}, \Gamma = \{b, \sqcup\}\) - Ομάδα Δ (Θέμα 3): \(\Sigma = \{1\}, \Gamma = \{1, \sqcup\}\) - Η τοπολογία του διαγράμματος μεταβάσεων είναι ακριβώς η ίδια σε όλες τις ομάδες, αλλάζοντας μόνο το σύμβολο του μονογράμματου αλφαβήτου (\(\sigma \in \{\alpha, 0, b, 1\}\)).

Συνάρτηση Μετάβασης (όπως φαίνεται καθαρά στο σχήμα):

Έστω σύμβολο \(\sigma \in \{\alpha, 0, b, 1\}\): - Από την αρχική κατάσταση \(q_0\): - \(\delta(q_0, \sigma) = (q_1, \sigma, \Delta)\) (διαβάζει \(\sigma\), το αφήνει ίδιο, πάει δεξιά στην κατάσταση \(q_1\)). - \(\delta(q_0, \sqcup) = (q_r, \sqcup, A)\) (διαβάζει κενό \(\sqcup\), πάει αριστερά στην κατάσταση απόρριψης \(q_r\)). - Από την κατάσταση \(q_1\): - \(\delta(q_1, \sigma) = (q_2, \sigma, \Delta)\) (διαβάζει \(\sigma\), πάει δεξιά στην κατάσταση \(q_2\)). - \(\delta(q_1, \sqcup) = (q_1, \sigma, A)\) (διαβάζει κενό \(\sqcup\), γράφει \(\sigma\), πάει αριστερά και παραμένει στην \(q_1\)). - Από την κατάσταση \(q_2\): - \(\delta(q_2, \sigma) = (q_1, \sigma, \Delta)\) (διαβάζει \(\sigma\), πάει δεξιά στην κατάσταση \(q_1\)). - \(\delta(q_2, \sqcup) = (q_\alpha, \sqcup, A)\) (διαβάζει κενό \(\sqcup\), πάει αριστερά στην κατάσταση αποδοχής \(q_\alpha\)).

Εκτέλεση και Συμπεριφορά:

  1. Κενή λέξη \(w = \epsilon\): Στην αρχή η κεφαλή βρίσκεται στο πρώτο κελί που περιέχει \(\sqcup\), σε κατάσταση \(q_0\). Εκτελείται η μετάβαση \(\delta(q_0, \sqcup) = (q_r, \sqcup, A)\). Η μηχανή μεταβαίνει στην \(q_r\) και τερματίζει απορρίπτοντας. Άρα \(\epsilon \notin L(M)\).

  2. Είσοδος περιττού μήκους \(w = \sigma^{2k+1}\) (\(k \ge 0\)):

  3. Για \(w = \sigma\) (\(k=0\)):

    • Αρχική διαμόρφωση: \((q_0, \underline{\sigma}\sqcup)\).
    • Βήμα 1: \((\sigma, q_1, \underline{\sqcup})\).
    • Στην κατάσταση \(q_1\), διαβάζει \(\sqcup\). Εκτελεί τη μετάβαση \(\sqcup \to \sigma, A\): γράφει \(\sigma\), κινείται αριστερά και παραμένει στην κατάσταση \(q_1\): \((q_1, \underline{\sigma}\sigma)\).
    • Βήμα 2: στην κατάσταση \(q_1\) διαβάζει \(\sigma \to\) μεταβαίνει στην \(q_2\) και κινείται δεξιά: \((\sigma, q_2, \underline{\sigma})\).
    • Βήμα 3: στην κατάσταση \(q_2\) διαβάζει \(\sigma \to\) μεταβαίνει στην \(q_1\) και κινείται δεξιά: \((\sigma\sigma, q_1, \underline{\sqcup})\).
    • Εδώ η ταινία περιέχει ξανά κενό \(\sqcup\) με την κατάσταση να είναι \(q_1\). Θα ξαναγράψει \(\sigma\), θα πάει αριστερά και θα επαναλάβει τον κύκλο \(q_1 \to q_2 \to q_1\), προσθέτοντας συνεχώς \(\sigma\) στην ταινία.
    • Επομένως, για είσοδο \(\sigma\) (και γενικά για κάθε περιττό πλήθος συμβόλων), η μηχανή δεν τερματίζει ποτέ αλλά εγκλωβίζεται σε ατέρμονα βρόχο.

  4. Είσοδος αρτίου μήκους \(w = \sigma^{2k}\) (\(k \ge 1\)):

  5. Για \(w = \sigma\sigma\) (\(k=1\)):
    • Αρχική διαμόρφωση: \((q_0, \underline{\sigma}\sigma\sqcup)\).
    • Βήμα 1: \((\sigma, q_1, \underline{\sigma}\sqcup)\).
    • Βήμα 2: \((\sigma\sigma, q_2, \underline{\sqcup})\).
    • Στην \(q_2\) διαβάζει \(\sqcup\). Εκτελεί τη μετάβαση \(\delta(q_2, \sqcup) = (q_\alpha, \sqcup, A)\): μεταβαίνει στην κατάσταση αποδοχής \(q_\alpha\) και τερματίζει!
  6. Γενικά για κάθε άρτιο μήκος \(2k \ge 2\):
    • Από \(q_0 \xrightarrow{\sigma} q_1\).
    • Τα υπόλοιπα \(2k-1\) σύμβολα εναλλάσσουν τις καταστάσεις \(q_1 \xrightarrow{\sigma} q_2 \xrightarrow{\sigma} q_1 \dots\)
    • Επειδή το υπόλοιπο μήκος είναι περιττό (\(2k-1\)), το τελευταίο σύμβολο \(\sigma\) οδηγεί στην κατάσταση \(q_2\).
    • Στο επόμενο βήμα, η κεφαλή συναντά το πρώτο κενό \(\sqcup\) ευρισκόμενη στην \(q_2\), οπότε εκτελείται η μετάβαση προς \(q_\alpha\) και η μηχανή τερματίζει με αποδοχή.

Συμπεράσματα:

  1. Είναι η \(M\) διαγνώστης; Όχι, η \(M\) δεν είναι διαγνώστης (decider), διότι για εισόδους περιττού μήκους (π.χ. \(w = \sigma\)) εγκλωβίζεται σε ατέρμονα βρόχο (infinite loop) και δεν τερματίζει ποτέ.
  2. Ποια είναι η γλώσσα \(L(M)\) που αναγνωρίζει; Η μηχανή αποδέχεται ακριβώς όλες τις λέξεις αρτίου θετικού μήκους:
  3. Ομάδα Α: \(L(M) = \alpha\alpha(\alpha\alpha)^*\)
  4. Ομάδα Β: \(L(M) = 00(00)^*\)
  5. Ομάδα Γ: \(L(M) = bb(bb)^*\)
  6. Ομάδα Δ: \(L(M) = 11(11)^*\)

Θέμα Α2(Α) και παραλλαγές: ΔΙΑΔΡΟΜΗ vs ΚΛΙΚΑ / ΑΝΕΞΑΡΤΗΤΟ ΣΥΝΟΛΟ

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

  • α. Αληθές. ΔΙΑΔΡΟΜΗ ∈ P ⊆ NP (BFS/DFS).
  • β. Αληθές. ΔΙΑΔΡΟΜΗ ∈ P, ενώ η ΚΛΙΚΑ (και το ΑΝΕΞΑΡΤΗΤΟ ΣΥΝΟΛΟ) είναι NP-πλήρης και μη τετριμμένη: η αναγωγή λύνει το ΔΙΑΔΡΟΜΗ και επιστρέφει σταθερό ΝΑΙ/ΟΧΙ στιγμιότυπο.
  • γ. Ψευδές (υπό \(P\neq NP\)): αλλιώς η ΚΛΙΚΑ θα ήταν στην P.

Θέμα Α2(Β) / Γ1(Β): \(\Pi K\) r-προσεγγιστική κλίκα είναι NP-πλήρες

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

NP: πιστοποιητικό: το σύνολο \(h\) των \(k\) κορυφών. Ο επαληθευτής μετρά τα ζεύγη κορυφών του \(h\) που δεν συνδέονται· «προσθήκη ακριβώς \(r\) ακμών κάνει κλίκα» ισοδυναμεί με: το πλήθος των ζευγών που λείπουν ισούται με \(r\). Πολυωνυμικός έλεγχος.

NP-δυσχέρεια (με περιορισμό \(r=0\)): CLIQUE \(\le_p \Pi K\) με \(\langle G,k\rangle\mapsto\langle G,k,0\rangle\). Μια 0-προσεγγιστική κλίκα με \(k\) κόμβους είναι κλίκα με \(k\) κόμβους. NP-πλήρες.

Θέμα Β4(Β) / Δ4(Β): \(\Pi AS\) r-προσεγγιστικό ανεξάρτητο σύνολο

Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: υψηλή

NP: πιστοποιητικό: το \(h\) με \(k\) κορυφές· μετράμε τις ακμές του \(h\) και ελέγχουμε ότι είναι ακριβώς \(r\) (αφαίρεση ακριβώς \(r\) ακμών κάνει το \(h\) ανεξάρτητο ανν είχε ακριβώς \(r\) ακμές).

NP-δυσχέρεια: INDEPENDENT-SET \(\le_p \Pi AS\) με \(\langle G,k\rangle\mapsto\langle G,k,0\rangle\). NP-πλήρες.

Θέμα Α3 / Β5 / Γ2 / Δ2: \(ETM=\{\langle M\rangle:\epsilon\in L(M)\}\)

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

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

2) Αναγνωρίσιμη (αναγωγή \(ETM\le_m TTM\)). \(\langle M\rangle\mapsto\langle M'',\epsilon\rangle\) όπου η \(M''\) για είσοδο \(x\) προσομοιώνει την \(M\) στο \(x\) και: αν η \(M\) δεχτεί, δέχεται· αν η \(M\) απορρίψει, εισέρχεται σε ατέρμονο βρόχο. Τότε η \(M''\) τερματίζει στο \(\epsilon\) ανν η \(M\) δέχεται το \(\epsilon\). Άρα \(\langle M\rangle\in ETM\iff\langle M'',\epsilon\rangle\in TTM\). Αφού η \(TTM\) είναι αναγνωρίσιμη, και η \(ETM\) είναι αναγνωρίσιμη.

Θέμα Α4 / Β1 / Γ3 / Δ1: σχέσεις κλάσεων (με \(P\ne NP\))

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

  • \(P=\text{co-}P\subseteq NP\cap\text{co-}NP\), και \(P\subsetneq NP\).
  • \(NPC\subseteq NP\), \(\text{co-}NPC\subseteq\text{co-}NP\), \(NPC\cap P=\varnothing\).
  • \(NP\cup\text{co-}NP\subseteq\) Διαγνώσιμες \(\subsetneq\) Αναγνωρίσιμες (και \(\subsetneq\) Συμπληρωματικά Αναγνωρίσιμες).
  • Διαγνώσιμες = Αναγνωρίσιμες ∩ Συμπληρωματικά Αναγνωρίσιμες.
  • Ανοιχτό: \(NP\overset{?}=\text{co-}NP\) (αν \(NP\ne\text{co-}NP\) τότε \(NPC\cap\text{co-}NPC=\varnothing\) και \(NPC\ne\text{co-}NPC\)) και \(NP\cap\text{co-}NP\overset{?}=P\).

Θέμα Α5 / Β3 / Γ4 / Δ3: Σωστό/Λάθος

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

Ομάδα Α (Θέμα 5): i Σ · ii Λ · iii Σ · iv Σ · v Σ · vi Σ · vii Σ · viii Σ (π.χ. σταθερά του Chaitin) · ix Λ · x Λ (τα ΓΦΑ αναγνωρίζουν μόνο τις context-sensitive γλώσσες).

Ομάδα Β (Θέμα 3): i Λ · ii Λ · iii Σ · iv Λ · v Λ · vi Λ · vii Σ · viii Λ · ix Σ · x Λ.

Ομάδα Γ (Θέμα 4): i Λ · ii Λ · iii Λ · iv Σ · v Σ · vi Λ · vii Λ · viii Σ · ix Λ · x Σ.

Ομάδα Δ (Θέμα 3): i Σ · ii Λ · iii Σ · iv Σ · v Σ · vi Σ · vii Λ · viii Σ · ix Λ · x Λ (το σύνολο όλων των γλωσσών είναι υπεραριθμήσιμο).

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

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