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

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

CC_Exams-14-6-2022.pdf (σελ. 1,3,5,7)¶

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

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

1. (10 μονάδες) Υποθέτοντας ότι 𝑃≠𝑁𝑃 , να αποδείξετε αν ισχύει ή όχι η εξής πρόταση: Αν κάθε στιγμιότυπο του προβλήματος απόφασης 𝑃1 είναι και στιγμιότυπο του προβλήματος απόφασης 𝑃2, και αν το 𝑃2 είναι 𝑁𝑃-δυσχερές (𝑁𝑃-hard) τότε και το 𝑃1 είναι 𝑁𝑃-δυσχερές.

2. (35 μονάδες) (Α) (20) Δείξτε ότι το ακόλουθο πρόβλημα είναι 𝑁𝑃-πλήρες:

𝑃𝐴𝑇𝐻≥𝑘 : Δοθέντος κατευθυντικού γραφήματος 𝐺 , δύο κόμβων 𝑠, 𝑡 του 𝐺 και θετικού ακεραίου 𝑘 , υπάρχει απλή διαδρομή (που σέβεται τις κατευθύνσεις των ακμών) από 𝑠 σε 𝑡 μήκους τουλάχιστον 𝑘. Υπενθυμίζεται ότι μία απλή διαδρομή είναι μία διαδρομή που δεν περιέχει επαναλήψεις κόμβων.

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

𝑃𝐴𝑇𝐻≤𝑘 : Δοθέντος γραφήματος 𝐺 , δύο κόμβων 𝑠, 𝑡 του 𝐺 και θετικού ακεραίου 𝑘 , υπάρχει απλή διαδρομή από 𝑠 σε 𝑡 μήκους το πολύ 𝑘;

(Γ) (9) Χαρακτηρίστε ως αληθείς ή ψευδείς τις παρακάτω δηλώσεις και δώστε σύντομη αιτιολόγηση. Για τις απαντήσεις σας θεωρήστε ότι 𝑃≠𝑁𝑃.

(1) Το πρόβλημα 𝑃𝐴𝑇𝐻≤𝑘 ανήκει στην κλάση 𝑁𝑃.
(2) Υπάρχει αναγωγή του προβλήματος 𝑃𝐴𝑇𝐻≤𝑘 στο 3𝑆𝐴𝑇.
(3) Υπάρχει αναγωγή του προβλήματος 𝐻𝐴𝑀𝐼𝐿𝑇𝑂𝑁 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨 στο πρόβλημα 𝑃𝐴𝑇𝐻≤𝑘.

3. (25 μονάδες) Έστω η γλώσσα 𝛬= {〈𝑀〉|𝜂 𝐿(𝛭) 𝜋𝜀𝜌𝜄 έ 𝜒𝜀𝜄 𝜏𝜂 𝜆 έ 𝜉𝜂 "𝛫𝛢𝛬𝛰"}. Να αποδείξετε ότι η Λ είναι μη-διαγνώσιμη. Με 𝐿(𝛭) συμβολίζουμε τη γλώσσα της ΤΜ Μ .

4. (20 μονάδες) Να αναφέρετε για κάθε μία πρόταση αν είναι Αληθής ή Ψευδής χωρίς αιτιολόγηση. Σε αυτό το θέμα εφαρμόζεται αρνητική βαθμολόγηση. Κάθε σωστή απάντηση δίνει +0.2 και κάθε λάθος -0.2. Η αρνητική βαθμολόγηση δεν μεταφέρεται εκτός της συγκεκριμένης άσκησης.

i. Δοθέντος ενός Η/Υ με 10ΤB συνολική μνήμη και ενός προγράμματος για αυτόν τον Η/Υ, δεν μπορούμε να διαγνώσουμε αν το πρόγραμμα τερματίζει.
ii. Αν A ≤ mB και η Α είναι αναγνωρίσιμη τότε και η Β είναι αναγνωρίσιμη
iii. Το αλφάβητο ταινίας Γ μίας ΤΜ δεν μπορεί να συμπίπτει με το αλφάβητο εισόδου Σ.
iv. Αν SAT  P τότε και co-SAT  P.
v. Μία γλώσσα είναι αναγνωρίσιμη αν είναι διαγνώσιμη και συμπληρωματικά διαγνώσιμη.
vi. Η αιτιοκρατική ΤΜ είναι ισοδύναμη με την ανταιτιοκρατική ΤΜ όσον αφορά το σύνολο των γλωσσών που μπορούν να αναγνωρίσουν.
vii. Μία απεικονιστική αναγωγή εκθετικού χρόνου δεν μπορεί να διαχωρίσει τις κλάσεις P και NP.
viii. Υπάρχει απεικονιστική αναγωγή από τη γλώσσα ΑΠΟΔΟΧΗ στη γλώσσα ΚΕΝΟΤΗΤΑ. ix. Ισχύει ότι 𝐷𝑇𝐼𝑀𝐸(𝑛² ) ⊆𝑁𝑇𝐼𝑀𝐸(𝑛³ )
x. Αν ένα πρόβλημα Α ανάγεται απεικονιστικά σε πολυωνυμικό χρόνο στο πρόβλημα Β τότε και το Β μπορεί να αναχθεί απεικονιστικά σε πολυωνυμικό χρόνο στο Α.

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

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

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

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

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

1. (25 μονάδες) Έστω η γλώσσα 𝛫= {〈𝑀〉|𝜂 𝐿(𝛭) 𝜋𝜀𝜌𝜄 έ 𝜒𝜀𝜄 𝜏𝜂 𝜆 έ 𝜉𝜂 "𝛫𝛢𝛫𝛰"}. Να αποδείξετε ότι η Λ είναι μη-διαγνώσιμη. Με 𝐿(𝛭) συμβολίζουμε τη γλώσσα της ΤΜ Μ.

2. (20 μονάδες) Να αναφέρετε για κάθε μία πρόταση αν είναι Αληθής ή Ψευδής χωρίς αιτιολόγηση. Σε αυτό το θέμα εφαρμόζεται αρνητική βαθμολόγηση. Κάθε σωστή απάντηση δίνει +0.2 και κάθε λάθος -0.2. Η αρνητική βαθμολόγηση δεν μεταφέρεται εκτός της συγκεκριμένης άσκησης.

i. Έστω N μία ανταιτιοκρατική ΤΜ που τρέχει σε χρόνο t ( n ) και διαγιγνώσκει την γλώσσα L . Τότε: Υπάρχει μία αιτιοκρατική ΤΜ, D , που σε O ( t² ( n )) βήματα διαγιγνώσκει την L .
ii. Μία γλώσσα είναι αναγνωρίσιμη αν είναι διαγνώσιμη και συμπληρωματικά διαγνώσιμη.
iii. Η αιτιοκρατική ΤΜ είναι ισοδύναμη με την ανταιτιοκρατική ΤΜ όσον αφορά το σύνολο των γλωσσών που μπορούν να διαγνώσουν.
iv. Το θεώρημα των Cook-Levin αναφέρει ότι οποιοσδήποτε αλγόριθμος μπορεί να αναπαρασταθεί από μία ΤΜ.
v. Ένας πραγματικός αριθμός που είναι υπολογίσιμος είναι και περιγράψιμος.
vi. Ισχύει ότι 𝐷𝑇𝐼𝑀𝐸(𝑛³ ) ⊆𝑁𝑇𝐼𝑀𝐸(𝑛⁴ )
vii. Αν μία ανταιτιοκρατική ΤΜ Ν διαγιγνώσκει τη γλώσσα L τότε το συμπλήρωμα της γλώσσας L διαγιγνώσκεται από την ίδια μηχανή Ν συμπληρώνοντας τις εξόδους της.
viii. Αν ένα NP-δυσχερές πρόβλημα ανήκει στο P τότε P=NP.
ix. Υπάρχει απεικονιστική αναγωγή από τη γλώσσα ΑΠΟΔΟΧΗ στη γλώσσα ΚΕΝΟΤΗΤΑ.
x. Αν A ≤ mB και η Α είναι διαγνώσιμη τότε και η Β είναι διαγνώσιμη.

3. (35 μονάδες)¶

(Α) (20) Δείξτε ότι το ακόλουθο πρόβλημα είναι 𝑁𝑃-πλήρες:

𝑃𝐴𝑇𝐻> 𝑘: Δοθέντος κατευθυντικού γραφήματος 𝐺, δύο κόμβων 𝑠, 𝑡 του 𝐺 και θετικού ακεραίου 𝑘, υπάρχει απλή διαδρομή (που σέβεται τις κατευθύνσεις των ακμών) από 𝑠 σε 𝑡 μήκους αυστηρά μεγαλύτερο του 𝑘. Υπενθυμίζεται ότι μία απλή διαδρομή είναι μία διαδρομή που δεν περιέχει επαναλήψεις κόμβων.

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

𝑃𝐴𝑇𝐻< 𝑘: Δοθέντος γραφήματος 𝐺, δύο κόμβων 𝑠, 𝑡 του 𝐺 και θετικού ακεραίου 𝑘, υπάρχει απλή διαδρομή από 𝑠 σε 𝑡 μήκους αυστηρά μικρότερου του 𝑘;

(Γ) (9) Χαρακτηρίστε ως αληθείς ή ψευδείς τις παρακάτω δηλώσεις και δώστε σύντομη αιτιολόγηση. Για τις απαντήσεις σας θεωρήστε ότι 𝑃≠𝑁𝑃.

(1) Το πρόβλημα 𝑃𝐴𝑇𝐻< 𝑘 ανήκει στην κλάση co𝑁𝑃.

(2) Υπάρχει αναγωγή του προβλήματος 𝑃𝐴𝑇𝐻< 𝑘 στο 𝛫𝛬𝛪𝛫𝛢.

(3) Υπάρχει αναγωγή του προβλήματος 𝐻𝐴𝑀𝐼𝐿𝑇𝑂𝑁 𝛥𝛪𝛢𝛥𝛲𝛰𝛭𝛨 στο πρόβλημα 𝑃𝐴𝑇𝐻< 𝑘.

4. (10 μονάδες) Υποθέτοντας ότι 𝑃≠𝑁𝑃 , να αποδείξετε αν ισχύει ή όχι η εξής πρόταση: Αν κάθε στιγμιότυπο του προβλήματος απόφασης 𝛱1 είναι και στιγμιότυπο του προβλήματος απόφασης 𝛱2, και αν το 𝛱2 είναι 𝑁𝑃-δυσχερές (𝑁𝑃-hard) τότε και το 𝛱1 είναι 𝑁𝑃-δυσχερές.

5. (20 μονάδες) Έστω η αιτιοκρατική ΤΜ 𝛭 όπου 𝛴=

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

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

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

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

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

2. (10 μονάδες) Υποθέτοντας ότι 𝑃≠𝑁𝑃 , να

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

αποδείξετε αν ισχύει ή όχι η εξής πρόταση: Αν κάθε στιγμιότυπο του προβλήματος απόφασης 𝑃1 είναι και στιγμιότυπο του προβλήματος απόφασης 𝑃2, και αν το 𝑃2 είναι 𝑁𝑃-πλήρες τότε και το 𝑃1 είναι 𝑁𝑃-πλήρες.

3. (25 μονάδες) Έστω η γλώσσα 𝛬= {〈𝑀〉|𝜂 𝐿(𝛭) 𝜋𝜀𝜌𝜄 έ 𝜒𝜀𝜄 𝜏𝜂 𝜆 έ 𝜉𝜂 "𝛫𝛢𝛬𝛰𝛫𝛢𝛪𝛲𝛪"}. Να αποδείξετε ότι η Λ είναι μη-διαγνώσιμη. Με 𝐿(𝛭) συμβολίζουμε τη γλώσσα της ΤΜ Μ.

4. (20 μονάδες) Να αναφέρετε για κάθε μία πρόταση αν είναι Αληθής ή Ψευδής χωρίς αιτιολόγηση. Σε αυτό το θέμα εφαρμόζεται αρνητική βαθμολόγηση. Κάθε σωστή απάντηση δίνει +0.2 και κάθε λάθος -0.2. Η αρνητική βαθμολόγηση δεν μεταφέρεται εκτός της συγκεκριμένης άσκησης.

i. Δοθέντος ενός Η/Υ με 100ΤB συνολική μνήμη και ενός προγράμματος για αυτόν τον Η/Υ, δεν μπορούμε να διαγνώσουμε αν το πρόγραμμα τερματίζει.
ii. Το αλφάβητο ταινίας Γ μίας πολυταινιακής ΤΜ δεν μπορεί να συμπίπτει με το αλφάβητο εισόδου Σ.
iii. Αν 𝑁𝑃𝐶= 𝑐𝑜𝑁𝑃𝐶 τότε 𝑁𝑃= 𝑐𝑜𝑁𝑃. (𝑁𝑃𝐶 είναι η κλάση των 𝑁𝑃-πλήρων γλωσσών)
iv. Μία καθολική ΤΜ μπορεί να εξομοιώσει οποιαδήποτε άλλη ΤΜ
v. Όλοι οι πραγματικοί αριθμοί είναι υπολογίσιμοι.
vi. Μία απεικονιστική αναγωγή εκθετικού χρόνου δεν μπορεί να διαχωρίσει τις κλάσεις P και NP.
vii. Υπάρχει απεικονιστική αναγωγή από τη γλώσσα ΑΠΟΔΟΧΗ στη γλώσσα ΚΕΝΟΤΗΤΑ.
viii. Αν μία ανταιτιοκρατική ΤΜ Ν διαγιγνώσκει τη γλώσσα L τότε το συμπλήρωμα της γλώσσας L διαγιγνώσκεται από την ίδια μηχανή Ν συμπληρώνοντας τις εξόδους της.
ix. Αν ένα πρόβλημα Β ανάγεται απεικονιστικά σε πολυωνυμικό χρόνο στο πρόβλημα Α τότε και το Α μπορεί να αναχθεί απεικονιστικά σε πολυωνυμικό χρόνο στο Β.
x. Αν ένα NP-δυσχερές πρόβλημα ανήκει στο co-P τότε P=NP.

5. (35 μονάδες) (Α) (20) Δείξτε ότι το ακόλουθο πρόβλημα είναι 𝑁𝑃-πλήρες:

𝐶𝑌𝐶𝐿𝐸≥𝑘: Δοθέντος κατευθυντικού γραφήματος 𝐺 και θετικού ακεραίου 𝑘, υπάρχει απλός κύκλος (που σέβεται τις κατευθύνσεις των ακμών) μήκους τουλάχιστον 𝑘.

Υπενθυμίζεται ότι ένας απλός κύκλος είναι ένας κύκλος που δεν περιέχει επαναλήψεις κόμβων.

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

𝑃𝐴𝑇𝐻≤𝑘 : Δοθέντος γραφήματος 𝐺 , δύο κόμβων 𝑠, 𝑡 του 𝐺 και θετικού ακεραίου 𝑘 , υπάρχει απλή διαδρομή από 𝑠 σε 𝑡 μήκους το πολύ 𝑘;

(Γ) (9) Χαρακτηρίστε ως αληθείς ή ψευδείς τις παρακάτω δηλώσεις και δώστε σύντομη αιτιολόγηση. Για τις απαντήσεις σας θεωρήστε ότι 𝑃≠𝑁𝑃.

(1) Το πρόβλημα 𝑃𝐴𝑇𝐻≤𝑘 ανήκει στην κλάση 𝑁𝑃.
(2) Υπάρχει αναγωγή του προβλήματος 𝑃𝐴𝑇𝐻≤𝑘 στο 𝑆𝐴𝑇.
(3) Υπάρχει αναγωγή του προβλήματος 𝐻𝐴𝑀𝐼𝐿𝑇𝑂𝑁 𝛫𝛶𝛫𝛬𝛰𝛴 στο πρόβλημα 𝑃𝐴𝑇𝐻≤𝑘.

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

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

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

1. (35 μονάδες) (Α) (20) Δείξτε ότι το ακόλουθο πρόβλημα είναι 𝑁𝑃-πλήρες:

𝐶𝑌𝐶𝐿𝐸> 𝑘: Δοθέντος κατευθυντικού γραφήματος 𝐺 και θετικού ακεραίου 𝑘, υπάρχει απλός κύκλος (που σέβεται τις κατευθύνσεις των ακμών) μήκους αυστηρά μεγαλύτερου από 𝑘.

Υπενθυμίζεται ότι ένας απλός κύκλος είναι ένας κύκλος που δεν περιέχει επαναλήψεις κόμβων.

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

𝑃𝐴𝑇𝐻< 𝑘 : Δοθέντος γραφήματος 𝐺 , δύο κόμβων 𝑠, 𝑡 του 𝐺 και θετικού ακεραίου 𝑘 , υπάρχει απλή διαδρομή από 𝑠 σε 𝑡 μήκους αυστηρά μικρότερου του 𝑘;

(Γ) (9) Χαρακτηρίστε ως αληθείς ή ψευδείς τις παρακάτω δηλώσεις και δώστε σύντομη αιτιολόγηση. Για τις απαντήσεις σας θεωρήστε ότι 𝑃≠𝑁𝑃.

(1) Το πρόβλημα 𝑃𝐴𝑇𝐻< 𝑘 ανήκει στην κλάση 𝑐𝑜𝑁𝑃.

(2) Υπάρχει αναγωγή του προβλήματος 𝑃𝐴𝑇𝐻< 𝑘 στο 𝑆𝐴𝑇.

(3) Υπάρχει αναγωγή του προβλήματος 𝐻𝐴𝑀𝐼𝐿𝑇𝑂𝑁 𝛫𝛶𝛫𝛬𝛰𝛴 στο πρόβλημα 𝑃𝐴𝑇𝐻< 𝑘.

q 1
β →Δ
β →Δ
⌴ → β ,A
q 0
q 2
⌴ →A
β →Δ
⌴ →Δ
qα
qr r

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

3. (25 μονάδες) Έστω η γλώσσα 𝛫= qr r {〈𝑀〉|𝜂 𝐿(𝛭) 𝜋𝜀𝜌𝜄 έ 𝜒𝜀𝜄 𝜏𝜂 𝜆 έ 𝜉𝜂 "𝛸𝛦𝛪𝛭𝛺𝛮𝛢𝛴"} . Να αποδείξετε ότι η Κ είναι μη-διαγνώσιμη. Με 𝐿(𝛭) συμβολίζουμε τη γλώσσα της ΤΜ Μ.

4. (10 μονάδες) Υποθέτοντας ότι 𝑃≠𝑁𝑃 , να αποδείξετε αν ισχύει ή όχι η εξής πρόταση: Αν κάθε στιγμιότυπο του προβλήματος απόφασης 𝛱1 είναι και στιγμιότυπο του προβλήματος απόφασης 𝛱2, και αν το 𝛱2 είναι 𝑁𝑃-πλήρες τότε και το 𝛱1 είναι 𝑁𝑃-πλήρες.

5. (20 μονάδες) Να αναφέρετε για κάθε μία πρόταση αν είναι Αληθής ή Ψευδής χωρίς αιτιολόγηση. Σε αυτό το θέμα εφαρμόζεται αρνητική βαθμολόγηση. Κάθε σωστή απάντηση δίνει +0.2 και κάθε λάθος -0.2. Η αρνητική βαθμολόγηση δεν μεταφέρεται εκτός της συγκεκριμένης άσκησης.

i. Μία ΤΜ με πεπερασμένη μνήμη διαγιγνώσκει τις ίδιες γλώσσες με μία ΤΜ με άπειρη μνήμη.
ii. Αν A ≤ mB και η Α είναι διαγνώσιμη τότε και η Β είναι διαγνώσιμη.
iii. Έστω N μία πολυταινιακή ΤΜ που τρέχει σε χρόνο t ( n ) και διαγιγνώσκει την γλώσσα L . Τότε, υπάρχει μία αιτιοκρατική μονοταινιακή ΤΜ, D , που σε O ( t² ( n )) βήματα διαγιγνώσκει την L .
iv. Αν SAT  coNP τότε και coSAT  NP.
v. Η αιτιοκρατική μονοταινιακή ΤΜ είναι ισοδύναμη με την αιτιοκρατική πολυταινιακή ΤΜ όσον αφορά το σύνολο των γλωσσών που μπορούν να διαγνώσουν.
vi. Μία καθολική ΤΜ μπορεί να εξομοιώσει οποιαδήποτε άλλη ΤΜ.
vii. Μία απεικονιστική αναγωγή εκθετικού χρόνου δεν μπορεί να διαχωρίσει τις κλάσεις P και NP.
viii. Υπάρχει απεικονιστική αναγωγή από τη γλώσσα ΑΠΟΔΟΧΗ στη γλώσσα ΚΕΝΟΤΗΤΑ.
ix. Αν μία αιτιοκρατική ΤΜ Μ διαγιγνώσκει τη γλώσσα L τότε το συμπλήρωμα της γλώσσας L διαγιγνώσκεται από την ίδια μηχανή Μ συμπληρώνοντας τις εξόδους της.
x. Αν ένα NP-δυσχερές πρόβλημα ανήκει στο coP τότε P=NP.

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

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