2026) — Θέματα¶

Μεταγραφή των φωτογραφιών της εξέτασης 19/01/2026 (IMG-4c07… και IMG-7e6f…).

IMG-4c07736ce9b628608c5eef944fccc860-V.jpg¶

ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ «ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ» 19/01/2026 Διάρκεια Εξέτασης (2 ώρες και 30 λεπτά) Όλες οι απαντήσεις θα δοθούν στην κόλλα σας και όχι στα θέματα.

(2) Έστω η αιτοκρατική ΤΜ M με Σ = {0,1} και Γ = {0,1,␣} με τη διπλανή συνάρτηση μετάβασης. Έστω ότι η αρχική κατάσταση είναι η q0, η κατάσταση απόρριψης είναι η qr και η κατάσταση αποδοχής είναι η qa. Είναι η M διαγνώσιμη; Ποια είναι η γλώσσα που αναγνωρίζει η M; Αιτιολογήστε τις απαντήσεις σας.

[Σχήμα: διάγραμμα καταστάσεων της M με καταστάσεις q0, q1, q2, q3, qr, qa. Ετικέτες μεταβάσεων που διακρίνονται: 1→0,Δ· 0→1,Δ· 1→1,Δ· 0→0,Δ· 1→1,Α· 0→0,Α· ␣→␣,Δ· ␣→␣,Α. Υπόλοιπες ετικέτες [δυσανάγνωστο].]

(2) Έστω το πρόβλημα ΔΙΠΛΟ_SAT = {⟨φ⟩ | ο λογικός τύπος φ έχει τουλάχιστον δύο αληθοποιούς τιμοδοσίες}. Να αποδείξετε ότι το πρόβλημα ΔΙΠΛΟ_SAT είναι NP-πλήρες.
(2) Σας δίνεται η εξής γλώσσα:

\[COMPL_{TM} = \{⟨M_1, M_2⟩ : \text{η γλώσσα } L(M_1) \text{ είναι το συμπλήρωμα της γλώσσας } L(M_2)\}\]

Να συμπληρώσετε την παρακάτω απόδειξη (τα κενά κουτιά) για τη μη διαγνωσιμότητα της COMPL_TM.

Απόδειξη: Θα δείξουμε ότι η γλώσσα COMPL_TM είναι μη διαγνωσιμη κάνοντας αναγωγή από τη γνωστή μη διαγνωσιμη γλώσσα ΑΠΟΔΟΧΗ_TM. Έστω ότι η γλώσσα COMPL_TM είναι διαγνωσιμη με μηχανή Turing R που τη διαγνωρίζει. Χρησιμοποιώντας την R, κατασκευάζουμε την TM S που διαγνωρίζει τη γλώσσα ΑΠΟΔΟΧΗ_TM ως εξής:

S = για είσοδο (M, w), όπου M είναι μια TM και w μια συμβολοσειρά:

Κατασκευάστε την TM M1, η οποία για είσοδο x, αν η x έχει το ίδιο μήκος με την w τότε αποδέχεται, αλλιώς απορρίπτει.
Κατασκευάστε την TM M2, η οποία για είσοδο x: [κενό πλαίσιο συμπλήρωσης]
Εκτέλεσε την TM R με είσοδο (M1, M2).
Αν η R αποδέχεται, τότε απόρριψε.
Αν η R απορρίψει, τότε αποδέξου.

Πράγματι, η S αποτελεί διαγνώστη της γλώσσας ΑΠΟΔΟΧΗ_TM αφού: [κενό πλαίσιο συμπλήρωσης]

Πρόσθετο κείμενο στο πάνω μέρος της σελίδας και στα κενά κουτιά της απόδειξης: [δυσανάγνωστο]

IMG-7e6ffb623e18fb2f3b0b237775d54a3f-V.jpg¶

(2)

(α) (1) Να αποδείξετε ότι η κλάση NP είναι κλειστή ως προς την πράξη της ένωσης.

(β) (1) Να δώσετε με σχήμα όσες σχέσεις γνωρίζετε που έχουν (αν περιέχονται ή είναι ίσες) οι παρακάτω κλάσεις πολυπλοκότητας δεδομένου ότι \(P \neq NP\): \(P\), Διαγνώσιμες Γλώσσες, \(co-P\), \(NP\), \(co-NP\), \(NPC\), \(co-NPC\), Αναγνωρίσιμες Γλώσσες, \(TIME(n^{1024})\). (το πρόθεμα co σημαίνει συμπλήρωμα της κλάσης ενώ NPC είναι η κλάση των NP-πλήρων προβλημάτων)

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

i. Αν ένα NP-πλήρες πρόβλημα λύνεται σε πολυωνυμικό χρόνο, τότε \(P = NP\).

ii. Μια μηχανή Turing με ταινία που εκτείνεται άπειρα προς μια κατεύθυνση είναι ισοδύναμη σε υπολογιστική ισχύ με μια μηχανή Turing με ταινία που εκτείνεται άπειρα προς τις δύο κατευθύνσεις.

iii. Το πρόβλημα Αποδοχής είναι ένα παράδειγμα προβλήματος που δεν μπορεί να επιλυθεί.

iv. Εάν ένα πρόβλημα Α ανάγεται στο Β και το Β είναι διαγνώσιμο, τότε και το Α πρέπει επίσης να είναι διαγνώσιμο.

v. Η κλάση πολυπλοκότητας NP αποτελείται από προβλήματα απόφασης για τα οποία μια λύση μπορεί να επαληθευτεί σε πολυωνυμικό χρόνο από μια ντετερμινιστική μηχανή Turing.

vi. Κάθε πρόβλημα στην κλάση NP είναι επίσης στην κλάση P.

vii. Η θέση των Church-Turing δεν έχει αποδειχθεί μαθηματικά.

viii. Μια μη ντετερμινιστική μηχανή Turing μπορεί να λύσει περισσότερα προβλήματα από μια ντετερμινιστική μηχανή Turing.

ix. Το 2-SAT είναι NP-πλήρες.

x. [δυσανάγνωστο: ο αριθμός του ερωτήματος καλύπτεται από το χέρι στη φωτογραφία] Μια γλώσσα L είναι μη-διαγνώσιμη εάν υπάρχει αναγωγή από την L στο πρόβλημα Τερματισμού.

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

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