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

Υπολογιστική Πολυπλοκότητα — Ιούνιος 2021 — Ασκήσεις (γραπτή εξέταση)

Μεταγραφή του αρχείου Ypologistiki_Ioun21.pdf (ΘΕΜΑΤΑ ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΙΟΥΝΙΟΣ 21).

Ypologistiki_Ioun21.pdf

ΘΕΜΑΤΑ ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΙΟΥΝΙΟΣ 21

ΑΣΚΗΣΗ 1: Γενικές ερωτήσεις σε ΤΜ και γλώσσες

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

Για τη γλώσσα \(L = \{a^n b^n : n \ge 0\}\), ένας απαριθμητής θα εκτυπώσει:
Με \(\epsilon\) αναπαριστούμε την κενή λέξη.

  • [ ] \(a^n b^n\)
  • [ ] \(\{ab, a^2 b^2, a^3 b^3, \dots\}\)
  • [ ] \(\{\epsilon, ab, a^2 b^2, a^3 b^3, \dots\}\)
  • [ ] Καμία επιλογή.

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

Μπορεί μια μηχανή Turing να διαβάσει στο δεύτερο βήμα της λειτουργίας της σύμβολο που δεν ανήκει στο αλφάβητο εισόδου και δεν είναι το κενό;

  • [ ] Ναι, αν το είχε γράψει στο προηγούμενο βήμα και μετακίνησε την κεφαλή δεξιά.
  • [ ] Όχι, αυτό δεν μπορεί να συμβεί ποτέ.
  • [ ] Ναι, αν το είχε γράψει στο προηγούμενο βήμα και μετακίνησε την κεφαλή αριστερά.
  • [ ] Καμία Επιλογή, δεν έχει αρνητική βαθμολογία.

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

Δώστε παράδειγμα διαγνώσιμων γλωσσών που η ένωσή τους είναι μη διαγνώσιμη γλώσσα.

  • [ ] Οι γλώσσες \(\emptyset\) και \(\Sigma^*\).
  • [ ] Οι γλώσσες ΑΠΟΔΟΧΗ/TM και ΚΕΝΟΤΗΤΑ/TM.
  • [ ] Δεν υπάρχει τέτοιο παράδειγμα.
  • [ ] Καμία Επιλογή.

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

Η \(L_1\) είναι μία αναγνωρίσιμη γλώσσα στο αλφάβητο \(\Sigma\). Ένας αλγόριθμος \(A\) απαριθμεί όλες τις λέξεις της \(L_1\) - έστω \(w_1, w_2, w_3, \dots\). Ορίζουμε μία άλλη γλώσσα \(L_2\) στο \(\Sigma \cup \{\#\}\) ως εξής: \(\{w_i \# w_j : w_i, w_j \in L_1, i < j\}\). Το σύμβολο \(\#\) είναι ένα νέο σύμβολο. Έστω οι επόμενοι δύο ισχυρισμοί \(S_1\) και \(S_2\). \(S_1\): Αν η \(L_1\) είναι διαγνώσιμη τότε και \(L_2\) είναι διαγνώσιμη. \(S_2\): Αν η \(L_2\) είναι διαγνώσιμη τότε και η \(L_1\) είναι διαγνώσιμη. Ποια από τις παρακάτω προτάσεις είναι αληθής;

  • [ ] Και οι δύο ισχυρισμοί είναι αληθείς.
  • [ ] Ο \(S_1\) είναι αληθής αλλά ο \(S_2\) δεν είναι απαραίτητα αληθής.
  • [ ] Ο \(S_2\) είναι αληθής αλλά ο \(S_1\) δεν είναι απαραίτητα αληθής.
  • [ ] Και οι δύο δεν είναι απαραίτητα αληθείς.
  • [ ] Καμία επιλογή.

ΑΣΚΗΣΗ 2: Περιγραφή δοθείσας ΤΜ (2,5 βαθμοί)

Δίνεται η μηχανή Turing του σχήματος. Να συμπληρώσετε τα κενά με τις κατάλληλες επιλογές.
Με είσοδο aa, η TM ___________ (επιλογή από (1)-(3)). Η TM ___________ (επιλογή από (4)-(5)) διότι ___________ (επιλογή από (6)-(7)). Η γλώσσα της ΤΜ είναι η ___________ (επιλογή από (8)-(11)). (Με ε αναπαριστούμε την κενή λέξη)

[Σχήμα: Διάγραμμα καταστάσεων μηχανής Turing με καταστάσεις \(q_0, q_1, q_2, q_3, q_{\text{ΝΑΙ}}, q_{\text{ΟΧΙ}}\) και μεταβάσεις: \(q_0 \xrightarrow{a \to \Delta} q_1\), \(q_0 \xrightarrow{\sqcup \to a, \Lambda} q_2\), \(q_1 \xrightarrow{a \to \Delta} q_2\), \(q_1 \xrightarrow{\sqcup \to a, \Delta} q_{\text{ΟΧΙ}}\), \(q_2 \xrightarrow{a \to \Delta} q_3\), \(q_2 \xrightarrow{\sqcup \to a, \Lambda} q_3\), \(q_3 \xrightarrow{a \to \Delta} q_0\), \(q_3 \xrightarrow{\sqcup \to \Lambda} q_{\text{ΝΑΙ}}\).]

  • [ ] (1) αποδέχεται
  • [ ] (2) απορρίπτει
  • [ ] (3) εγκλωβίζεται
  • [ ] (4) είναι διαγνώστης
  • [ ] (5) δεν είναι διαγνώστης
  • [ ] (6) τερματίζει σε οποιαδήποτε συμβολοσειρά
  • [ ] (7) εγκλωβίζεται σε κάποια συμβολοσειρά
  • [ ] \(\epsilon + aa(aaaa)^*\)
  • [ ] \(a + aaa(aaaa)^*\)
  • [ ] \(\epsilon + aaaaa(aaa)^*\) [δυσανάγνωστο: η τρίτη επιλογή στη φωτογραφία με χαμηλή ανάλυση]

    [Λείπει από τη φωτογραφία: η ερώτηση αναφέρει επιλογές (8)-(11), αλλά εμφανίζονται μόνο τρεις· η τέταρτη επιλογή δεν είναι ορατή στη σελίδα.]

ΑΣΚΗΣΗ 3: Απόδειξη Μη-Διαγνωστιμότητας

Το παρακάτω αποτελεί τμήμα απόδειξης ότι η γλώσσα B είναι μη διαγνώσιμη χρησιμοποιώντας αναγωγή από τη γλώσσα A.

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

S = για είσοδο 1. Κατασκεύασε την TM M' που λειτουργεί ως εξής M' = για είσοδο x 1. Αν x = "aaa", τότε αποδέξου 2. Αλλιώς, αν x != "aaa", τότε προσομοίωσε την TM M με είσοδο w 3. Αν η M αποδεχτεί, τότε αποδέξου 4. Αν η M απορρίψει, τότε απόρριψε 2. Εκτέλεσε την TM R με είσοδο <M'> 3. Αν η R αποδεχτεί, τότε απόρριψε 4. Αν η R απορρίψει, τότε αποδέξου

Καθώς γνωρίζουμε ότι η γλώσσα A είναι μη διαγνώσιμη, καταλήγουμε σε άτοπο. Έτσι, έχουμε αποδείξει ότι, αντίθετα με την υπόθεσή μας, η γλώσσα B είναι μη διαγνώσιμη.

Από την παραπάνω απόδειξη, έχει παραληφθεί η απόδειξη ορθότητας της S (δηλαδή, ότι είναι πράγματι διαγνώστης της γλώσσας A). Σημειώστε ποιοι από τους παρακάτω συνδυασμούς για τις γλώσσες A και B οδηγούν σε σωστή αναγωγή.

  • [ ] A = ΠΕΡΑΤΩΣΗ/ΤΜ και B = {: η M είναι TM που δεν τερματίζει με είσοδο την κενή συμβολοσειρά}
  • [ ] A = ΑΠΟΔΟΧΗ/ΤΜ και B = ΚΕΝΟΤΗΤΑ/ΤΜ
  • [ ] A = ΑΠΟΔΟΧΗ/ΤΜ και B = {: η M είναι TM που τερματίζει για ακριβώς μια είσοδο}
  • [ ] A = ΑΠΟΔΟΧΗ/ΤΜ και B = {: η M είναι TM που αποδέχεται την κενή συμβολοσειρά}
  • [ ] A = ΑΠΟΔΟΧΗ/ΤΜ και B = {: η M είναι TM με |L(M)| = 1}

ΑΣΚΗΣΗ 4: Γενικές ασκήσεις πολυπλοκότητας

Κάθε ετικέτα στο παρακάτω διάγραμμα εγκλεισμού κλάσεων αντιστοιχεί σε μία κλάση υπολογισιμότητας ή πολυπλοκότητας. Με δεδομένο ότι \(P \neq NP\), να επιλέξετε τη σωστή αντιστοίχιση που να σέβεται τις σχέσεις εγκλεισμού.

Το πρόθεμα co στην κλάση X αντιστοιχεί στο συμπλήρωμα της κλάσης X.

[Σχήμα: Εγκλειόμενα ελλειπτικά σχήματα με ετικέτες α, β, γ, δ, ε, στ, με τα ονόματα των κλάσεων στις θέσεις α–στ όπως ακολουθούν.]

  • [ ] (α) διαγνώσιμη (β) \(EXPTIME\) (γ) \(\text{co}NP\) (δ) \(NTIME(n^2)\) (ε) \(NP\) (στ) \(SPACE(n^3)\)
  • [ ] (α) \(PSPACE\) (β) \(EXPTIME\) (γ) \(\text{co}NP\) (δ) \(\text{co}P\) (ε) \(NP\) (στ) \(NTIME(n^3)\)
  • [ ] (α) \(EXPTIME\) (β) \(NPSPACE\) (γ) \(P\) (δ) \(NSPACE(n^3)\) (ε) \(NP\) (στ) \(NTIME(n^2)\)
  • [ ] (α) \(EXPTIME\) (β) \(NPSPACE\) (γ) \(\text{co}NP\) (δ) \(P\) (ε) \(DTIME(n^4)\) (στ) \(DTIME(n^3)\)

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

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

α) : Δοθέντος γραφήματος \(G(V, E)\), έχει το \(G\) κλίκα μεγέθους \(\frac{|V|}{2}\);
β) : Δοθέντος γραφήματος \(G(V, E)\), έχει το \(G\) κλίκα μεγέθους 4;

  • [ ] Τα (α) και (β) είναι \(NP\)-πλήρη προβλήματα.
  • [ ] Το (α) είναι \(NP\)-πλήρες ενώ (β) ανήκει στο \(P\).
  • [ ] Το (β) είναι \(NP\)-πλήρες ενώ (α) ανήκει στο \(P\).
  • [ ] Τα (α) και (β) ανήκουν στο \(P\).
  • [ ] Καμία επιλογή.

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

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

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

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

Ζητήθηκε από δύο φοιτητές A και B να αποδείξουν ότι ένα πρόβλημα \(\Pi\) είναι NP-πλήρες. Ο A δίνει μία απεικονιστική αναγωγή πολυωνυμικού χρόνου από το 3SAT στο \(\Pi\) ενώ ο B από το \(\Pi\) στο 3SAT. Ποιο είναι το συμπέρασμα που μπορούμε να βγάλουμε από αυτές τις αναγωγές;

  • [ ] το \(\Pi\) είναι NP-δυσχερές αλλά όχι NP-πλήρες
  • [ ] το \(\Pi\) ανήκει στην NP αλλά δεν είναι NP-πλήρες
  • [ ] το \(\Pi\) είναι NP-πλήρες
  • [ ] το \(\Pi\) δεν ανήκει στην NP και δεν είναι NP-πλήρες
  • [ ] Καμία Επιλογή

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

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

[Σχήμα: Τέσσερα διαγράμματα: (α) Ένας κύκλος με ένδειξη P=NP=NPC. (β) Δύο επικαλυπτόμενοι κύκλοι με ετικέτες NP και P, και NPC στην τομή τους. (γ) Κύκλος NP=P που περιέχει μικρότερο κύκλο NPC. (δ) Κύκλος NP που περιέχει έναν κύκλο NPC και έναν κύκλο P.]

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

ΑΣΚΗΣΗ 5: Απόδειξη NP-πληρότητας

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

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

Το πρώτο βήμα είναι να δείξουμε ότι το πρόβλημα \(ULSC\) ανήκει στη κλάση [ ] (1). Αυτό μπορούμε να το κάνουμε με δύο τρόπους: α) να κατασκευάσουμε μία [ ] (2) ΤΜ που σε [ ] (3) χρόνο να λύνει το πρόβλημα ή β) να κατασκευάσουμε έναν αιτιοκρατικό πολυωνυμικό [ ] (4) όπου το πιστοποιητικό θα είναι [ ] (5). Αυτό το πιστοποιητικό έχει [ ] (6) μέγεθος και μπορούμε να το ελέγξουμε αποδοτικά. Το δεύτερο βήμα είναι να βρούμε το κατάλληλο πρόβλημα από το οποίο θα κάνουμε αναγωγή. Θα επιλέξουμε να αποδείξουμε πολύ εύκολα την NP-πληρότητα του προβλήματος \(ULSC\) με περιορισμό. Το πρόβλημα που επιλέγουμε για να αποτελέσει περιορισμό του \(ULSC\) είναι το (δώστε πλήρη ορισμό του προβλήματος): [ ] (7) το οποίο γνωρίζουμε ήδη ότι είναι NP-πλήρες. Πράγματι, αν [ ] (8) τότε το πρόβλημα \(ULSC\) μετασχηματίζεται σε αυτό που δόθηκε στο (7). Άρα το πρόβλημα \(ULSC\) είναι NP-πλήρες.

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

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

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

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

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

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

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

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2021-06.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): compcomp_1.jpg

Λύσεις (🟡 community)

Κατάσταση: 🟡 community Πηγή: φωτογραφία φοιτητικών απαντήσεων (σημειώσεις «Απ:» στα ερωτήματα Α–Δ)

Προσοχή

Τα ερωτήματα Α–Δ της φωτογραφίας (αποδείξεις για NP, για συμπλήρωμα NP-πλήρους γλώσσας, για P≠NP και για αναγωγή) δεν εμφανίζονται στη μεταγραφή του θέματος Ypologistiki_Ioun21.pdf. Η αντιστοιχία με την εξέταση Ιουνίου 2021 δεν είναι βέβαιη. Στο Discord (27/8/2022) η ίδια φωτογραφία αναρτήθηκε με σχόλιο ότι αφορά σύντομες λύσεις στο χαρτί που είχε φοιτητής στην εξέταση του Αυγούστου 2022. Αυτό ενισχύει την αμφιβολία ότι ανήκει στο θέμα Ιουνίου 2021.

Λύσεις — Υπολογιστική Πολυπλοκότητα — Ιούνιος 2021 — Ασκήσεις

Απαντήσεις φοιτητή σε ερωτήματα αποδείξεων (NP, συμπλήρωμα, P≠NP, αναγωγές)· δεν επαληθεύτηκαν.

compcomp_1.jpg

A) Αποδείξτε ότι αν η γλώσσα L ανήκει στο NP και για τη γλώσσα K ισχύει ότι \(K \leq_p L\) τότε και η K ανήκει στην NP. Απ: Κατασκευή πολ. επαληθευτή που πρώτα κάνει την απεικόνιση και μετά τρέχει το πολ. επαληθευτή της δοθείσας NP γλώσσας.

B) Αποδείξτε ότι: Αν η γλώσσα L είναι NP–πλήρης και το συμπλήρωμα \(L'\) αυτής ανήκει στην κλάση NP, τότε το συμπλήρωμα οποιασδήποτε γλώσσας στην κλάση NP ανήκει και αυτό στην κλάση NP. Απ: Αφού είναι NP-πλήρης η L, για κάθε γλώσσα στο NP θα ισχύει \(A \leq_p L\). Παίρνοντας συμπλήρωμα: \(A' \leq_p L'\). Με βάση το (A), αφού η \(L'\) είναι στο NP, θα είναι και η \(A'\).

Γ) Υποθέτοντας ότι \(P \neq NP\), ισχύει ή όχι ότι: Αν κάθε στιγμιότυπο του προβλήματος απόφασης \(P_1\) είναι και στιγμιότυπο του προβλήματος απόφασης \(P_2\), και αν το \(P_2\) είναι NP-δύσκολο (σκληρό) τότε και το \(P_1\) είναι NP-δύσκολο; ΑΠ: Όχι. Αντιπαράδειγμα το SAT είναι NP-πλήρες, και άρα και NP-hard. Όμως, το 2SAT είναι P. Για να είναι και αυτό NP-hard, θα έπρεπε \(P = NP\). Άρα άτοπο.

Δ) Αποδείξτε ότι: Αν \(L_1, L_2 \subseteq \Sigma^*\), με \(L_1 \in P\), \(L_2 \neq \varnothing\) και \(L_2 \neq \Sigma^*\), τότε υπάρχει πολυωνυμική απεικονιστική αναγωγή \(L_1 \leq L_2\). ΑΠ: Αφού η \(L_2\) δεν είναι τετριμμένη (δηλ. κενή ή \(\Sigma^*\)), θα υπάρχει \(x_1 \in L_2\) και \(x_2 \notin L_2\). Για την απεικόνιση θα είναι

\[f(x) = \begin{cases} x_1, & \text{αν } x \in L_1 \text{ (επαληθεύεται σε πολ. χρόνο άρα θα είναι πολ. αναγωγή)} \\ x_2, & \text{αν } x \notin L_1 \text{ (ομοίως)} \end{cases}\]

Επομένως θα πρέπει \(x \in L_1 \Leftrightarrow f(x) \in L_2\). Έστω \(x \in L_1\): θα είναι \(f(x) = x_1\) άρα πράγματι \(f(x) \in L_2\). Αντιθέτως, έστω \(x \notin L_1\): θα είναι \(f(x) = x_2\) άρα \(f(x) \notin L_2\). Άρα η αναγωγή είναι έγκυρη.

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

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