Υπολογιστική Πολυπλοκότητα — Σεπτέμβριος 2021 — Ηλεκτρονική εξέταση (πολλαπλής επιλογής και συμπλήρωσης κενών)¶

Μεταγραφή των στιγμιοτύπων της ηλεκτρονικής εξέτασης Σεπτεμβρίου 2021 (ερωτήσεις 1–4 και στοιχεία (στ)).

196499504_419727176242904_6444715863322572547_n.jpg¶

Έστω το εξής πρόβλημα: $AK2SAT = \{\langle \phi, n, m \rangle :$ υπάρχει τιμοδοσία που ικανοποιεί τουλάχιστον $n$ και το πολύ $m$ φράσεις του $2SAT$ λογικού τύπου $\phi\}$. Θέλουμε να δείξουμε ότι το πρόβλημα $AK2SAT$ είναι NP-πλήρες.

Το πρώτο βήμα είναι να δείξουμε ότι το πρόβλημα $AK2SAT$ ανήκει στη κλάση _____ (1). Αυτό μπορούμε να το κάνουμε με δύο τρόπους: α) να κατασκευάσουμε έναν αιτιοκρατικό πολυωνυμικό _____ (2) όπου το πιστοποιητικό θα είναι _____ (3). Αυτό το πιστοποιητικό έχει _____ (4) μέγεθος και μπορούμε να το ελέγξουμε αποδοτικά. β) να κατασκευάσουμε _____ (5) ΤΜ που σε _____ (6) χρόνο να λύνει το πρόβλημα.

Το δεύτερο βήμα είναι να [δυσανάγνωστο] πρόβλημα από το οποίο θα κάνουμε αναγωγή. Θα επιλέξουμε να αποδείξουμε πολύ εύκολα την NP-πληρότητα του προβλήματος $AK2SAT$ [δυσανάγνωστο] περιορισμό. Το πρόβλημα που επιλέγουμε για να αποτελέσει περιορισμό του $AK2SAT$ είναι το (δώστε πλήρη ορισμό του προβλήματος) _____ (7), το οποίο γνωρίζουμε ήδη ότι είναι NP-πλήρες. Πράγματι, αν _____ (8) τότε το πρόβλημα $AK2SAT$ μετασχηματίζεται σε αυτό που δόθηκε στο (7). Άρα το πρόβλημα $AK2SAT$ είναι NP-πλήρες.

Ερώτηση 2 (Πολλαπλής Επιλογής (Πολλαπλές Απαντήσεις) — 1 βαθμός)

Θεωρήστε την παρακάτω αναγωγή $f$ από το πρόβλημα ΧΑΜΙΛΤΟΝΙΑΝΟΣΚΥΚΛΟΣ στο πρόβλημα ΧΑΜΙΛΤΟΝΙΑΝΗΔΙΑΔΡΟΜΗ. Επιλέξτε τις σωστές προτάσεις.

ΧΑΜΙΛΤΟΝΙΑΝΟΣΚΥΚΛΟΣ: Δίνεται κατευθυνόμενο γράφημα $G$. Υπάρχει κατευθυνόμενος κύκλος που περνά από κάθε κόμβο του γραφήματος $G$ ακριβώς μια φορά;

ΧΑΜΙΛΤΟΝΙΑΝΗΔΙΑΔΡΟΜΗ: Δίνεται κατευθυνόμενο γράφημα $H$ και δύο κόμβοι του $s$ και $t$. Υπάρχει διαδρομή από τον κόμβο $s$ στον κόμβο $t$ που περνά από κάθε κόμβο του γραφήματος $H$ ακριβώς μια φορά;

Αναγωγή $f$: Με είσοδο το κατευθυνόμενο γράφημα $G$, η $f$ επιστρέφει ως γράφημα $H$ το ίδιο γράφημα $G$ καθώς και δύο αυθαίρετους αλλά διαφορετικούς κόμβους $s$ και $t$.

Αποσαφήνιση: Ένα ΝΑΙ-Στιγμιότυπο ενός προβλήματος είναι ένα στιγμιότυπο που ανήκει στην αντίστοιχη γλώσσα (π.χ., ένα ΝΑΙ-στιγμιότυπο της ΧΑΜΙΛΤΟΝΙΑΝΗΔΙΑΔΡΟΜΗΣ είναι ένα γράφημα που έχει Χαμιλτονιανή διαδρομή). Αντίστοιχα ορίζεται και ένα ΟΧΙ-στιγμιότυπο.

[ ] Είναι αναγωγή πολυωνυμικού χρόνου.
[ ] Η αναγωγή δεν είναι πολυωνυμικού χρόνου.
[ ] Η αναγωγή δεν είναι σωστή καθώς υπάρχει ΝΑΙ-στιγμιότυπο του προβλήματος ΧΑΜΙΛΤΟΝΙΑΝΟΣΚΥΚΛΟΣ που αντιστοιχίζεται σε ΟΧΙ-στιγμιότυπο του προβλήματος ΧΑΜΙΛΤΟΝΙΑΝΗΔΙΑΔΡΟΜΗ.

[Λείπει από τη φωτογραφία: τυχόν επιλογές κάτω από το κάτω άκρο της εικόνας] Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

204851457_322122866306888_3159914450605309948_n.jpg¶

Ερώτηση 1 (Συμπλήρωση Κενών (Χαλαρή Ταυτοποίηση) — 2 βαθμοί)

Έστω το εξής πρόβλημα: $UL2SAT = \{\langle \phi, l, u \rangle : \text{υπάρχει τιμοδοσία που ικανοποιεί τουλάχιστον } l \text{ και το πολύ } u \text{ φράσεις του } 2SAT \text{ λογικού τύπου } \phi\}$. Θέλουμε να δείξουμε ότι το πρόβλημα $UL2SAT$ είναι NP-πλήρες.

Το πρώτο βήμα είναι να δείξουμε ότι το πρόβλημα $UL2SAT$ ανήκει στη κλάση _____ (1). Αυτό μπορούμε να το κάνουμε με δύο τρόπους: α) να κατασκευάσουμε έναν αιτιοκρατικό πολυωνυμικό

_____ (2) όπου το πιστοποιητικό θα είναι _____ (3). Αυτό το πιστοποιητικό έχει

_____ (4) μέγεθος και μπορούμε να το ελέγξουμε αποδοτικά. β) να κατασκευάσουμε μία

_____ (5) TM που σε _____ (6) χρόνο να λύνει το πρόβλημα. Το δεύτερο βήμα

είναι να βρούμε το κατάλληλο πρόβλημα από το οποίο θα κάνουμε αναγωγή. Θα επιλέξουμε να αποδείξουμε πολύ εύκολα την NP-πληρότητα του προβλήματος $UL2SAT$ με περιορισμό. Το πρόβλημα που επιλέγουμε για να αποτελέσει

περιορισμό του $UL2SAT$ είναι το (δώστε πλήρη ορισμό του προβλήματος) _____ (7), το οποίο γνωρίζουμε ήδη ότι είναι NP-πλήρες. Πράγματι, αν _____ (8) τότε το πρόβλημα $UL2SAT$ μετασχηματίζεται σε αυτό που δόθηκε στο (7). Άρα το πρόβλημα $UL2SAT$ είναι NP-πλήρες.

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

Ερώτηση 2 (Πολλαπλής Επιλογής (Πολλαπλές Απαντήσεις) — 1 βαθμός)

Θεωρήστε την παρακάτω αναγωγή $f$ από το πρόβλημα ΚΟΜΒΙΚΟΚΑΛΥΜΜΑ στο πρόβλημα ΚΥΡΙΑΡΧΟΣΥΝΟΛΟ. Επιλέξτε τις σωστές προτάσεις.

[Λείπει από τη φωτογραφία: το υπόλοιπο κείμενο της ερώτησης και οι επιλογές· βλ. την ενότητα για 203581992_1219362141826975_426672005690586103_n.jpg]

a2.jpg¶

Ερώτηση 1 (Συμπλήρωση Κενών (Χαλαρή Ταυτοποίηση) — 2 βαθμοί)

Έστω μία συλλογή συνόλων $\{P_1, P_2, \ldots, P_m\}$ έτσι ώστε για κάθε $i$ να ισχύει ότι το $P_i$ είναι υποσύνολο ενός συνόλου $X$. Έστω το εξής πρόβλημα: $ULSC = {(X, {P_1, P_2, \ldots, P_m}, p, q) : υπάρχει μία συλλογή από τουλάχιστον $p$ και το πολύ $q$ υποσύνολα $P_i$ του $X$ των οποίων η ένωση δίνει το $X\}$. Θέλουμε να δείξουμε ότι το πρόβλημα $ULSC$ είναι NP-πλήρες.

Το πρώτο βήμα είναι να δείξουμε ότι το πρόβλημα $ULSC$ ανήκει στη κλάση _____ (1). Αυτό μπορούμε να το κάνουμε με δύο τρόπους: α) να κατασκευάσουμε μία _____ (2) TM που σε _____ (3) χρόνο να λύνει το πρόβλημα ή β) να κατασκευάσουμε έναν αιτιοκρατικό πολυωνυμικό _____ (4) όπου το πιστοποιητικό θα είναι _____ (5). Αυτό το πιστοποιητικό έχει _____ (6) μέγεθος και μπορούμε να το ελέγξουμε αποδοτικά.

Το δεύτερο βήμα είναι να βρούμε το κατάλληλο πρόβλημα από το οποίο θα κάνουμε αναγωγή. Θα επιλέξουμε να αποδείξουμε πολύ εύκολα την NP-πληρότητα του προβλήματος $ULSC$ με περιορισμό. Το πρόβλημα που επιλέγουμε για να αποτελέσει περιορισμό του $ULSC$ είναι το (δώστε πλήρη ορισμό του προβλήματος) _____ (7), το οποίο γνωρίζουμε ήδη ότι είναι NP-πλήρες. Πράγματι, αν _____ (8) τότε το πρόβλημα $ULSC$ μετασχηματίζεται σε αυτό που δόθηκε στο (7). Άρα το πρόβλημα $ULSC$ είναι NP-πλήρες.

Screenshot_614.png¶

Ερώτηση 1 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.30 βαθμοί)

Έστω ότι υπάρχει πολυωνυμικός αιτιοκρατικός αλγόριθμος για την εύρεση μίας τιμοδοσίας σε ένα λογικό τύπο σε κανονική συζευκτική μορφή. Σε αυτή την περίπτωση να αναφέρετε ποιο από τα παρακάτω 4 διαγράμματα περιγράφει σωστά τις σχέσεις μεταξύ των κλάσεων P, NP και NPC.

[Σχήμα (α): έλλειψη με την ετικέτα «P=NP=NPC»]

[Σχήμα (β): δύο τέμνοντες κύκλοι· αριστερά «NP», στην τομή «NPC», δεξιά «P»]

[Σχήμα (γ): μεγάλη έλλειψη με την ετικέτα «NP=P» και μέσα της μικρότερη έλλειψη με την ετικέτα «NPC»]

[Σχήμα (δ): τρεις εγκλειόμενες ελλείψεις· η εξωτερική με ετικέτα «NP» (αριστερά), η μεσαία με ετικέτα «P», η εσωτερική με ετικέτα «NPC»]

[ ] (α)
[ ] (β)
[ ] (γ)
[ ] (δ)

a1.jpg¶

Ερώτηση 2 (Πολλαπλής Επιλογής (Πολλαπλές Απαντήσεις) — 1 βαθμός)

Θεωρήστε την παρακάτω αναγωγή $f$ από το πρόβλημα ΧΑΜΙΛΤΟΝΙΑΝΟΣΚΥΚΛΟΣ στο πρόβλημα ΜΑΚΡΥΤΕΡΗΔΙΑΔΡΟΜΗ. Επιλέξτε τις σωστές προτάσεις.

ΧΑΜΙΛΤΟΝΙΑΝΟΣΚΥΚΛΟΣ: Δίνεται μη-κατευθυνόμενο γράφημα $G$. Υπάρχει μη-κατευθυνόμενος κύκλος που περνά από κάθε κόμβο του γραφήματος $G$ ακριβώς μια φορά;

ΜΑΚΡΥΤΕΡΗΔΙΑΔΡΟΜΗ: Δίνεται μη-κατευθυνόμενο γράφημα $H$ και δύο κόμβοι $s$ και $t$ και ένας ακέραιος $k$. Υπάρχει απλή διαδρομή (δεν απαναλαμβάνονται κόμβοι) από τον κόμβο $s$ στον κόμβο $t$ μήκους τουλάχιστον $k$; Το μήκος μίας διαδρομής είναι ίσο με το πλήθος των ακμών που διαπερνά.

Αναγωγή $f$: Με είσοδο το μη-κατευθυνόμενο γράφημα $G$, η $f$ επιστρέφει ως έξοδο το γράφημα $H$ στο ίδιο γράφημα $G$ καθώς και δύο αυθαίρετους αλλά διαφορετικούς κόμβους $s$ και $t$. Επίσης, αν $n$ είναι το πλήθος των κόμβων του $G$, τότε η $f$ θέτει $k = n - 1$.

Αποσαφήνιση: Ένα ΝΑΙ-στιγμιότυπο ενός προβλήματος είναι ένα στιγμιότυπο που ανήκει στην αντίστοιχη γλώσσα (π.χ., ένα ΝΑΙ-στιγμιότυπο της ΧΑΜΙΛΤΟΝΙΑΝΗΔΙΑΔΡΟΜΗΣ είναι ένα γράφημα που έχει Χαμιλτονική διαδρομή). Αντίστοιχα ορίζεται και ένα ΟΧΙ-στιγμιότυπο.

[ ] Είναι αναγωγή πολυωνυμικού χρόνου.
[ ] Η αναγωγή δεν είναι πολυωνυμικού χρόνου.
[ ] Η αναγωγή δεν είναι σωστή καθώς υπάρχει ΝΑΙ-στιγμιότυπο του προβλήματος ΧΑΜΙΛΤΟΝΙΑΝΟΣΚΥΚΛΟΣ που αντιστοιχίζεται σε ΟΧΙ-στιγμιότυπο του προβλήματος ΜΑΚΡΥΤΕΡΗΔΙΑΔΡΟΜΗ.
[ ] Η αναγωγή δεν είναι σωστή καθώς υπάρχει ΟΧΙ-στιγμιότυπο του προβλήματος ΧΑΜΙΛΤΟΝΙΑΝΟΣΚΥΚΛΟΣ που αντιστοιχίζεται σε ΝΑΙ-στιγμιότυπο του προβλήματος ΜΑΚΡΥΤΕΡΗΔΙΑΔΡΟΜΗ.

Capture.PNG¶

[στιγμιότυπο οθόνης ηλεκτρονικής εξέτασης· η κεφαλίδα του μαθήματος δεν φαίνεται]

Ερώτηση 2 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.50 βαθμοί)

Έστω ότι ο προϊστάμενος μας σε μία εταιρία σας ζητάει να του φτιάξετε ένα πρόγραμμα που να λύνει ένα μη-διαγνώσιμο πρόβλημα Π. Τι θα του απαντήσετε από τα παρακάτω;

[ ] Το πρόβλημα είναι μη διαγνώσιμο. Δεν λύνεται. Τέλος!
[ ] Και επειδή είναι μη-διαγνώσιμο και τί έγινε; Θα σου φέρω το προγραμματάκι που να το λύνει εντός του μήνα!
[ ] Θα σου φέρω ένα πρόγραμμα, αλλά μερικές φορές μπορεί να σου απαντήσει λάθος. Πάντως, επειδή το πρόβλημα είναι μη-διαγνώσιμο, μείωση μισθού δεν θα δεχθώ!
[ ] Καμία επιλογή.

203390370_180211090717804_8028792376647987842_n.png¶

[Στιγμιότυπο οθόνης ηλεκτρονικής εξέτασης (πλατφόρμα εξετάσεων του eClass). Η αρχή και το τέλος της σελίδας είναι κομμένα.]

[Λείπει από τη φωτογραφία: η αρχή της ερώτησης και οι επιλογές που προηγούνται της (στ)]

(στ) SPACE(n²)

[ ] Καμία Επιλογή.

Ερώτηση 2 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.30 βαθμοί)

Η κλάση προβλημάτων απόφασης που μπορούν να λυθούν από ανταιτιοκρατικούς πολυωνυμικούς αλγόριθμ[δυσανάγνωστο] είναι η:

[ ] κλάση P
[ ] κλάση των NP-δυσχερών προβλημάτων
[ ] κλάση NPC
[ ] κλάση NP
[ ] Καμία Επιλογή.

Ερώτηση 3 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.30 βαθμοί)

Έστω ότι μία αιτιοκρατική ΤΜ μπορεί να προσομοιώσει μία ανταιτιοκρατική ΤΜ σε πολυωνυμικό χρόνο. Ποια από τις παρακάτω προτάσεις είναι αληθής;

[ ] Η κλάση P δεν συμπίπτει με την κλάση NP
[ ] Η κλάση NP δεν συμπίπτει με την κλάση coNP
[ ] Η κλάση P συμπίπτει με την κλάση NP
[ ] Η κλάση NPC συμπίπτει με την κλάση NP – P
[ ] Καμία Επιλογή.

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

204696492_524497061924865_1988373232113366332_n.png¶

Ερώτηση 3 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.30 βαθμοί)

Το συμπλήρωμα όλων των γλωσσών που ανήκουν στην κλάση PSPACE ανήκει στη κλάση: - [ ] PSPACE - [ ] NP - [ ] P - [ ] coNP - [ ] Καμία επιλογή.

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

203581992_1219362141826975_426672005690586103_n.jpg¶

Ερώτηση 2 (Πολλαπλής Επιλογής (Πολλαπλές Απαντήσεις) — 1 βαθμός)

[Η κεφαλίδα της ερώτησης δεν φαίνεται στη φωτογραφία· πρόκειται για την ίδια ερώτηση με την ενότητα 204851457_322122866306888_3159914450605309948_n.jpg]

Θεωρήστε την παρακάτω αναγωγή f από το πρόβλημα ΚΟΜΒΙΚΟΚΑΛΥΜΜΑ στο πρόβλημα ΚΥΡΙΑΡΧΟΣΥΝΟΛΟ. Επιλέξτε τις σωστές προτάσεις.

ΚΟΜΒΙΚΟΚΑΛΥΜΜΑ: Δίνεται μη-κατευθυνόμενο γράφημα G και ακέραιος k. Υπάρχει κομβικό κάλυμμα μεγέθους k στο γράφημα G; Υπενθυμίζεται ότι κομβικό κάλυμμα σε ένα γράφημα είναι ένα σύνολο κόμβων S ώστε κάθε ακμή του γραφήματος να έχει τουλάχιστον ένα άκρο στο σύνολο S.

ΚΥΡΙΑΡΧΟΣΥΝΟΛΟ: Δίνεται μη-κατευθυνόμενο γράφημα H και ακέραιος k'. Υπάρχει σύνολο S με k' κόμβους ώστε κάθε κόμβος του γραφήματος H είτε να ανήκει στο S είτε να είναι γειτονικός με κόμβο που ανήκει στο S;

Αναγωγή f: Με είσοδο το ζευγάρι G, k που αποτελείται από ένα γράφημα G και έναν ακέραιο k, η f επιστρέφει το ζευγάρι H, k', όπου k' = k και H είναι το γράφημα που έχει όλους τους κόμβους του γραφήματος G και, για κάθε ακμή (u, v) του γραφήματος G, έναν επιπλέον κόμβο z_uv και ακμές (u, z_uv) και (v, z_uv), όπως φαίνεται στο παρακάτω σχήμα:

Αποσαφήνιση: Ένα ΝΑΙ-στιγμιότυπο ενός προβλήματος είναι ένα στιγμιότυπο που ανήκει στην αντίστοιχη γλώσσα (π.χ., ένα ΝΑΙ-στιγμιότυπο του ΚΟΜΒΙΚΟΚΑΛΥΜΜΑ είναι ένα γράφημα που έχει κομβικό κάλυμμα μεγέθους k). Αντίστοιχα ορίζεται και ένα ΟΧΙ-στιγμιότυπο.

[Σχήμα: αριστερά "Γράφημα G" με κορυφές v (πάνω) και u (κάτω) και ακμή μεταξύ τους. Δεξιά "Γράφημα H" με κορυφές v (πάνω), u (κάτω) και ενδιάμεση κορυφή z_uv που συνδέεται με τις v και u. Βέλος από το G προς το H.]

[ ] Είναι αναγωγή πολυωνυμικού χρόνου.
[ ] Δεν είναι αναγωγή πολυωνυμικού χρόνου.
[ ] Η αναγωγή δεν είναι σωστή καθώς υπάρχει ΝΑΙ-στιγμιότυπο του προβλήματος ΚΟΜΒΙΚΟΚΑΛΥΜΜΑ που [Λείπει από τη φωτογραφία: το υπόλοιπο κείμενο της επιλογής]

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

Screenshot_617.png¶

Ερώτηση 4 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.30 βαθμοί) (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.30 βαθμοί)

Έστω ότι ο φοιτητής Α σχεδίασε μία απεικονιστική αναγωγή πολυωνυμικού χρόνου από ένα πρόβλημα Q1 στο 3SAT και ο φοιτητής Β μια πολυωνυμική αναγωγή από το 3SAT στο Q2. Ποια από τις παρακάτω προτάσεις είναι αληθής;

[ ] το Q1 ανήκει στην NP, το Q2 είναι NP-δυσχερές
[ ] το Q2 ανήκει στην NP, το Q1 είναι NP-δυσχερές
[ ] τα Q1 και Q2 ανήκουν στην κλάση NP
[ ] τα Q1 και Q2 είναι NP-δυσχερή

[Λείπει από τη φωτογραφία: το επόμενο ερώτημα, κομμένο στο κάτω άκρο]

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

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: migrated from previous_exams.md (Antigravity, 2026-10)

Προσοχή

Η απάντηση μεταφέρεται από το παλιό αρχείο για την ίδια διατύπωση ερώτησης· δεν επαληθεύτηκε χωριστά για τη σύνοδο Σεπτεμβρίου 2021. Οι υπόλοιπες παλιές απαντήσεις που αφορούν τη σύνοδο δεν μεταφέρθηκαν, επειδή στο παλιό αρχείο ανακατεύονται με εκφωνήσεις ή αφορούν άλλη σύνοδο (π.χ. η απάντηση «2SAT» για ερώτηση περί μη NP-δυσχερών προβλημάτων).

Λύσεις — Υπολογιστική Πολυπλοκότητα — Σεπτέμβριος 2021 — Ηλεκτρονική εξέταση (πολλαπλής επιλογής και συμπλήρωσης κενών)¶

Ερώτηση 1 (διαγράμματα P, NP, NPC, ίδια διατύπωση με την ερώτηση 1 της εξέτασης Ιουνίου 2021): α.

Απάντηση:Το α

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

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