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

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

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

ToC_Exams-11-6-13.pdf (σελ. 1,2)

ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ

ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ « ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ » - 11/6/2013

Διάρκεια Εξέτασης (2½ ώρες)

1. (1.5 μονάδες) Έστω 𝐻𝐴𝐿𝑇𝛵𝛭′ ={  Μ,w  | η Μ είναι μία χρησμοληπτική ΤΜ που τερματίζει σε είσοδο w όταν υπολογίζει με χρησμοδότη για την HALTΤΜ }, όπου HALTΤΜ = {  Μ,w  | η Μ είναι μία ΤΜ που τερματίζει σε είσοδο w}. Δείξτε ότι η 𝐻𝐴𝐿𝑇𝛵𝛭′ είναι μη-διαγνώσιμη χρήσει της γλώσσας HALTΤΜ .

2. (2 μονάδες) Για κάθε σταθερά k , στο πρόβλημα του k -χρωματισμού μας δίνεται ένα ακατεύθυντο γράφημα του οποίου οι κορυφές θα πρέπει να χρωματισθούν με το πολύ k χρώματα έτσι ώστε κανένα ζευγάρι γειτονικών κορυφών να μην έχει ίδιο χρώμα. Έστω ότι γνωρίζετε ότι το πρόβλημα του 2- χρωματισμού ανήκει στο P ενώ το πρόβλημα του 3-χρωματισμού είναι NP-πλήρες.

α) (1.6) Να δείξετε ότι το πρόβλημα του 5-χρωματισμού είναι και αυτό NP-πλήρες με αναγωγή από το πρόβλημα του 3-χρωματισμού.

β) (0.4) Το πρόβλημα του k -χρωματισμού, για k ≥3, είναι NP-πλήρες ή υπάρχει κάποιο μεγάλο k για το οποίο το πρόβλημα λύνεται σε πολυωνυμικό χρόνο (αιτιολογήστε διαισθητικά);

3. (2 μονάδες)

α) (1 μονάδα) Να δείξετε ότι μία γλώσσα ανήκει στην κλάση NP αν και μόνο αν έχει πολυωνυμικό επαληθευτή.

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

4. (2 μονάδες) Να αναφέρετε αν οι παρακάτω προτάσεις είναι Σωστές (Σ) ή Λάθος (Λ) χωρίς αιτιολόγηση. a. Ένας κβαντικός υπολογιστής μπορεί να διαγνώσει περισσότερες γλώσσες από έναν κλασσικό Η/Υ. b. Ένας υπολογιστής που βασίζεται σε DNA μπορεί να λύσει αποδοτικά NP-πλήρη προβλήματα. c. Ένας φυσικός αλγόριθμος βασίζεται σε φαινόμενα που συναντιούνται στη φύση.

  • d. Τα κυψελωτά αυτόματα δεν μπορούν να διαγνώσουν τις γλώσσες που διαγιγνώσκει μία ΤΜ.

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

  • f. Το σύνολο όλων των γλωσσών στο αλφάβητο Σ={0,1} είναι αριθμήσιμο.

  • g. Το θεώρημα αναδρομής περιγράφει έναν τρόπο αυτό-αντιγραφής των προγραμμάτων.

  • h. To 3-SAT ως NP-πλήρες χρειάζεται εκθετικό χρόνο άρα και εκθετικό χώρο

  • i. Αν ένα NP-δυσχερές πρόβλημα λυνόταν σε πολυωνυμικό χρόνο τότε P=NP.

  • j. Το πρόβλημα TQBF είναι PSPACE-δυσχερές.

5. (1.5 μονάδες) α) (0.8 μονάδες) Να αποδείξετε ότι για όλες τις NP-πλήρεις γλώσσες A , B , C , A < p B και B < p CA < p C .

β) (0.7 μονάδες) Αναγράψτε τις σχέσεις (αν εμπεριέχονται, τέμνονται κοκ) μεταξύ των εξής κλάσεων πολυπλοκότητας: P, IP, PSPACE, NP, EXPTIME, DTIME( n123 ), co-P, co-NP, NPSPACE. Αναφέρετε ποιες από αυτές τις σχέσεις έχουν αποδειχτεί και ποιες όχι.

6. (2 μονάδες) Απαντήστε στις παρακάτω ερωτήσεις με αιτιολόγηση.

α) (0.7 μονάδες) Έστω μια οποιαδήποτε μηχανή Turing Μ στην οποία θέτουμε ως είσοδο μια οποιαδήποτε λέξη x . Μπορούμε να διαγνώσουμε αν η μηχανή M με είσοδο x περνά από κάθε μη τερματική κατάσταση της το πολύ 5 φορές;

β) (1.3 μονάδες) Έστω μια οποιαδήποτε μηχανή Turing Μ στην οποία θέτουμε ως είσοδο μια οποιαδήποτε λέξη x . Μπορούμε να διαγνώσουμε αν η μηχανή M με είσοδο x περνά από μια δοσμένη κατάσταση q τουλάχιστον 1 φορά;

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

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

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2013-06

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

Θέμα 1

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Δείχνουμε \(HALT_{TM} \le_m HALT'_{TM}\), άρα αν η \(HALT'_{TM}\) ήταν διαγνώσιμη θα ήταν και η \(HALT_{TM}\) (άτοπο).

Αναγωγή: για είσοδο \(\langle M,w\rangle\) (απλή ΤΜ) κατασκευάζουμε τη χρησμοληπτική μηχανή \(M'\) που, για είσοδο \(w\), δεν ρωτά ποτέ τον χρησμό και απλώς προσομοιώνει την \(M\) στο \(w\). Η απεικόνιση \(\langle M,w\rangle \mapsto \langle M',w\rangle\) είναι υπολογίσιμη.

  • Αν η \(M\) τερματίζει στο \(w\), τερματίζει και η \(M'\) (ό,τι χρησμό κι αν έχει).
  • Αν η \(M\) δεν τερματίζει, δεν τερματίζει ούτε η \(M'\).

Άρα \(\langle M,w\rangle \in HALT_{TM} \iff \langle M',w\rangle \in HALT'_{TM}\). Επειδή η \(HALT_{TM}\) είναι μη διαγνώσιμη, η \(HALT'_{TM}\) είναι μη διαγνώσιμη (ακόμη και με χρησμό για την \(HALT_{TM}\): ο χρησμός δεν βοηθά για τον τερματισμό των ίδιων των χρησμοληπτικών μηχανών).

Θέμα 2

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

α) Το 5-COLOR ∈ NP (πιστοποιητικό: ο χρωματισμός, έλεγχος κάθε ακμής σε πολυωνυμικό χρόνο).

Αναγωγή 3-COLOR \(\le_p\) 5-COLOR: από το \(G\) φτιάχνουμε το \(G'\) προσθέτοντας δύο νέες κορυφές \(u,v\) που ενώνονται μεταξύ τους και με όλες τις κορυφές του \(G\) (σε πολυωνυμικό χρόνο).

  • Αν το \(G\) έχει 3-χρωματισμό, χρωματίζουμε τις \(u,v\) με 2 νέα χρώματα (4ο και 5ο): έγκυρος 5-χρωματισμός του \(G'\).
  • Αν το \(G'\) έχει 5-χρωματισμό, οι \(u,v\) έχουν διαφορετικά χρώματα (γειτονικές) και κανένα από αυτά δεν εμφανίζεται στις κορυφές του \(G\) (όλες γειτονικές με τις \(u,v\)). Άρα το \(G\) χρωματίζεται με το πολύ \(5-2=3\) χρώματα.

Άρα \(G \in\) 3-COLOR \(\iff G' \in\) 5-COLOR. Το 5-COLOR είναι NP-πλήρες.

β) NP-πλήρες για κάθε σταθερό \(k\ge3\). Η ίδια αναγωγή (προσθήκη \(k-3\) κορυφών που ενώνονται μεταξύ τους και με όλο το γράφημα) δείχνει 3-COLOR \(\le_p\) \(k\)-COLOR. Διαισθητικά, το να είναι το \(k\) μεγάλο δεν «ξεκλειδώνει» αλγόριθμο: μπορούμε πάντα να «ξοδέψουμε» τα επιπλέον χρώματα και να μείνει ένα 3-χρωματισμό-ισοδύναμο υποπρόβλημα. Αν λυνόταν πολυωνυμικά για κάποιο \(k\), θα ίσχυε \(P=NP\).

Θέμα 3

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

α) (\(\Rightarrow\)) Έστω \(L\in NP\) με ΜΤ \(N\) που αποφασίζει σε χρόνο \(n^c\). Πιστοποιητικό για το \(x\): η ακολουθία των μη ντετερμινιστικών επιλογών μιας αποδεκτής διαδρομής (μήκος \(\le n^c\)). Ο επαληθευτής \(V(x,c)\) προσομοιώνει την \(N\) κατά τις επιλογές \(c\) και δέχεται αν η διαδρομή αποδέχεται: πολυωνυμικός χρόνος.

(\(\Leftarrow\)) Έστω πολυωνυμικός επαληθευτής \(V\) με πιστοποιητικά μήκους \(\le n^k\). Η ΜΤ \(N\) για είσοδο \(x\): μαντεύει μη ντετερμινιστικά συμβολοσειρά \(c\) μήκους \(\le |x|^k\), τρέχει την \(V(x,c)\) και δέχεται αν δεχτεί η \(V\). Πολυωνυμικός χρόνος, και \(x\in L \iff\) υπάρχει \(c\) που δέχεται. Άρα \(L\in NP\).

β) Το PSPACE είναι κλειστό ως προς:

  • Ένωση: αν οι \(A,B\) αποφασίζονται από ΜΤ \(M_A,M_B\) με πολυωνυμικό χώρο, τρέχουμε διαδοχικά (επαναχρησιμοποιώντας τον χώρο) την \(M_A\) και την \(M_B\) και δεχόμαστε αν δεχτεί κάποια. Χώρος = max των δύο + πολυώνυμο.
  • Σώρευση (συνένωση) \(AB\): για είσοδο \(w\) (\(|w|=n\)), για κάθε \(i=0..n\) ελέγχουμε \(w_{1..i}\in A\) και \(w_{i+1..n}\in B\) (επαναχρησιμοποιώντας τον χώρο). Χώρος: μετρητής \(i\) + πολυωνυμικός.
  • (Αν εννοείται και το άστρο του Kleene \(A^*\)): πίνακας \(T[0..n]\) με \(T[0]=\)true, \(T[j]=\bigvee_{i<j}\big(T[i]\wedge w_{i+1..j}\in A\big)\). Χώρος \(O(n)\) + πολυωνυμικός, άρα πολυωνυμικός.

Θέμα 4

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν

  • a. Λ (οι κβαντικοί υπολογιστές διαγιγνώσκουν ακριβώς τις ίδιες γλώσσες, ταχύτερα ίσως).
  • b. Λ (δεν είναι γνωστό/αποδεδειγμένο· απαιτεί εκθετικό πλήθος μορίων).
  • c. Σ
  • d. Λ (τα κυψελωτά αυτόματα είναι Turing-πλήρη).
  • e. Σ (πολυπλοκότητα Kolmogorov).
  • f. Λ (υπεραριθμήσιμο).
  • g. Σ (θεώρημα αναδρομής).
  • h. Λ (το 3-SAT λύνεται σε γραμμικό χώρο· ούτε είναι γνωστό ότι χρειάζεται εκθετικό χρόνο).
  • i. Σ
  • j. Σ (το TQBF είναι PSPACE-πλήρες).

Θέμα 5

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν

α) Αφού \(A\le_p B\) μέσω πολυωνυμικά υπολογίσιμης \(f\) και \(B\le_p C\) μέσω \(g\), ορίζουμε \(h=g\circ f\). Είναι υπολογίσιμη σε πολυωνυμικό χρόνο (\(|f(x)|\le p(|x|)\), άρα ο χρόνος της \(g\) στο \(f(x)\) είναι \(q(p(|x|))\)) και \(x\in A\iff f(x)\in B\iff g(f(x))\in C\). Άρα \(A\le_p C\).

β) Αποδεδειγμένες: - \(P=\text{co-}P\), \(P\subseteq NP\cap \text{co-}NP\). - \(DTIME(n^{123})\subsetneq P\) (θεώρημα ιεραρχίας χρόνου: υπάρχουν γλώσσες σε \(DTIME(n^{124})\) εκτός). - \(NP,\text{co-}NP\subseteq PSPACE\). - \(PSPACE=NPSPACE\) (Savitch), \(IP=PSPACE\) (Shamir). - \(PSPACE\subseteq EXPTIME\) και \(P\subsetneq EXPTIME\).

Ανοιχτές: \(P\overset{?}{=}NP\), \(NP\overset{?}{=}\text{co-}NP\), \(P\overset{?}{=}PSPACE\) (και \(NP\overset{?}{=}PSPACE\)), \(PSPACE\overset{?}{=}EXPTIME\).

Θέμα 6

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν

α) Ναι, διαγνώσιμο. Έστω \(m\) το πλήθος των μη τερματικών καταστάσεων. Αν η \(M\) περάσει από κάθε μη τερματική κατάσταση το πολύ 5 φορές, τότε τα βήματά της είναι \(\le 5m\) (κάθε βήμα ξεκινά από μη τερματική κατάσταση). Αλγόριθμος: προσομοιώνουμε την \(M\) στο \(x\) για \(5m+1\) βήματα. Αν σε \(\le 5m\) βήματα τερματίσει, η απάντηση είναι ΝΑΙ. Αν έγινε το \((5m+1)\)-οστό βήμα χωρίς τερματισμό, από την αρχή του περιστερώνα κάποια κατάσταση επισκέφθηκε \(\ge6\) φορές: ΟΧΙ.

β) Μη διαγνώσιμο (για γενική \(q\)). Αναγωγή από την \(A_{TM}\): \(\langle M,w\rangle\mapsto\langle M,w,q_{acc}\rangle\). Η \(M\) δέχεται το \(w\) ακριβώς όταν περνά από την \(q_{acc}\) τουλάχιστον μία φορά. Άρα ένας διαγνώστης του προβλήματος θα διέγνωσκε την \(A_{TM}\). Άτοπο. (Για συγκεκριμένα \(q\), π.χ. την αρχική, το πρόβλημα είναι τετριμμένο· το γενικό πρόβλημα όμως είναι μη διαγνώσιμο.)

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

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