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

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

Μεταγραφή των αρχείων 4d64cfeb2516093f.pdf και Screenshot_566, _569, _570, _575 (ερωτήσεις πολλαπλής επιλογής, συμπλήρωσης κενών και ανοιχτές).

4d64cfeb2516093f.pdf

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

Είναι δυνατόν ο πίνακας μεταβάσεων μιας μη ντετερμινιστικής μηχανής Turing να περιέχει τις μεταβάσεις \((q_2,a) \rightarrow (q_{NAI},b,A)\) και \((q_2,a) \rightarrow (q_{OXI},\sqcup,\Delta)\);

  • [ ] Ναι, ο ορισμός της μη ντετερμινιστικής μηχανής Turing το επιτρέπει.
  • [ ] Όχι βέβαια.

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή, οι οποίες δεν μεταγράφονται. Η ίδια ερώτηση είναι γραμμένη και ως «1)» στην πρώτη σελίδα του PDF, με τις μεταβάσεις \((q_2,a) \rightarrow (q_{NAI},b,A)\) και \((q_2,a) \rightarrow (q_{OXI},\text{KENO},\Delta)\) χωρίς επιλογές.

2. Έστω διαγνώσιμη γλώσσα L1 και αναγνωρίσιμη γλώσσα L2. Η γλώσσα \(\overline{L_1} \cap L_2\) είναι

Σημείωση: η φωτογραφία περιέχει απάντηση φοιτητή, η οποία δεν μεταγράφεται. Οι επιλογές της εκφώνησης για τις δύο ιδιότητες (διαγνώσιμη, αναγνωρίσιμη) δεν φαίνονται στις σελίδες.

Άσκηση 2: Περιγραφή δοθείσας TM. Εύρεση της γλώσσας δοθείσας Μηχανής Turing. Η απάντηση δίνεται με συμπλήρωση κενών. Βαθμολογικό βάρος ίσο με 30%. Δεν υπάρχει αρνητική βαθμολόγηση.

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

Δίνεται η μηχανή Turing του σχήματος.

[Σχήμα: μηχανή Turing με καταστάσεις q0, q1, q2, q3, qNAI και qOXI. Μεταβάσεις: q0 → q1 «α → Δ»· q1 → qOXI «⊔ → α, Δ»· q0 → q2 «⊔ → α, Λ»· q1 → q2 «α → Δ»· q2 → q3 «α → Δ» και «⊔ → α, Λ»· q3 → q0 «α → Δ»· q3 → qNAI «⊔ → Λ».]

Με είσοδο αα, η ΤΜ (αποδέχεται/απορρίπτει/εγκλωβίζεται) [ ]. Η ΤΜ (είναι/δεν είναι) [ ] διαγνώστης διότι [ ]. Η γλώσσα της ΤΜ είναι η [ ].

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

3. Μια μη ντετερμινιστική μηχανή Turing ονομάζεται διαγνώστης όταν

  • [ ] το δέντρο υπολογισμού της έχει έναν κλάδο που καταλήγει σε τελική κατάσταση.
  • [ ] το δέντρο υπολογισμού της έχει πεπερασμένο μέγεθος.

Σημείωση: οι επιλογές φαίνονται στη σελίδα 10 του PDF, ως «Ερώτηση (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.50 βαθμοί)». Στην πρώτη σελίδα φαίνεται μόνο η εκφώνηση και η απάντηση του φοιτητή.

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

Έστω τα εξής δύο προβλήματα: Π1: Δοθέντος γραφήματος \(G=(V,E)\), έχει το \(G\) ανεξάρτητο σύνολο μεγέθους \(|V| - 2\); Π2: Δοθέντος γραφήματος \(G=(V,E)\), έχει το \(G\) ανεξάρτητο σύνολο μεγέθους \(4\). Ποια από τις παρακάτω προτάσεις είναι η σωστή;

  • [ ] τα Π1 ανήκει στην κλάση P και το Π2 είναι NP-δυσχερές
  • [ ] το Π2 ανήκει στην κλάση P και το Π1 είναι NP-δυσχερές
  • [ ] και τα δύο προβλήματα ανήκουν στην κλάση P
  • [ ] και τα δύο προβλήματα είναι NP-πλήρη

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

Με δεδομένο ότι \(P \neq NP\), η κλάση \(\mathrm{coNP}\) περιέχει:

  • [ ] όλες τις γλώσσες που δεν ανήκουν στην κλάση NP (είναι το συμπλήρωμά της)
  • [ ] τα συμπληρώματα των γλωσσών που ανήκουν στην κλάση NP
  • [ ] όλες τις γλώσσες της κλάσης NP (συμπίπτει με την κλάση NP)
  • [ ] είναι άσχετη με την κλάση NP

Σημείωση: η φωτογραφία περιέχει επιλεγμένη απάντηση φοιτητή, η οποία δεν μεταγράφεται.

Ερώτηση (χωρίς βαθμολογία στο αρχείο)

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

[Σχήμα: έξι εμφωλευμένες ελλείψεις με ετικέτες α (εξωτερική), β, γ, δ, ε, στ (εσωτερική)]

  • [ ] (α) Διαγνώσιμη · (β) Μη-Αναγνωρίσιμη · (γ) NP · (δ) NTIME(n²) · (ε) P · (στ) NTIME(n³)
  • [ ] (α) Μη-Αναγνωρίσιμη · (β) Διαγνώσιμη · (γ) NTIME(n³) · (δ) NTIME(n²) · (ε) NP · (στ) P
  • [ ] (α) Μη-Αναγνωρίσιμη · (β) Διαγνώσιμη · (γ) NP · (δ) P · (ε) NTIME(n³) · (στ) NTIME(n²)
  • [ ] (α) Διαγνώσιμη · (β) NP · (γ) P · (δ) Μη-Αναγνωρίσιμη · (ε) NTIME(n³) · (στ) NTIME(n²)

Σημείωση: η φωτογραφία περιέχει επιλεγμένη απάντηση φοιτητή, η οποία δεν μεταγράφεται.

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

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

[Σχήμα: τέσσερα διαγράμματα Venn με ετικέτες (α), (β), (γ), (δ), όπως περιγράφονται στις επιλογές.]

  • [ ] (α): κύκλος με ετικέτα «P=NP=NPC»
  • [ ] (β): δύο τέμνοντες κύκλοι· αριστερά «NP», στην τομή «NPC», δεξιά «P»
  • [ ] (γ): εξωτερικός κύκλος «NP=P» και μέσα του κύκλος «NPC»
  • [ ] (δ): τρεις ομόκεντροι κύκλοι· εξωτερικός «NP», μεσαίος «P», εσωτερικός «NPC»

Σημείωση: η φωτογραφία περιέχει επιλεγμένη απάντηση φοιτητή, η οποία δεν μεταγράφεται.

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

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

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

Σημείωση: η ίδια ερώτηση είναι γραμμένη ως «1)» στην τρίτη σελίδα του PDF, χωρίς επιλογές.

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

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

  • [ ] Η ΙΣΟΔΥΝΑΜΙΑ/ΤΜ και το συμπλήρωμά της.
  • [ ] Δεν υπάρχει τέτοιο παράδειγμα.
  • [ ] Η ΑΠΟΔΟΧΗ/ΤΜ και η ΚΕΝΟΤΗΤΑ/ΤΜ.

Σημείωση: η ίδια ερώτηση είναι γραμμένη ως «2)» στην τρίτη σελίδα του PDF, χωρίς επιλογές.

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

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

[Σχήμα: τέσσερα διαγράμματα με ετικέτες (α), (β), (γ), (δ), όπως περιγράφονται στις επιλογές.]

  • [ ] (α): κύκλος με ετικέτα «P=NP=NPC»
  • [ ] (β): δύο τέμνοντες κύκλοι· αριστερά «NP», στην τομή «NPC», δεξιά «P»
  • [ ] (γ): εξωτερικός κύκλος «NP=P» και μέσα του κύκλος «NPC»
  • [ ] (δ): εξωτερικός κύκλος «NP», μέσα του κύκλος «P» και μικρός κύκλος «NPC» κοντά στο πάνω μέρος του εξωτερικού κύκλου

Σημείωση: η φωτογραφία περιέχει επιλεγμένη απάντηση φοιτητή, η οποία δεν μεταγράφεται.

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

Αν θέλαμε να δείξουμε ότι το πρόβλημα ΚΛΙΚΑ = \(\{<G,k>: \text{το γράφημα } G \text{ έχει } k\text{-κλίκα}\}\) ανήκει στην κλάση NP τότε το πιστοποιητικό του επαληθευτή θα ήταν:

  • [ ] ο αλγόριθμος που το επιλύει
  • [ ] όλες οι κλίκες που περιέχει το γράφημα G
  • [ ] μία κλίκα μεγέθους k του G εφόσον υπάρχει
  • [ ] ένα τυχαίο σύνολο k κόμβων του G

Ερώτηση (χωρίς αρίθμηση στο αρχείο) — με τμήμα απόδειξης αναγωγής και τετραγωνίδια επιλογής

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

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

S = για είσοδο \(\langle M,w \rangle\):

  1. Κατασκευάσε την TM M' που λειτουργεί ως εξής: M' = για είσοδο x:
  2. Αν x = "aaa", τότε αποδέξου.
  3. Αλλιώς, αν x ≠ "aaa", τότε προσομοίωσε την TM M με είσοδο w.
  4. Αν η M αποδεχτεί, τότε αποδέξου.
  5. Αν η M απορρίψει, τότε απόρριψε.
  6. Εκτέλεσε την TM R με είσοδο \(\langle M' \rangle\).
  7. Αν η R αποδεχτεί, τότε απόρριψε.
  8. Αν η R απορρίψει, τότε αποδέξου.

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

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

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

Τα προβλήματα 2SAT και 3SAT είναι:

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

Σημείωση: η φωτογραφία περιέχει επιλεγμένη απάντηση φοιτητή, η οποία δεν μεταγράφεται.

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

Αν θέλαμε να δείξουμε ότι το πρόβλημα SAT={<φ>: ο λογικός τύπος φ είναι αληθεύσιμος} ανήκει στην κλάση NP τότε το πιστοποιητικό του επαληθευτή θα ήταν:

  • [ ] μία τιμοδοσία της φ που την κάνει αληθή εφόσον υπάρχει
  • [ ] όλες οι τιμοδοσίες της φ
  • [ ] ο αλγόριθμος που το επιλύει
  • [ ] μία τυχαία τιμοδοσία της φ
  • [ ] Καμία Επιλογή.

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

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

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

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

Ποιο από τα παρακάτω προβλήματα δεν είναι NP-δυσχερές δεδομένου ότι \(P \neq NP\);

  • [ ] Hamiltonian διαδρομή
  • [ ] 3SAT
  • [ ] 2SAT
  • [ ] Πρόβλημα Τερματισμού (Halting)

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

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

  • [ ] το Π είναι NP-δυσχερές αλλά όχι NP-πλήρες
  • [ ] το Π ανήκει στην NP αλλά δεν είναι NP-πλήρες
  • [ ] το Π είναι NP-πλήρες
  • [ ] το Π δεν ανήκει στην NP και δεν είναι NP-πλήρες

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

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

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

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

Έστω διαγνώσιμες γλώσσες \(L_1\) και \(L_2\). Η γλώσσα \(\overline{L_1} \cup \overline{L_2}\) είναι

  • [ ] διαγνώσιμη.
  • [ ] αναγνωρίσιμη αλλά όχι διαγνώσιμη.
  • [ ] κενή.

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

Έστω μία συλλογή συνόλων {P1, P2, …, Pm} έτσι ώστε για κάθε i να ισχύει ότι το Pi είναι υποσύνολο ενός συνόλου X. Έστω το εξής πρόβλημα: UL-SC={: υπάρχει μία συλλογή από τουλάχιστον p και το πολύ q υποσύνολα Pi του X των οποίων η ένωση δίνει το X}. Θέλουμε να δείξουμε ότι το πρόβλημα UL-SC είναι NP-πλήρες.

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

Σημείωση: τα κενά (1)–(8) εμφανίζονται κενά στη φωτογραφία και μεταγράφονται ως [ ] με τον αριθμό τους. Οι απαντήσεις του φοιτητή δεν μεταγράφονται.

Screenshot_566.png

2. Έστω διαγνώσιμη γλώσσα L1 και αναγνωρίσιμη γλώσσα L2. Η γλώσσα \(\overline{L_1} \cap L_2\) είναι

Σημείωση: η φωτογραφία περιέχει απάντηση φοιτητή, η οποία δεν μεταγράφεται. Η ερώτηση είναι η ίδια με τη «2.» της πρώτης σελίδας του PDF.

Screenshot_569.png

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

Η ερώτηση είναι η ίδια με την «Ερώτηση 2 (0.30 βαθμοί)» της τέταρτης σελίδας του PDF (εκθετικό κάτω φράγμα, διαγράμματα (α)–(δ)).

Σημείωση: η φωτογραφία περιέχει επιλεγμένη απάντηση φοιτητή, η οποία δεν μεταγράφεται. Το κάτω μέρος της φωτογραφίας κόβεται στο σχήμα (δ)· ολόκληρο το σχήμα και οι επιλογές (α)–(δ) υπάρχουν στο PDF.

Screenshot_570.png

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

Η ερώτηση είναι η ίδια με την «Ερώτηση 1 (0.30 βαθμοί)» της τρίτης σελίδας του PDF (πολυωνυμικός αιτιοκρατικός αλγόριθμος για SAT, διαγράμματα (α)–(δ)).

  • [ ] (α)

Σημείωση: η φωτογραφία περιέχει επιλεγμένη απάντηση φοιτητή, η οποία δεν μεταγράφεται. Κόβεται στο κάτω μέρος· φαίνεται μόνο η επιλογή (α) και οι επιλογές (β)–(δ) λείπουν από τη φωτογραφία.

Screenshot_575.png

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

Η ερώτηση είναι η ίδια με την «Ερώτηση 5» της coNP (βλ. παραπάνω στο PDF), με τις ίδιες τέσσερις επιλογές.

Σημείωση: η φωτογραφία περιέχει επιλεγμένη απάντηση φοιτητή, η οποία δεν μεταγράφεται.

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

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

Προσοχή

Οι μεταφερόμενες απαντήσεις είναι μόνο γράμματα επιλογής, χωρίς αιτιολόγηση· δεν επαληθεύτηκαν από διδάσκοντα ή φοιτητή. Ερώτηση 1: η απάντηση α (P=NP=NPC) είναι συμβατή με την εκφώνηση: πολυωνυμικός αιτιοκρατικός αλγόριθμος για εύρεση τιμοδοσίας στο SAT συνεπάγεται P=NP, άρα όλες οι κλάσεις συμπίπτουν. Ερώτηση 2: η επιλογή δ δεν ελέγχθηκε πλήρως, επειδή το διάγραμμα (δ) στο Screenshot_569.png είναι μερικώς δυσανάγνωστο στη μεταγραφή. Οι απαντήσεις για τις ερωτήσεις 4 και 5 και για τα κενά της Άσκησης 2 δεν μεταφέρθηκαν: στο παλιό αρχείο η απάντηση είναι στην ίδια γραμμή με την εκφώνηση. Το Screenshot_566.png (ερώτηση 2) περιέχει μόνο επιλεγμένη απάντηση φοιτητή χωρίς κείμενο λύσης· δεν χρησιμοποιήθηκε ως πηγή λύσης.

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

Ερώτηση 1 (διαγράμματα P, NP, NPC): α. Ερώτηση 2 (εκθετικό κάτω φράγμα για ικανοποιησιμότητα): δ. Μεταφέρονται μόνο οι απαντήσεις που αφορούν ερωτήσεις αυτής της συνόδου· οι υπόλοιπες παλιές απαντήσεις ανακατεύονται με εκφωνήσεις και δεν μεταφέρονται.

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

Ερώτηση 2 :Απάντηση:Το δ

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

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