Latest revision as of 13:55, 24 January 2017

Υπολογιστική Πολυπλοκότητα

Προβλήματα και Αλγόριθμοι

Για την καλύτερη κατανόηση των εννοιών υπολογιστικό πρόβλημα, αλγόριθμος, μέγεθος προβλήματος, πολυπλοκότητα, κ.ά., θα παρουσιάσουμε έναν αλγόριθμο για την επίλυση του προβλήματος της ΠΡΟΣΠΕΛΑΣΙΜΟΤΗΤΑΣ (REACHABILITY) ή διαφορετικά, του προβλήματος του ΜΟΝΟΠΑΤΙΟΥ (PATH). Στην Θεωρία Πολυπλοκότητας αντιμετωπίζουμε τα υπολογιστικά προβλήματα όχι μόνο σαν προβλήματα προς λύση αλλά και σαν μαθηματικά αντικείμενα. Για το λόγο αυτό, απ' εδώ και στο εξής, θα αναφερόμαστε σε αυτά γράφοντας το όνομα τους με ΚΕΦΑΛΑΙΟΥΣ χαρακτήρες.

Το πρόβλημα της ΠΡΟΣΠΕΛΑΣΙΜΟΤΗΤΑΣ ορίζεται ως εξής:

Δοθέντος ενός κατευθυντικού γραφήματος $G = (V, E)$ και δύο κόμβων $s$ και $t$ του $G$ , υπάρχει μονοπάτι από τον κόμβο $s$ στον κόμβο $t$ ;

Στο σχήμα που ακολουθεί παρουσιάζουμε ένα στιγμιότυπο του προβλήματος. Πρόκειται για ένα γράφημα $G = (V, E)$ με σύνολο κόμβων $V = { 1, 2, 3, 4, 5 }$ και σύνολο ακμών $E = { (1,4), (2,1), (2,3), (3,1), (3,5), (4,3), (5,4) }$ , ενώ $s=1$ και $t=5$ . Δοθέντος του γραφήματος $G$ , ζητάμε απάντηση στο ερώτημα αν υπάρχει μονοπάτι από τον κόμβο $1$ στον κόμβο $5$ . Είναι εύκολο να διαπιστώσει κανείς ότι στο γράφημα αυτό πράγματι υπάρχει μονοπάτι από τον κόμβο $1$ στον κόμβο $5$ , το $(1, 4, 3, 5)$ .

Ένας αλλός τρόπος για να διατυπώσουμε το πρόβλημα της ΠΡΟΣΠΕΛΑΣΙΜΟΤΗΤΑΣ (τον οποίο και θα χρησιμοποιούμε για την διατύπωση των υπολογιστικών προβλημάτων που θα μας απασχολήσουν) είναι ο εξής:

ΠΡΟΣΠΕΛΑΣΙΜΟΤΗΤΑ (REACHABILITY)

Στιγμιότυπο:	Κατευθυντικό γράφημα $G = (V, E)$ και κόμβοι $s, t \in V$ .
Ερώτηση:	Υπάρχει μονοπάτι από τον κόμβο $s$ στον κόμβο $t$ ;

Είναι εύκολο να δει κανείς ότι αν το πλήθος των κόμβων ενός κατευθυντικού γραφήματος είναι ίσο με $|V|=n$ , τότε το πλήθος όλων των δυνατών ακμών που μπορούν να ορισθούν είναι ίσο με $|E| = n(n-1)$ . ʼΑρα το πλήθος των κόμβων $n$ του δοθέντος γραφήματος προσδιορίζει το μέγεθος του προβλήματος.

Η ΠΡΟΣΠΕΛΑΣΙΜΟΤΗΤΑ είναι ένα πρόβλημα απόφανσης(decision problem), δηλαδή ένα πρόβλημα στο οποία ζητείται απλά μια απάντηση "ΝΑΙ" ή "ΟΧΙ". Έτσι, για έναν αλγόριθμο επίλυσης του προβλήματος αυτού αρκεί να εξετάζει την ύπαρξη ή όχι μονοπατιού από τον κόμβο $s$ στον κόμβο $t$ και να απαντά "ΝΑΙ" ή "ΟΧΙ", αντίστοιχα, χωρίς να είναι απαραίτητο να δίνει στην έξοδο του και το μονοπάτι στην περίπτωση που αυτό υπάρχει. Τα προβλήματα απόφανσης παίζουν σημαντικό ρόλο στη Θεωρία της Υπολογιστικής Πολυπλοκότητας και θα μας απασχολήσουν αρκετά στα επόμενα μαθήματα.

Ας δώσουμε τώρα μια άτυπη περιγραφή ενός αλγορίθμου επίλυσης του προβλήματος της ΠΡΟΣΠΕΛΑΣΙΜΟΤΗΤΑΣ: Ο αλγόριθμος ουσιαστικά αναζητά το πιθανό μονοπάτι από τον κόμβο $s$ στον κόμβο $t$ . Η λειτουργία του αλγορίθμου είναι η εξής: Καθ' όλη τη διάρκεια εκτέλεσης του αλγορίθμου, διατηρούμε ένα σύνολο $S \subseteq V$ από κόμβους. Αρχικά, $S = { s }$ . Κάθε κόμβος του γραφήματος μπορεί να είναι χρωματισμένος ή όχι. Ένας κόμβος αποκτά χρώμα αν κάποια στιγμή κατά τη διάρκεια του υπολογισμού γίνει μέλος του συνόλου $S$ . Αρχικά μόνο ο κόμβος $s$ είναι χρωματισμένος. Σε κάθε επανάληψη του αλγορίθμου επιλέγουμε έναν κόμβο $i \in S$ και τον διαγράφουμε από το $S$ . Στη συνέχεια, εξετάζουμε όλες τις ακμές $(i,j)$ του γραφήματος. Αν ο κόμβος $j$ δεν έχει χρώμα, τότε τον χρωματίζουμε και τον εισάγουμε στο σύνολο $S$ . Η διαδικασία επαναλαμβάνεται μέχρι το σύνολο $S$ να μην περιέχει κανέναν κόμβο. Τότε, αν ο κόμβος $t$ είναι χρωματισμένος ο αλγόριθμος απαντά "ΝΑΙ" (δηλαδή, υπάρχει μονοπάτι από τον κόμβο $s$ στον κόμβο $t$ ) ενώ διαφορετικά απαντά "ΟΧΙ".

Αλγόριθμος 1 Αλγόριθμος επίλυσης της ΠΡΟΣΠΕΛΑΣΙΜΟΤΗΤΑΣ

repeat
  Πάρε έναν κόμβο  $i \in S$ .
   $S = S \setminus \{i\}.$ 
  for all   $(i,i) \in E$  do
    if ο κόμβος  $j$  δεν είναι χρωματισμένος then
        $S = S \cup \{j\}$ . {χρωμάτισε τον κόμβο  $j$ }
    end if
  end for
until  $S = \emptyset$ 
if ο κόμβος  $t$  είναι χρωματισμένος then
   return  NAI
else
   return  OXI
end if

Τα βήματα του αλγορίθμου που περιγράψαμε δίνονται στον Αλγόριθμο \ref{r_algorithm}. Είναι εύκολο να δεί κανείς ότι ο αλγόριθμος είναι ορθός αφού ένας κόμβος λαμβάνει χρώμα αν και μόνο αν υπάρχει μονοπάτι από τον κομβο $s$ σε αυτόν. Επίσης ο αλγόριθμος τερματίζει όταν το σύνολο $S$ γίνει ίσο με το κενό σύνολο, δηλαδή μετά από το πολύ $n$ επαναλήψεις (το σύνολο $S$ μπορεί να περιέχει το πολύ $n$ κόμβους και κάθε κόμβος εισάγεται το πολύ μία φορά σε αυτό). Σε κάθε επανάληψη (δηλαδή για κάθε κόμβο του $S$ ) ο αλγόριθμος εξετάζει όλες τις κορυφές που ξεκινούν από έναν κόμβο του γραφήματος, το πλήθος των οποίων είναι το πολύ $n$. Συνεπώς ο αλγόριθμος τερματίζει μετά από το πολύ $n^2$ βήματα. Άρα, η χρονική πολυπλοκότητα του Αλγορίθμου \ref{r_algorithm} είναι $O(n^2)$ .

Το πρόβλημα της ΠΡΟΣΠΕΛΑΣΙΜΟΤΗΤΑΣ λοιπόν μπορεί να λυθεί σε χρόνο πολυωνυμικό στο μέγεθος της εισόδου. Το αποτέλεσμα αυτό, όπως θα δούμε σε επόμενα μαθήματα, κατατάσει την ΠΡΟΣΠΕΛΑΣΙΜΟΤΗΤΑ στην κλάση $P$ , την κλάση όλων των προβλημάτων για τα οποία υπάρχει αλγόριθμος που τα επιλύει σε πολυωνιμικό χρόνο.

Αρχή της σελίδας

Μηχανή Turing

Ορίσαμε τη μηχανή Turing ως μια διατεταγμένη τετράδα $M=(K,\Sigma, \delta, s)$ όπου

1. $K$ είναι το πεπερασμένο σύνολο των καταστάσεων της $M$ ,

2. $\Sigma$ είναι το πεπερασμένο αλφάβητο της $M$ ,

3. $s$ είναι η αρχική κατάσταση της $M$ , $s \in K$ , και

4. $\delta : K \times \Sigma \rightarrow (K \cup \{h, q_{\rm NAI}, q_{\rm OXI}\}) \times \Sigma \times \{ \leftarrow, \rightarrow, - \}$ είναι η συνάρτηση μετάβασης της $M$ .

Στο αλφάβητο $\Sigma$ της μηχανής περιέχονται οι ειδικοί χαρακτήρες $\triangleright$ και $\sqcup$ (το κενό σύμβολο\footnote{Προσοχή, το κενό σύμβολο συμβολίζεται με $\flat$ στο σύγγραμμα διδασκαλίας \cite{KavvadiasBook}.}) ενώ η κατάσταση αποδοχής $q_{\rm NAI}$ , η κατάσταση απόρριψης $q_{\rm OXI}$ και η κατάσταση τερματισμού $h$ δεν ανήκουν στο σύνολο των καταστάσεων $K$ της μηχανής. Η συμβολοσειρά εισόδου $x \in (\Sigma \setminus \{ \sqcup \})^*$ δεν περιέχει κενά σύμβολα, οπότε το σύμβολο $\triangleright$ οριοθετεί την αρχή και το κενό σύμβολο $\sqcup$ οριοθετεί το τέλος της εισόδου της μηχανής.

Στη βιβλιογραφία μπορεί να συναντήσει κανείς διάφορες παραλλαγές στον ορισμό της μηχανής Turing. Για παράδειγμα, ο Χρήστος Παπαδημητρίου \cite{Pap94} ορίζει τη μηχανή Turing με τον παραπάνω τρόπο ενώ ο Michael Sipser \cite{Sipser97} ορίζει τη μηχανή Turing ως μια διατεταγμένη επτάδα. Οι διαφορές που μπορεί να παρουσιάζουν οι ορισμοί είναι επουσιώσεις και δεν επιρεάζουν τη συμπεριφορά του μαθηματικού αυτού μοντέλου υπολογισμού.

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

Ορισμός 1 Θα λέμε ότι η διαμόρφωση $(q, w, u)$ ακολουθεί τη διαμόρφωση $(q', w', u')$ σε ένα βήμα (και θα συμβολίζουμε με $(q, w, u) \xrightarrow{M} (q', w', u')$ ) αν η μηχανή Turing $M$ σε ένα βήμα της μεταβαίνει από τη διαμόρφωση $(q, w, u)$ στη διαμόρφωση $(q', w', u')$ .

Θα λέμε ότι η διαμόρφωση $(q, w, u)$ ακολουθεί τη διαμόρφωση $(q', w', u')$ σε $k$ βήματα, όπου $k \geq 0$ ακέραιος, (και θα συμβολίζουμε με $(q, w, u) \xrightarrow{M^k} (q', w', u')$ ) αν υπάρχουν διαμορφώσεις $(q_i, w_i, u_i)$ , $i=1,\ldots,i+1,$ τέτοιες ώστε $(q, w, u) = (q_1, w_1, u_1)$ , $(q_i, w_i, u_i) \xrightarrow{M} (q_{i+1}, w_{i+1}, u_{i+1}),$ $i=1,\ldots,k$ , και $(q_{i+1}, w_{i+1}, u_{i+1}) = (q', w', u')$ .

Τέλος, θα λέμε ότι η διαμόρφωση $(q, w, u)$ ακολουθεί τη διαμόρφωση $(q', w', u')$ (και θα συμβολίζουμε με $(q, w, u) \xrightarrow{} (q', w', u')$ ) αν υπάρχει ακέραιος $k \geq 0$ τέτοιος ώστε $(q, w, u) \xrightarrow{M^k} (q', w', u')$ .

Αν $s$ είναι η αρχική κατάσταση της μηχανής Turing $M$ , η αρχική διαμόρφωση της $M$ θα είναι η $(s, \triangleright , x)$ , όπου $x$ είναι η είσοδος της $M$ . Η διαμόρφωση στην οποία η κατάσταση της $M$ είναι η $q_{\rm NAI}$ καλείται διαμόρφωση αποδοχής ενώ η διαμόρφωση όπου η κατάσταση της $M$ είναι η $q_{\rm OXI}$ καλείται διαμόρφωση απόρριψης. Έτσι, θα λέμε, εναλλακτικά, ότι η μηχανή Turing $M$ αποδέχεται την είσοδο $x$ αν την αρχική διαμόρφωση ακολουθεί η διαμόρφωση αποδοχής ενώ η μηχανή Turing $M$ απορρίπτει την είσοδο $x$ αν την αρχική διαμόρφωση ακολουθεί η διαμόρφωση απόρριψης. Τέλος, η διαμόρφωση όπου η κατάσταση της $M$ είναι η $h$ καλείται διαμόρφωση τερματισμού.

Στη συνέχεια διατυπώνουμε πάλι τον Ορισμό 2.2 του συγγράμματος διδασκαλίας. Θυμίζουμε ότι με $M(x)$ συμβολίζουμε την έξοδο της μηχανής Turing $M$ όταν αυτή δεχθεί ως είσοδο τη συμβολοσειρά $x$ .

Ορισμός 2 Έστω $L\subseteq (\Sigma \setminus\{ \sqcup \})^*$ μία γλώσσα. Αν μία μηχανή Turing $M$ είναι τέτοια ώστε για κάθε συμβολοσειρά $x\in L$ , $M(x)=q_{\rm NAI}$ και για κάθε συμβολοσειρά $x\notin L$ , $M(x) = q_{\rm OXI}$ , τότε λέμε ότι η $M$ αποφασίζει (decides) την $L$ . Αν μία μηχανή Turing $M$ είναι τέτοια ώστε για κάθε συμβολοσειρά $x\in L$ , $M(x)=q_{\rm NAI}$ και για κάθε συμβολοσειρά $x\notin L$ , $M(x)=\uparrow$ , τότε λέμε ότι η $M$ αποδέχεται (accepts) την $L$ .

Αν για μία δοθείσα γλώσσα υπάρχει μηχανή Turing που να την αποφασίζει, τότε λέμε ότι η γλώσσα είναι Turing αποφασίσιμη (Turing decidable) ή αναδρομική (recursive). Παρόμοια, αν για μία γλώσσα υπάρχει μηχανή Turing που να την αποδέχεται, τότε λέμε ότι η γλώσσα είναι Turing αναγνωρίσιμη (Turing recognizable) ή αναδρομικά αριθμήσιμη (recursive enumerable).

Διατυπώνουμε πάλι το Παράδειγμα 2.1 του διδακτικού συγγράμματος:

Έστω η μηχανή Turing $M=(K, \Sigma, \delta, s)$ όπου $\Sigma=\{\triangleright, \sqcup, a, b\}$ , $K = \{ s \}$ και $\delta$ η συνάρτηση μετάβασης που ορίζεται σύμφωνα με τον παρακάτω πίνακα:

$q$	$\sigma$	$\delta(q, \sigma)$
$s$ &	$\triangleright$	$(s, \triangleright, \rightarrow )$
$s$	$a$	$(q_{\rm NAI} , a, - )$
$s$	$b$	$(s, b, \rightarrow )$
$s$	$\flat$	$(q_{\rm OXI}, \sqcup, - )$

Ας δούμε τις μεταβάσεις της μηχανής $M$ με είσοδο, για παράδειγμα την συμβολοσειρά $bbaab$ , καταγράφοντας τις διαδοχικές διαμορφώσεις της:

$( s, \triangleright, bbaab ) \rightarrow ( s, \triangleright b, baab ) \rightarrow ( s, \triangleright bb, aab ) \rightarrow ( s, \triangleright bba, ab ) \rightarrow ( q_{\rm NAI}, \triangleright bba, ab )$ .

Η μηχανή $M$ λοιπόν τερματίζει στην κατάσταση $q_{\rm NAI}$ όταν στην ταινία της διαβάσει τον χαρακτήρα a.

Ας δούμε την λειτουργία της μηχανής για μια ακόμα είσοδο, π.χ. για την συμβολοσειρά $bbb$ :

$( s, \triangleright, bbb ) \rightarrow ( s, \triangleright b, bb ) \rightarrow ( s, \triangleright bb, b ) \rightarrow ( s, \triangleright, \sqcup ) \rightarrow ( s, \triangleright bbb\sqcup, \sqcup ) \rightarrow ( q_{\rm OXI}, \triangleright bbb, \sqcup )$ .

Με είσοδο την συμβολοσειρά $bbb$ η μηχανή $M$ τερματίζει στην κατάσταση $q_{\rm OXI}$ .

Είναι εύκολο να δει κανείς ότι η μηχανή $M$ αποδέχεται όλες τις συμβολοσειρές που περιέχουν τουλάχιστον ένα χαρακτήρα $a$ ενώ σε διαφορετική περίπτωση τις απορρίπτει. Συνεπώς η $M$ αποφασίζει τη γλώσσα $L = \{ w \in \{a,b\}^\ast ~|~$ η $w$ περιέχει τον χαρακτήρα $a$ . Άρα η παραπάνω γλώσσα είναι Turing αποφασίσιμη (αναδρομική).

Συνεχίζουμε με το Παράδειγμα 2.2,\footnote{(Μια μικρή διόρθωση για το

Παράδειγμα 2.2: Η 9η (συμπεριλαμβανομένης και της αρχικής) διαμόρφωση στον υπολογισμό της μηχανής με είσοδο $aabab$ είναι η $(p, \triangleright bbab, b )$ .} δίνοντας μια εναλλακτική μηχανή Turing. Θέλουμε να κατάσκευάσουμε μια μηχανή Turing η οποία να αντιστρέφει κάθε συμβολοσειρά $x \in \{a,b\}^\ast$ . Για παράδειγμα, με είσοδο τη συμβολοσειρά $aabab$ η μηχανή θα πρέπει να δίνει ως έξοδο τη συμβολοσειρά $bbaba$ . Η μηχανή $M=(K, \Sigma, \delta, s)$ θα έχει το σύνολο καταστάσεων $K = \{ s \}$ , το αλφάβητό της είναι το $\Sigma=\{\triangleright, \sqcup, a,$ $b\}$ και η συνάρτηση μετάβασης $\delta$ αυτής ορίζεται σύμφωνα με τον παρακάτω πίνακα:

$q$	$\sigma$	$\delta(q, \sigma)$
$s$	$\triangleright$	$(s,\triangleright, \rightarrow )$
$s$	$a$	$(s, b, \rightarrow )$
$s$	$b$	$(s, a, \rightarrow )$
$s$	$\flat$	$(h,\sqcup, - )$

Ας δούμε τον υπολογισμό της $M$ με είσοδο τη συμβολοσειρά $aabab$ :

$( s, \triangleright, aabab ) \rightarrow ( s, \triangleright a, abab ) \rightarrow ( s, \triangleright ba, bab ) \rightarrow ( s, \triangleright bbb, ab ) \rightarrow ( s, \triangleright bbaa, b ) \rightarrow ( s, \triangleright bbabb, \sqcup ) \rightarrow ( s, \triangleright bbaba\sqcup, \sqcup ) \rightarrow ( h, \triangleright bbaba\sqcup, \sqcup )$ .

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

Συνεχίζουμε με την κατασκευή μιας ακόμα μηχανής Turing:

Άσκηση 1

Να κατασκευαστεί μηχανή Turing $M$ η οποία να αναγνωρίζει τη γλώσσα $L = \{ w \in \{a,b\}^\ast ~|~$ η $w$ περιέχει τη συμβολοσειρά $aa$ . \end{exercise}

Δίνουμε πρώτα μια περιγραφή της λειτουργίας της μηχανής Turing $M$ : Με είσοδο $w$ η μηχανή κινεί την κεφαλή της από αριστερά προς δεξιά μέχρι να συναντήσει τον χαρακτήρα $a$ . Τότε, η μηχανή <<θυμάται>> το $a$ και κινεί την κεφαλή της μια θέση δεξιά. Αν και ο επόμενος χαρακτήρας είναι $a$ , η μηχανή αποδέχεται την είσοδο. Διαφορετικά, <<ξεχνάει>> το $a$ και συνεχίζει να κινείται δεξιά.

Ο τυπικός μαθηματικός ορισμός της μηχανής Turing $M$ είναι: $M=(K, \Sigma, \delta, s)$ όπου $K = \{s, q_a\}$ , $\Sigma = \{ \triangleright, \sqcup, a, b\}$ , και η συνάρτηση μετάβασης $\delta : K \times \Sigma \rightarrow (K \cup \{h, q_{\rm NAI}, q_{\rm OXI}) \} \times \Sigma \times \{ \leftarrow, \rightarrow, - \}$ ορίζεται σύμφωνα με τον ακόλουθο πίνακα:

$q$	$\sigma$	$\delta(q, \sigma)$
$s$	$\triangleright$	$( s, \triangleright, \rightarrow)$
$s$	$a$	$( q_a, a, \rightarrow)$
$s$	$b$	$( s, b, \rightarrow)$
$s$	$\sqcup$	$( s, \sqcup, -)$
$q_a$	$\triangleright$	$( q_a, \triangleright, -)$
$q_a$	$a$	$( q_{\rm NAI}, a, -)$
$q_a$	$b$	$( s, b, \rightarrow)$
$q_a$	$\sqcup$	$( q_a, \sqcup, - )$

Η μηχανή Turing $M$ που μόλις κατασκευάσαμε αναγνωρίζει τη γλώσσα $L$ . Συνεπώς η $L$ είναι Turing αναγνωρίσιμη (αναδρομικά αριθμήσιμη). Ωστόσο, η $L$ είναι επίσης και Turing αποφασίσιμη (αναδρομική).\footnote{Προσοχή, αυτό δεν συμβαίνει για κάθε γλώσσα.} Η μηχανή Turing $M'$ που αποφασίζει τη γλώσσα $L$ έχει το ίδιο σύνολο καταστάσεων με την $M$ και η συνάρτηση μετάβασης αυτής δίνεται στον πίνακα που ακολουθεί (συγκρίνετε τον με τον προηγούμενο πίνακα):

$q$	$\sigma$	$\delta(q, \sigma)$
$s$	$\triangleright$	$( s,\triangleright, \rightarrow )$
$s$	$a$	$( q_a, a, \rightarrow )$
$s$	$b$	$( s, b, \rightarrow )$
$s$	$\sqcup$	$( q_{\rm OXI}, \sqcup, - )$
$q_a$	$\triangleright$	$( q_{\rm OXI}, \triangleright, - )$
$q_a$	$a$	$( q_{\rm NAI}, a, - )$
$q_a$	$b$	$( s, b, \rightarrow )$
$q_a$	$\sqcup$	$( q_{\rm OXI}, \sqcup, - )$

Αρχή της σελίδας

Αναδρομικές και αναδρομικά αριθμήσιμες γλώσσες

Ξεκινάμε με κάποιες ασκήσεις αναφορικά με τη σχέση αναδρομικών ή αναδρομικά αριθμήσιμων γλωσσών και της ένωσης αυτών. Να θυμίσουμε ότι μια γλώσσα $L$ είναι αναδρομική (Turing αποφασίσιμη) αν υπάρχει μηχανή Turing, έστω $M$ , που την αποφασίζει, δηλαδή $M(x)=q_{NAI}, \forall x\in L$ και $M(x)=q_{OXI}, \forall x\not\in L$ . Επίσης, μια γλώσσα $L$ είναι αναδρομικά αριθμήσιμη (Turing αναγνωρίσιμη) αν υπάρχει μηχανή Turing, έστω $M$ , που την αναγνωρίζει, δηλαδή $M(x)=q_{NAI}, \forall x\in L$ $M(x)=\uparrow, \forall x\not\in L$ .

Άσκηση 2 Δείξτε ότι αν μια γλώσσα $L$ είναι αναδρομική τότε είναι και αναδρομικά αριθμήσιμη.

Αφού η $L$ είναι αναδρομική, υπάρχει μηχανή Turing $M$ που την αποφασίζει, δηλαδή, για κάθε συμβολοσειρά $x$ ,

$M(x) = \left\{ \begin{array}{ll} {\textrm NAI}, & x \in L, \\ {\textrm OXI}, & x \not \in L. \\ \end{array} \right.$

Κατασκευάζουμε μηχανή Turing $M'$ η οποία είσοδο $x$ προσομοιώνει τη λειτουργία της $M$ με είσοδο $x$ , και

αν $M(x)={\textrm NAI}$ , τότε και $M'(x)={\textrm NAI}$ , ενώ
αν $M(x)={\textrm OXI}$ , τότε $M'(x) = \uparrow$ (η $M'$ πέφτει σε ατέρμονο βρόχο).

Είναι φανερό ότι $M'(x)={\textrm NAI} \Leftrightarrow M(x)={\textrm NAI} \Leftrightarrow x \in L$ . ʼAρα, η μηχανή $M'$ αναγνωρίζει τη γλώσσα $L$ , δηλαδή η $L$ είναι αναδρομικά αριθμήσιμη.

Άσκηση 3 Δείξτε ότι αν μια γλώσσα $L$ είναι αναδρομική τότε και η συμπληρωματική γλώσσα αυτής, $\overline{L}$ , είναι αναδρομική.

Αφού η $L$ είναι αναδρομική, υπάρχει μηχανή Turing $M$ που την αποφασίζει, δηλαδή, για κάθε συμβολοσειρά $x$ ,

$M(x) = \left\{ \begin{array}{ll} {\textrm NAI}, & x \in L, \\ {\textrm OXI}, & x \not \in L.\\ \end{array} \right.$

Κατασκευάζουμε μηχανή Turing $M'$ η οποία με είσοδο $x$ προσομοιώνει τη λειτουργία της $M$ με είσοδο $x$ , και

αν $M(x)={\textrm NAI}$ , τότε $M'(x)={\textrm OXI}$ , ενώ
αν $M(x)={\textrm OXI}$ , τότε $M'(x)={\textrm NAI}$ .

Είναι φανερό ότι $M'(x)={\textrm NAI} \Leftrightarrow M(x)={\textrm OXI} \Leftrightarrow x \not\in L \Leftrightarrow x \in \overline{L}$ . Επίσης, $M'(x)={\textrm OXI} \Leftrightarrow M(x)={\textrm NAI} \Leftrightarrow x \in L \Leftrightarrow x \not\in \overline{L}$ . ʼAρα η μηχανή $M'$ αποφασίζει τη γλώσσα $\overline{L}$ , δηλαδή η $\overline{L}$ είναι αναδρομική.

Άσκηση 4

Δείξτε ότι, αν οι γλώσσες $L_1$ και $L_2$ είναι αναδρομικές, τότε και η ένωση $L_1 \cup L_2$ αυτών είναι αναδρομική γλώσσα.

Μια συμβολοσειρά ανήκει στην ένωση των $L_1$ και $L_2$ αν ανήκει είτε στην $L_1$ είτε στην $L_2$ . Για να δείξουμε ότι η γλώσσα $L_1 \cup L_2$ είναι αναδρομική θα κατασκευάσουμε μηχανή Turing $M$ η οποία θα την αποφασίζει, δηλαδή, με είσοδο τη συμβολοσειρά $x$ ,

$M(x) = \left\{ \begin{array}{ll} {\textrm NAI}, & x \in L_1 \cup L_2, \\ {\textrm OXI}, & x \not \in L_1 \cup L_2. \\ \end{array} \right.$

Για την αναδρομική γλώσσα $L_1$ θα υπάρχει μηχανή Turing $M_1$ που την αποφασίζει, δηλαδή,

$M_1(x) = \left\{ \begin{array}{ll} {\textrm NAI}, & x \in L_1, \\ {\textrm OXI}, & x \not \in L_1. \\ \end{array} \right.$

Ομοίως, για την αναδρομική γλώσσα $L_2$ θα υπάρχει μηχανή Turing $M_2$ που την αποφασίζει, δηλαδή,

$M_2(x) = \left\{ \begin{array}{ll} {\textrm NAI}, & x \in L_1, \\ {\textrm OXI}, & x \not \in L_1. \\ \end{array} \right.$

Η μηχανή Turing $M$ με είσοδο $x$ , αρχικά προσομοιώνει την λειτουργία της $M_1$ με είσοδο $x$ . Αν $M_1(x)={\textrm NAI}$ , τότε $M(x)={\textrm NAI}$ . Διαφορετικά, προσομοιώνει την λειτουργία της $M_2$ με είσοδο $x$ . Αν $M_2(x)={\textrm NAI}$ , τότε $M(x)={\textrm NAI}$ . Διαφορετικά, $M(x)={\textrm OXI}$ .

Είναι φανερό ότι $M(x)={\textrm NAI} \Leftrightarrow \{ M_1(x)={\textrm NAI}$ ή $M_2(x)={\textrm NAI} \} \Leftrightarrow \{ x \in L_1$ ή $x \in L_2 \}$ $\Leftrightarrow x \in L_1 \cup L_2$ .Επίσης, $M(x)={\textrm OXI} \Leftrightarrow \{ M_1(x)={\textrm OXI}$ και $M_2(x)={\textrm OXI} \} \Leftrightarrow \{ x \not\in L_1$ και $x \not\in L_2 \} \Leftrightarrow \{ x \in \overline{L_1}$ και $x \in \overline{L_2} \} \Leftrightarrow x \in \overline{L_1} \cap \overline{L_2} \Leftrightarrow x \in \overline{L_1 \cup L_2} \Leftrightarrow x \not \in L_1 \cup L_2.$ \footnote{Το συμπλήρωμα της ένωσης δύο συνόλων (γλωσσών) ισούται με την τομή των συμπληρωμάτων αυτών.} Συνεπώς η $M$ αποφασίζει τη γλώσσα $L_1 \cup L_2$ , άρα η $L_1 \cup L_2$ είναι αναδρομική.

Είναι εύκολο να αποδείξει κανείς ότι αντίστοιχη ιδιότητα ισχύει και για την τομή $L_1 \cap L_2$ δυο αναδρομικών γλωσσών (η απόδειξη αφήνεται ως άσκηση).

Άσκηση 5 Δείξτε ότι, αν οι γλώσσες $L_1$ και $L_2$ είναι αναδρομικές, τότε η ένωση $L_1 \cup L_2$ αυτών είναι αναδρομικά αριθμήσιμη γλώσσα.

Γνωρίζουμε ότι αν μια γλώσσα είναι αναδρομική τότε είναι και αναδρομικά αριθμήσιμη. Σύμφωνα με την προηγούμενη άσκηση, η ένωση $L_1 \cup L_2$ δύο αναδομικών γλωσσών $L_1$ και $L_2$ είναι αναδρομική γλώσσα, άρα και αναδρομικά αριθμήσιμη.

Άσκηση 6 Δείξτε ότι, αν οι γλώσσες $L_1$ και $L_2$ είναι αναδρομικά αριθμήσιμες, τότε και η ένωση $L_1 \cup L_2$ αυτών είναι αναδρομικά αριθμήσιμη γλώσσα.

θα κατασκευάσουμε μια μηχανή Turing $M$ που να αναγνωρίζει τη γλώσσα $L_1 \cup L_2$ , δηλαδή, με είσοδο τη συμβολοσειρά $x$ ,

$M(x) = \left\{ \begin{array}{ll} {\textrm NAI}, & x \in L_1 \cap L_2, \\ \uparrow, & x \not \in L_1 \cap L_2. \\ \end{array} \right.$

Για την αναδρομικά αριθμήσιμη γλώσσα $L_1$ θα υπάρχει μηχανή Turing $M_1$ που την αναγνωρίζει, δηλαδή

$M_1(x) = \left\{ \begin{array}{ll} {\textrm NAI}, & x \in L_1, \\ \uparrow, & x \not \in L_1. \\ \end{array} \right.$

Ομοίως, για την αναδρομικά αριθμήσιμη γλώσσα $L_2$ θα υπάρχει μηχανή Turing $M_2$ που την αναγνωρίζει, δηλαδή

$M_2(x) = \left\{ \begin{array}{ll} {\textrm NAI}, & x \in L_2, \\ \uparrow, & x \not \in L_2. \\ \end{array} \right.$

Η μηχανή Turing $M$ θα προσομοιώνει τη λειτουργία των $M_1$ και $M_2$ . Προσέξτε όμως ότι σε αυτή την περίπτωση η δυο μηχανές θα πρέπει να λειτουργούν <<παράλληλα>> και όχι <<σειριακά>> (όπως στην προηγούμενη άσκηση) διότι ενδέχεται η $M_1$ με είσοδο $x\in L_2$ (άρα και $x \in L_1 \cup L_2$ ) να πέσει σε ατέρμονο βρόχο με συνέπεια η $M$ να μην προσομοιώσει ποτέ τη λειτουργία της $M_2$ με είσοδο $x$ (η οποία θα τερμάτιζε με κατάσταση αποδοχής).

Έτσι, λοιπόν, η μηχανή Turing $M$ με είσοδο $x$ προσομοιώνει την λειτουργία της $M_1$ με είσοδο $x$ και της $M_2$ με είσοδο $x$ , κάνοντας εναλλάξ ένα βήμα της $M_1$ και ένα βήμα της $M_2$ . Αν $M_1(x)={\textrm NAI}$ , τότε $M(x)={\textrm NAI}$ . Επίσης, αν $M_2(x)={\textrm NAI}$ , τότε $M(x)={\textrm NAI}$ . Σε κάθε άλλη περίπτωση, $M(x)=\uparrow$ .

Είναι φανερό ότι $M(x)={\textrm NAI} \Leftrightarrow \{ M_1(x)={\textrm NAI}$ ή $M_2(x)={\textrm NAI} \} \Leftrightarrow \{ x \in L_1$ ή $x \in L_2 \}$ $\Leftrightarrow x \in L_1 \cup L_2.$ Επίσης, $M(x)=\uparrow \Leftrightarrow$ $M_1(x)=\uparrow$ και $M_2(x)=\uparrow \} \Leftrightarrow \{ x \not \in L_1$ και $x \not \in L_2 \} \Leftrightarrow \{ x \in \overline{L_1}$ και $x \in \overline{L_2} \} \Leftrightarrow x \in \overline{L_1} \cap \overline{L_2} \Leftrightarrow x \in \overline{L_1 \cup L_2} \Leftrightarrow x \not \in L_1 \cup L_2.$ Συνεπώς η $M$ αναγνωρίζει τη γλώσσα $L_1 \cup L_2$ , άρα η $L_1 \cup L_2$ είναι αναδρομικά αριθμήσιμη.

Είναι εύκολο να αποδείξει κανείς ότι αντίστοιχη ιδιότητα ισχύει και για την τομή $L_1 \cap L_2$ δυο αναδρομικά αριθμήσιμων γλωσσών (η απόδειξη αφήνεται ως άσκηση).

Περνάμε τώρα στην κατασκευή μηχανών Turing που αναγνωρίζουν ή αποφασίζουν συγκεκριμένες γλώσσες.

Άσκηση 7 Να κατασκευαστεί μηχανή Turing $M$ η οποία να αναγνωρίζει τη γλώσσα $L = \{ a^\ast b a^\ast b \}.$

Ας δώσουμε πρώτα με άτυπη περιγραφή της λειτουργίας της $M$ . H $M$ σαρώνει την είσοδο της από αριστερά προς δεξιά μέχρι να συναντήσει το πρώτο $b$ . Η $M$ <<θυμάται>> το $b$ και συνεχίζει να κινείται δεξιά μέχρι να συναντήσει το δεύτερο $b$ . Αν ακολουθεί το κενό σύμβολο, η $M$ αποδέχεται την είσοδο ενώ διαφορετικά την απορρίπτει.

Ο τυπικός μαθηματικός ορισμός της μηχανή Turing $M$ είναι ο εξής: $M=(K, \Sigma, \delta, s)$ όπου $K = \{s, q_1, q_2\}$ , $\Sigma = \{ \triangleright, \sqcup, a, b\}$ , και η συνάρτηση μετάβασης $\delta : K \times \Sigma \rightarrow (K \cup \{h, q_{\rm NAI}, q_{\rm OXI}) \} \times \Sigma \times \{ \leftarrow, \rightarrow, - \}$ ορίζεται σύμφωνα με τον ακόλουθο πίνακα:

$q$	$\sigma$	$\delta(q, \sigma)$
$s$	$\triangleright$	$( s, \triangleright, \rightarrow)$
$s$	$a$	$( s, a, \rightarrow)$
$s$	$b$	$( q_1, b, \rightarrow)$
$s$	$\sqcup$	$( s, \sqcup, -)$
$q_1$	$\triangleright$	$( q_1, \triangleright -)$
$q_1$	$a$	$( q_1, a, \rightarrow)$
$q_1$	$b$	$( q_2, b, \rightarrow)$
$q_1$	$\sqcup$	$( q_1, \sqcup, - )$
$q_2$	$\triangleright$	$( q_2, \triangleright, -)$
$q_2$	$a$	$( q_2, a, -)$
$q_2$	$b$	$( q_2, b, -)$
$q_2$	$\sqcup$	$( q_{NAI}, \sqcup, - )$

'Ασκηση 8 Να κατασκευαστεί μηχανή Turing $M$ η οποία να αποφασίζει τη γλώσσα $L = \{ w \in \{0,1\}^\ast ~|~$ η συμβολοσειρά $w$ είναι παλίνδρομο.

Μια συμβολοσειρά καλείται παλίνδρομο εάν είναι αναγνώσιμη με τον ίδιο τρόπο και από αριστερά προς τα δεξιά αλλά και από δεξία προς τα αριστερά. Για παράδειγμα, η συμβολοσειρά νιψονανομηματαμημονανοψιν είναι παλίδρομο.

Ας δώσουμε πρώτα με άτυπη περιγραφή της λειτουργίας της $M$ . Η $M$ διαβάζει το περιεχόμενο του πρώτου κυτάρου της ταινίας της, το θυμάται και το <<διαγράφει>> (γράφει τον χαρακτήρα $\triangleright$ ). Στη συνέχεια σαρώνει την είσοδο μέχρι το τέλος της (συναντά το κενό σύμβολο $\sqcup$ ). Αν το τελευταίο στοιχείο συμφωνεί με το πρώτο, κινείται αριστερά μέχρι να συναντήσει την (νέα) αρχή της ταινίας και επαναλαμβάνει τη διαδικασία. Αν όχι, απορρίπτει την είσοδο. Η μηχανή αποδέχεται την είσοδο όταν στην ταινία της υπάρχουν μόνο κενά σύμβολα (η περίπτωση όπου η είσοδος έχει άρτιο μήκος) ή απομείνει ένα μόνο σύμβολο (η περίπτωση όπου η είσοδος έχει περιττό μήκος).

Ο τυπικός μαθηματικός ορισμός της μηχανή Turing $M$ είναι ο εξής: $M=(K, \Sigma, \delta, s)$ όπου $K = \{s, q_0, q_1, q_0', q_1',q\}$ , $\Sigma = \{ \triangleright, \sqcup, 0, 1\}$ , και η συνάρτηση μετάβασης $\delta : K \times \Sigma \rightarrow (K \cup \{h, q_{\rm NAI}, q_{\rm OXI}) \} \times \Sigma \times \{ \leftarrow, \rightarrow, - \}$ ορίζεται σύμφωνα με τον ακόλουθο πίνακα:

$p$	$\sigma$	$\delta(p, \sigma)$
$s$	$\triangleright$	$( s, \triangleright, \rightarrow)$
$s$	$0$	$( q_0,\triangleright, \rightarrow)$
$s$	$1$	$( q_1,\triangleright, \rightarrow)$
$s$	$\sqcup$	$( q_{NAI}, \sqcup, -)$
$q_0$	$\triangleright$	$( q_{OXI}, \triangleright, -)$
$q_0$	$0$	$( q_0, 0, \rightarrow)$
$q_0$	$1$	$( q_0, 1, \rightarrow)$
$q_0$	$\sqcup$	$( q_0', \sqcup, \leftarrow )$
$q_1$	$\triangleright$	$( q_{OXI}, \triangleright, -)$
$q_1$	$0$	$( q_1, 0, \rightarrow)$
$q_1$	$1$	$( q_1, 1, \rightarrow)$
$q_1$	$\sqcup$	$( q_1', \sqcup, \leftarrow )$

$p$	$\sigma$	$\delta(p, \sigma)$
$q_0'$	$\triangleright$	$( q_{NAI}, \sqcup, - )$
$q_0'$	$0$	$( q, \sqcup, \leftarrow )$
$q_0'$	$1$	$( q_{OXI}, 1, - )$
$q_0'$	$\sqcup$	$( q_{OXI}, \sqcup, - )$
$q_1'$	$\triangleright$	$( q_{NAI}, \triangleright, - )$
$q_1'$	$0$	$( q_{OXI}, 0, - )$
$q_1'$	$1$	$( q, \sqcup, \leftarrow )$
$q_1$	$\sqcup$	$( q_{OXI}, \sqcup, - )$
$q$	$\triangleright$	$( s,\triangleright, \rightarrow )$
$q$	$0$	$( q, 0, \leftarrow )$
$q$	$1$	$( q, 1, \leftarrow )$
$q$	$\sqcup$	$( q_{OXI}, \sqcup, - )$

Αρχή της σελίδας

Παραλλαγές της μηχανής Turing

Ξεκινάμε με την κατασκευή μιας μηχανής Turing με $2$ ταινίες η οποία αποφασίζει συγκεκριμένη γλώσσα.

Άσκηση 9

Να κατασκευαστεί μηχανή Turing $2$ ταινιών η οποία να αποφασίζει τη γλώσσα $L = \{ w \in \{0,1\}^\ast ~|~$ η συμβολοσειρά $w\}$ είναι παλίνδρομο.

Θυμίζουμε ότι μια συμβολοσειρά καλείται παλίνδρομο εάν είναι αναγνώσιμη με τον ίδιο τρόπο και από αριστερά προς τα δεξιά αλλά και από δεξία προς τα αριστερά.

Δίνουμε την περιγραφή της λειτουργίας της μηχανής Turing: Η μηχανή,

1.Δημιουργεί ένα αντίγραφο της εισόδου της στη δεύτερη ταινία.

2.Τοποθετεί την κεφαλή της πρώτης ταινίας στο πρώτο σύμβολο της εισόδου και την κεφαλή της δεύτερης ταινίας στο τελευταίο σύμβολο του αντίγραφου.

3.Μετακινεί τις δύο κεφαλές με αντίθετη φορά, ελέγχοντας κάθε φορά εάν το τρέχον σύμβολο στην πρώτη ταινία ταυτίζεται με το τρέχον σύμβολο στην δεύτερη ταινία. Αν όχι, τότε η μηχανή απορρίπτει την είσοδο. Διαφορετικά, όταν η κεφαλή της πρώτης ταινίας φτάσει στο τέλος της εισόδου (και η κεφαλή της δεύτερης ταινίας φτάσει στην αρχή της), τότε η μηχανή αποδέχεται την είσοδο.

Ο τυπικός μαθηματικός ορισμός της μηχανής είναι ο εξής: $M=(K, \Sigma, \delta, s)$ όπου $K = \{s, q, r\}$ , $\Sigma = \{ \triangleright, \sqcup, a, b\}$ , και η συνάρτηση μετάβασης $\delta : K \times \Sigma^2 \rightarrow (K \cup \{h, q_{\rm NAI}, q_{\rm OXI}) \} \times \Sigma^2 \times \{ \leftarrow, \rightarrow, - \}^2$ ορίζεται σύμφωνα με τον ακόλουθο πίνακα:

$p$	$\sigma_1$	$\sigma_2$	$\delta(p, \sigma_1, \sigma_2)$
$s$	$\triangleright$	$\triangleright$	$(s, \triangleright, \rightarrow, \triangleright, \rightarrow)$
$s$	$a$	$\sqcup$	$(s, a, \rightarrow, a, \rightarrow)$
$s$	$b$	$\sqcup$	$(s, b, \rightarrow, b, \rightarrow)$
$s$	$\sqcup$	$\sqcup$	$(q, \sqcup, \leftarrow, \sqcup, -)$
$q$	$a$	$\sqcup$	$(q, a, \leftarrow, \sqcup, -)$
$q$	$b$	$\sqcup$	$(q, b, \leftarrow, \sqcup, -)$
$q$	$\triangleright$	$\sqcup$	$(r, \triangleright, \rightarrow, \sqcup, \leftarrow)$ $
$r$	$a$	$a$	$(r, a, \rightarrow, a, \leftarrow )$
$r$	$a$	$b$	$(q_{OXI}, a, -, b, -)$
$r$	$b$	$a$	$(q_{OXI}, b, -, a, -)$
$r$	$b$	$b$	$(r, b, \rightarrow, b, \leftarrow)$
$r$	$\sqcup$	$\triangleright$	$(q_{NAI}, \sqcup, -, \triangleright, - )$

Αποδείξαμε ότι για κάθε μηχανή Turing $k$ ταινιών υπάρχει ισοδύναμη μηχανή Turing μιας ταινίας. Θυμίζουμε ότι δυο μηχανές Turing καλούνται ισοδύναμες αν αναγνωρίζουν (αποδέχονται) την ίδια γλώσσα.

Άσκηση 10 Δείξτε ότι μια γλώσσα $L$ είναι αναδρομικά αριθμήσιμη αν και μόνο αν υπάρχει μηχανή Turing $k$ ταινιών που την αναγνωρίζει.

Έστω ότι η $L$ είναι αναδρομικά αριθμήσιμη. Τότε, εξ ορισμού, υπάρχει μηχανή Turing, έστω $S$ , που αναγνωρίζει την $L$ . Θα κατασκευάσουμε μηχανή Turing $M$ $k$ ταινιών που να αναγνωρίζει την $L$ . Η κατασκευή είναι ιδιαίτερα απλή: Η $M$ με είσοδο $x$ προσομοιώνει τη λειτουργία της $S$ με είσοδο $x$ και αποδέχεται την είσοδο όταν η $S$ αποδεχθεί την είσοδο. Είναι φανερό ότι η μηχανή Turing $M$ που κατασκευάσαμε αναγνωρίζει τη γλώσσα $L$ .

Αντίστροφα τώρα, έστω ότι υπάρχει μηχανή Turing $M$ $k$ ταινιών που αναγνωρίζει τη γλώσσα $L$ . Για την $M$ υπάρχει ισοδύναμη μηχανή Turing $S$ μιας ταινίας. ʼΑρα υπάρχει μηχανή Turing μιας ταινίας που αναγνωρίζει την $L$ , δηλαδή η $L$ είναι αναδρομικά αριθμήσιμη.

Μια ακόμα παραλλαγή του βασικού μοντέλου της μηχανής Turing είναι ο απαριθμητής (enumerator). Πρόκειται για μια μηχανή Turing $E$ η οποία είναι συνδεδεμένη με μια συσκευή εξόδου (για παράδειγμα, με έναν εκτυπωτή). Ο απαριθμητής ξενικά με κενή ταινία εισόδου και τυπώνει στη συσκευή εξόδου μια μη πεπερασμένη ακολουθία απο συμβολοσειρές από κάποιο αλφάβητο, οι οποίες χωρίζονται μεταξύ τους με κάποιο ειδικό χαρακτήρα (π.χ. $\sharp$ ). Ένας απαριθμητής απαριθμεί μια γλώσσα $L$ εάν στην συσκευή εξόδου τυπώνει τις συμβολοσειρές που ανήκουν στην $L$ . Η έξοδος των συμβολοσειρών γίνεται με αυθαίρετο τρόπο (όχι κατ' ανάγκη με κάποια συγκεκριμένη διάταξη) και ενδεχομένως και με επαναλήψεις.

Το θεώρημα που ακολουθεί φανερώνει τη σχέση μεταξύ των απαριθμητών και των αναδρομικά αριθμήσιμων γλωσσών.

Θεώρημα 1:Μια γλώσσα είναι αναδρομικά αριθμήσιμη αν και μόνο αν υπάρχει απαριθμητής που την απαριθμεί.

Απόδειξη Ας θεωρήσουμε αρχικά ότι μια γλώσσα $L$ είναι αναδρομικά αριθμήσιμη και έστω $M$ η μηχανή Turing που την αναγνωρίζει. Θεωρούμε την ακολουθία $s_1, s_2, \ldots$ όλων των δυνατών συμβολοσειρών του αλφαβήτου. Κατασκευάζουμε απαριθμητή $E$ ο οποίος λειτουργεί ως εξής:

Για $i=1, 2, 3, \ldots$

1. Προσομοιώνει τη λειτουργία της $M$ για $i$ βήματα με είσοδο κάθε μια από τις συμβολοσειρές $s_1, s_2, \ldots, s_i$ .

2. Κάθε φορά που η $M$ αποδέχεται μια συμβολοσειρά, ο $E$ την τυπώνει στην έξοδο του.

Αν μια συμβολοσειρά $s$ ανήκει στη γλώσσα $L$ , τότε σε κάποιο βήμα του υπολογισμού του ο $E$ θα τυπώσει την $s$ στην έξοδο του. Η συμβολοσειρά $s$ ενδεχομένως να εμφανιστεί περισσότερες από μία φορές στην έξοδο του $E$ , αφού η μηχανή $M$ κάνει κάθε φορά $i$ βήματα για κάθε συμβολοσειρά $s_1, s_2, \ldots, s_i$ .

Ο τρόπος που λειτουργεί ο απαριθμητής αποφεύγει την περίπτωση η $M$ να <<κολλήσει>> για συγκεκριμένη συμβολοσειρά εισόδου $s_i$ , κάτι που θα συνέβαινε στην περίπτωση που προσομοίωνε την $M$ με είσοδο $s_i$ από την αρχή μέχρι το τέλος της λειτουργίας της. Η τεχνική αυτή καλείται μέθοδος της ουράς του περιστεριού (dove tailing method).

Αντίστροφα τώρα, έστω ότι υπάρχει απαριθμητής $E$ που απαριθμεί τη γλώσσα $L$ . Κατασκευάζουμε μηχανή Turing $M$ η οποία με είσοδο $x$ λειτουργεί ως εξής: Προσομοιώνει τη λειτουργία του $E$ (αγνοώντας την είσοδο) και κάθε φορά που ο $E$ τυπώνει κάποια συμβολοσειρά στην έξοδο του, την συγκρίνει με την $x$ . Αν η $x$ εμφανιστεί στην έξοδο του $E$ , τότε η $M$ τερματίζει με κατάσταση αποδοχής.

Είναι φανερό ότι η μηχανή που κατασκευάσαμε αναγνωρίζει τη γλώσσα $L$ . ʼAρα η $L$ είναι Turing-αναγνωρίσιμη.

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

Αποδείξαμε ότι μια γλώσσα είναι αναδρομικά αριθμήσιμη αν και μόνο αν υπάρχει απαριθμητής που την απαριθμεί. Η επόμενη πρόταση φανερώνει ότι αν ένας απαριθμητής έχει συγκεκριμένα χαρακτηριστικά, τότε είναι δυνατό να χρησιμοποιηθεί για την κατασκευή μιας μηχανής Turing που αποφασίζει μια γλώσσα.

Άσκηση 11 Δείξτε ότι μια γλώσσα $L$ είναι αναδρομική αν και μόνο αν υπάρχει απαριθμητής που απαριθμεί τα στοιχεία της με αυξανόμενο μήκος.

Έστω ότι η $L$ είναι αναδρομική και έστω $M$ η μηχανή Turing που αποφασίζει την $L$ . Θεωρούμε την ακολουθία $s_1, s_2, \ldots$ όλων των συμβολοσειρών του αλφαβήτου, διατεταγμένες με αυξανόμενο μήκος. Κατασκευάζουμε απαριθμητή $E$ ο οποίος λειτουργεί ως εξής:

Για $i=1, 2, 3, \ldots$

1. Προσομοιώνει τη λειτουργία της $M$ με είσοδο τη συμβολοσειρά $s_i$ . 2. Αν $M(s_i) =$ NAI, τότε ο $E$ τυπώνει την $s_i$ . Διαφορετικά, συνεχίζει (εκτελεί το Βήμα 1 για την επόμενη τιμή του $i$ ).

Είναι φανερό ότι ο απαριθμητής $E$ απαριθμεί τα στοιχεία της γλώσσας $L$ με αυξανόμενο μήκος.

Αντίστροφα τώρα, έστω ότι υπάρχει απαριθμητής $E$ που απαριθμεί τα στοιχεία της γλώσσας $L$ με αυξανόμενο μήκος. Κατασκευάζουμε μηχανή Turing $M$ η οποία με είσοδο $x$ λειτουργεί ως εξής:

Προσομοιώνει τη λειτουργία του $E$ (αγνοώντας την είσοδο). Κάθε φορά που ο $E$ δίνει μια συμβολοσειρά στην έξοδο του, η $M$ τη συγκρίνει με την $x$ . Αν η $x$ εμφανιστεί στην έξοδο του $E$ , τότε η $M$ αποδέχεται την $x$ . Αν, όμως, εμφανιστεί στην έξοδο του $E$ συμβολοσειρά με μήκος μεγαλύτερο από το μήκος της $x$ , τότε η $M$ απορρίπτει την $x$ .

Είναι φανερό ότι η μηχανή που κατασκευάσαμε αποφασίζει τη γλώσσα $L$ . ʼAρα η $L$ είναι αναδρομική.

Αρχή της σελίδας

H μη ντετερμινιστική μηχανή Turing

Το τυπικό μοντέλο της μηχανής Turing λειτουργεί με ντετερμινιστικό τρόπο: κάθε βήμα του υπολογισμού της καθορίζεται μονοσήμαντα από το προηγούμενο βήμα. Η έννοια του μη ντετερμινισμού δίνει σε μια μηχανή Turing τη δυνατότητα να επιλέγει, μεταξύ διαφόρων δυνατών επιλογών, ποιο θα είναι το επόμενο βήμα της αλλά και την ελευθερία να βρίσκεται ταυτόχρονα σε πολλά σημεία του υπολογισμού. Οι μεταβάσεις μιας μη ντετερμινιστικής μηχανής Turing $M=(K,\Sigma,\Delta,s)$ ορίζονται πλέον μέσω μιας σχέσης μετάβασης $\Delta \subseteq (K\times \Sigma)\times ((K\cup \{h, q_{\rm NAI}, q_{\rm OXI}\}) \times \Sigma \times \{\leftarrow, \rightarrow,-\})$ και όχι από μια συνάρτηση μετάβασης $\delta : K \times \Sigma \rightarrow (K\cup \{h, q_{\rm NAI}, q_{\rm OXI}\}) \times \Sigma \times \{\leftarrow, \rightarrow,-\}$ όπως στην περίπτωση της ντετερμινιστικής μηχανής Turing. Έτσι, ο υπολογισμός μιας μη ντετερμινιστικής μηχανής Turing δεν είναι μια γραμμική ακολουθία βημάτων (όπως στην περίπτωση μιας ντετερμινιστικής μηχανής) αλλά ένα δέντρο από βήματα. Η ρίζα του δέντρου αντιστοιχεί στην αρχή του υπολογισμού. Κάθε εσωτερικός κόμβος του δέντρου αντιστοιχεί σε ένα ενδιάμεσο σημείο του υπολογισμού. Η μηχανή μπορεί να επιλέξει πιο θα είναι το επόμενο βήμα της μεταξύ των απογόνων του κόμβου. Το μέγιστο πλήθος $d$ των δυνατών απογόνων ενός κόμβου είναι σταθερό και χαρακτηρίζει το βαθμό του μη ντετερμινισμού. Τέλος, τα φύλλα του δέντρου αντιστοιχούν στις καταστάσεις αποδοχής και απόρριψεις $q_{\rm NAI}$ και $q_{\rm OXI}$ αντίστοιχα, ή και στην κατάσταση τερματισμού $h$ .

Ο τυπικός μαθηματικός ορισμός της μη ντετερμινιστικής μηχανής Turing είναι ο ακόλουθος:

Ορισμός 3

Μια μη ντετερμινιστική μηχανή Turing είναι μία διατεταγμένη τετράδα $M=(K,\Sigma,\Delta,s)$ . Το $K$ είναι το πεπερασμένο σύνολο καταστάσεων', το $\Sigma$ το πεπερασμένο αλφάβητο και η $s\in K$ είναι η αρχική κατάσταση. Το $\Delta$ είναι ένα υποσύνολο του $(K\times \Sigma)\times ((K\cup \{h, q_{\rm NAI}, q_{\rm OXI}\}) \times \Sigma \times \{\leftarrow, \rightarrow,-\})$ και ονομάζεται σχέση μετάβασης.

Μια μη ντετερμινιστική μηχανή Turing αποδέχεται την συμβολοσειρά εισόδου $x$ εάν στο δέντρο του υπολογισμού της υπάρχει κάποιο μονοπάτι (δηλαδή, εάν υπάρχει ακολουθία μεταβάσεων) που καταλήγει σε κατάσταση αποδοχής. Σε διαφορετική περίπτωση, η μηχανή δεν αποδέχεται την είσοδο της. Βλέπουμε ότι μια μη ντετερμινιστική μηχανή Turing είναι αρκετά γενναιόδωρη όσο αφορά στον τρόπο αποδοχής μιας συμβολοσειράς. Αρκεί η ύπαρξη ενός μονοπατιού στο (πιθανόν εκθετικά μεγάλου μεγέθους) δέντρο του υπολογισμού που να καταλήγει σε κατάσταση αποδοχής, ενώ σε περίπτωση μη αποδοχής, απαιτεί όλα τα δυνατά μονοπάτια να μην καταλήγουν σε κατάσταση αποδοχής. Είναι ήδη φανερό ότι ο ορίσμος της αποδοχής ή όχι μιας συμβολοσειράς είναι κάθε άλλο παρά συμμετρικός με τον ορισμό που είχαμε δώσει στη ντετερμινιστική μηχανή. Αυτό γίνεται ακόμα πιο έντονο στην περίπτωση που θελήσουμε να ορίσουμε πότε μια μη ντετερμινιστική μηχανή αποδέχεται μια γλώσσα. Στην περίπτωση του μη ντετερμινισμού οι έννοιες <<αποφασίζω>> και <<αποδέχομαι>> μια γλώσσα έχουν πλέον την ίδια σημασία. Ο ορισμός είναι ο ακόλουθος:

Ορισμός 4 Έστω $L\subseteq (\Sigma \setminus\{ \sqcup \})^*$ μία γλώσσα. Μία μη ντετερμινιστική μηχανή Turing $M$ αποδέχεται την $L$ αν για κάθε συμβολοσειρά $x\in L$ , υπάρχει μία τουλάχιστον ακολουθία μεταβάσεων που οδηγεί την $M$ σε κατάσταση αποδοχής. Αντίθετα, για κάθε συμβολοσειρά $x\notin L$ , καμία ακολουθία μεταβάσεων δεν οδηγεί σε κατάσταση αποδοχής.

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

Στην πραγματικότητα η μη ντετερμινιστική μηχανή Turing δεν είναι ένα ρεαλιστικό μοντέλο υπολογισμού. Ωστόσο, πρόκειται για ένα ισχυρό μοντέλο η αξία του οποίου βρίσκεται στη δυνατότητα που παρέχει για επιπλέον ανάλυση της πολυπλοκότητας των προβλημάτων. Το βασικό στοιχείο του μη ντετερμινισμού είναι η διαδικασία <<μάντεψε και επαλήθευσε>>. Αυτό που ουσιαστικά κάνει μια μη ντετερμινιστική μηχανή Turing είναι να μαντεύει μια ακολουθία βημάτων (με άλλα λόγια, να μαντεύει τη λύση) και στη συνέχεια να επαληθεύει ότι αυτή η ακολουθία βημάτων είναι η σωστή. Είναι σαν να ρωτάει κάθε φορά κάποιο μαντείο ποια πορεία να ακολουθήσει στο δέντρο του υπολογισμού. Το μαντείο γνωρίζει την ύπαρξη ή όχι του σωστού μονοπατιού και, εφ' όσον υπάρχει, θα κατευθύνει τον υπολογισμό σε αυτό.

Θα αποδείξουμε στη συνέχεια μια πρόταση που συνδέει κάθε μη ντετερμινιστική μηχανή Turing με μια ισοδύναμη ντετερμινιστική μηχανή Turing. Θυμίζουμε ότι δυο μηχανές είναι ισοδύναμες αν αναγνωρίζουν την ίδια γλώσσα, δηλαδή αν αποδέχονται ακριβώς τις ίδιες συμβολοσειρές.

Θεώρημα 2 Για κάθε μη ντετερμινιστική μηχανή Turing υπάρχει ισοδύναμη ντετερμινιστική μηχανή Turing.

Απόδειξη Έστω $N=(K, \Sigma , \Delta ,s)$ μια μη ντετερμινιστική μηχανή Turing. Θα κατασκευάσουμε μια ντετερμινιστική μηχανή Turing $M$ η οποία θα είναι ισοδύναμη με την $N$ . Η $M$ θα πρέπει να προσομοιώνει κάθε δυνατό μη ντετερμινιστικό υπολογισμό της $N$ . Η βασική ιδέα της προσομοίωσης είναι η εξής: Κάθε υπολογισμός της $N$ είναι μια ακολουθία από μη ντετερμινιστικές επιλογές. Αν $d$ είναι ο βαθμός του μη ντετερμινισμού της $N$ (το μέγιστο πλήθος επιλογών της μηχανής σε κάθε βήμα της), τότε κάθε ακολουθία από $t$ το πλήθος μη ντετερμινιστικές επιλογές της $N$ (δηλαδή κάθε μονοπάτι μήκος $t$ στο δέντρο του μη ντετερμινιστικού υπολογισμού της $N$ ) δεν είναι τίποτε άλλο παρά μια ακολουθία από $t$ ακεραίους $c_1 c_2 \cdots c_t$ , όπου $c_i \in \{0, 1, \ldots, d\}$ για κάθε $i = 1, 2, \ldots, t$ .

Έτσι, για παράδειγμα, στο παρακάτω δέντρο η ακολουθία $131$ δηλώνει ότι η μηχανή ξεκινώντας από τη ρίζα του δέντρου, επιλέγει τον πρώτο απόγονο, στη συνέχεια τον τρίτο απόγονο αυτού και τέλος τερματίζει στον πρώτο (και μοναδικό) απόγονο του προηγούμενου κόμβου.

Η ντετερμινιστική μηχανή $M$ πρέπει να λαμβάνει υπόψη της όλες τις δυνατές ακολουθίες επιλογών και να προσομοιώνει τη λειτουργία της $N$ για κάθε μια από αυτές. Έτσι, ουσιαστικά η $M$ θα διασχίσει όλο (στη χειρότερη περίπτωση) το δέντρο του μη ντετερμινιστικού υπολογισμού της $N$ . Με ποιό τρόπο η $M$ θα πρέπει να επισκεφτεί τους κόμβους του δέντρου; Ο ορθός τρόπος είναι η κατά πλάτος επίσκεψη των κόμβων του δέντρου και όχι η κατά βάθος, διότι είναι πιθανό κάποιο μονοπάτι να μην καταλήγει ποτέ σε τερματική κατάσταση και η μηχανή να πέσει σε ατέρμονο βρόχο. Συνεπώς η ντετερμινιστική μηχανή $M$ θα θεωρεί τις ακολουθίες των μη ντετερμινιστικών επιλογών της $N$ σε αύξουσα διάταξη αναφορικά με το μήκος τους. Έτσι, στην αρχή θα επισκεφτεί όλους τους κόμβους του πρώτου επιπέδου, στη συνέχεια όλους τους κόμβους του δεύτερου επιπέδου, κ.ο.κ. Κάθε φορά η μηχανή θα προσομοιώνει τη λειτουργία της μηχανής $N$ . Αν η $N$ αποδεχθεί την είσοδο (δηλαδή το μονοπάτι καταλήγει σε κατάσταση αποδοχής), τότε η $M$ αποδέχεται την είσοδο και τερματίζει. Διαφορετικά, συνεχίζει τον υπολογισμό προσομοιώνοντας τη λειτουργία της $N$ για την επόμενη ακολουθία επιλογών. Η γέννηση της επόμενης ακολουθίας επιλογών ισοδυναμεί με τον υπολογισμό του επόμενου $d$ -αδικού θετικού ακεραίου. Αν μια ακολουθία δεν αντιστοιχεί σε έγκυρο υπολογισμό (δηλαδή δεν υπάρχει το αντίστοιχο μονοπάτι στο δέντρο) τότε η $M$ προχωρά στην επόμενη ακολουθία στη διάταξη.

Η ντετερμινιστική μηχανή $M$ , λοιπόν, θα αποτελείται από $3$ ταινίες, όπως φαίνεται στο παρακάτω σχήμα:

Η 1η ταινία είναι ταινία μόνο ανάγνωσης και περιέχει την συμβολοσειρά εισόδου $w$ . Στη 2η ταινία η $M$ προσομοιώνει τη λειτουργία της $N$ με είσοδο $w$ και σύμφωνα με την ακολουθία επιλογών που προσδιορίζει το περιεχόμενο της 3ης ταινίας. Τέλος, η 3η ταινία περιέχει έναν θετικό $d$ -αδικό ακέραιο που αντιστοιχεί στην ακολουθία των μη ντετερμινιστικών επιλογών της $N$ .

Αρχικά η 1η ταινία περιέχει τη συμβολοσειρά εισόδου $w$ , ενώ η 2η και 3η ταινία είναι κενές. Η $M$ αντιγράφει το $w$ στη 2η ταινία και παράγει τον πρώτο $d$ -αδικό ακέραιο στην 3η ταινία. Στη συνέχεια στη 2η ταινία προσομοιώνει τη λειτουργία της $N$ με είσοδο $w$ σύμφωνα με την ακολουθία επιλογών που ορίζει το περιεχόμενο της 3ης ταινίας. Αν η $N$ αποδεχθεί την είσοδο, τότε και η $M$ αποδέχεται την είσοδο και τερματίζει. Διαφορετικά, αντίγράφει το $w$ στη 2η ταινία, παράγει τον επόμενο $d$ -αδικό ακέραιο στην 3η ταινία και προσομοιώνει τη λειτουργία της $N$ για τη νέα ακολουθία επιλογών.

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

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

Αρχή της σελίδας

H αρχή της διαγωνοποίησης

Η αρχή της διαγωνιοποίησης (diagonalization principle) αποτελεί μία απο τις θεμελειώδεις τεχνικές απόδειξης, μαζί με την μαθηματική επαγωγή (mathematical induction) και την αρχή του περιστεριώνα (pigeonhole principle). Την τεχνική αυτή θα χρησιμοποιήσουμε για να αποδείξουμε το πρώτο μας μη επιλύσιμο πρόβλημα, ένα πρόβλημα δηλαδή για το οποίο αποδεδειγμένα δεν υπάρχει αλγόριθμος που να το επιλύει.

Η αρχή της διαγωνιοποίησης προτάθηκε το 1873 από τον Ρώσο μαθηματικό Georg Cantor στην προσπάθεια του να συγκρίνει τα μεγέθη μη πεπερασμένων συνόλων. Το πρόβλημα είναι απλό στην περίπτωση που τα σύνολα είναι πεπερασμένα: Το μέγεθος ενός πεπερασμένου συνόλου είναι ο πληθικός αριθμός του (το πλήθος των στοιχείων του), οπότε αρκεί κανείς να μετρήσει το πλήθος των στοιχείων του για να βρει το μέγεθος του. Αν όμως το σύνολο είναι μη πεπερασμένο, έχει άπειρο πλήθος στοιχείων οπότε ο πληθικός αριθμός αυτού δεν είναι δυνατό να υπολογιστεί. Συνεπώς δεν είναι δυνατό να υπολογίσουμε το μέγεθος ενός μη πεπερασμένου συνόλου μετρώντας τα στοιχεία του. Στην περίπτωση της σύγκρισης, ωστόσο, των μεγεθών δύο συνόλων (πεπερασμένων ή μη), η μέτρηση του μεγέθους αυτών δεν είναι απαραίτητη. Αυτό που μας ενδιαφέρει είναι τα σχετικά μεγέθη των δύο συνόλων. Δυο πεπερασμένα σύνολα έχουν το ίδιο μέγεθος αν μπορούμε να <<ζευγαρώσουμε>> κάθε στοιχείο του πρώτου συνόλου με ακριβώς ένα στοιχείο του δεύτερου συνόλου έτσι ώστε όλα τα στοιχεία του πρώτου και του δεύτερου συνόλου τελικά να έχουν το ταίρι τους. Η ιδέα αυτή μπορεί να επεκταθεί και για μη πεπερασμένα σύνολα. Δίνουμε τους απαραίτητους μαθηματικούς ορισμούς στη συνέχεια.

Ορισμός 5 Έστω δυο σύνολα $A$ και $B$ και μια συνάρτηση $f : A \to B$ .

1. Η συνάρτηση $f$ καλείται αμφιμονοσήμαντη (ένα-προς-ένα) αν για κάθε $a, b \in A, a\neq b \Rightarrow f(a) \neq f(b).$

2. Η συνάρτηση $f$ καλείται επί αν $f(A) = B$ , δηλαδή για κάθε $b \in B$ υπάρχει $a \in A$ τέτοιο ώστε $f(a) = b.$

3. Η συνάρτηση $f$ καλείται αντιστοιχία αν είναι αμφιμονοσήμαντη και επί.

Αν μια συνάρτηση $f : A \to B$ είναι αντιστοιχία τότε κάθε στοιχείο του συνόλου $A$ αντιστοιχεί σε μοναδικό στοιχείο του συνόλου $B$ και κάθε στοιχείο του $B$ έχει μοναδικό στοιχείο του $A$ που αντιστοιχεί σε αυτό.

Ορισμός 6 Δύο σύνολα $A$ και $B$ έχουν το ίδιο μέγεθος αν υπάρχει αντιστοιχία $f : A \to B$ .

Πρόταση 1 Το σύνολο των φυσικών αριθμών $\mathbb{N} = \{ 1, 2, 3, \ldots \}$ και το σύνολο των άρτιων αριθμών $\mathbb{E} = \{ 2, 4, 6, \ldots \}$ έχουν το ίδιο μέγεθος.

Απόδειξη Θεωρούμε την απλή αντιστοιχία $f : \mathbb{N} \to \mathbb{E}$ με $f(n) = 2n$ για κάθε $n \in \mathbb{N}$ . Η αντιστοίχιση των στοιχειών των δύο συνολών φαίνεται στον παρακάτω πίνακα.

$n$	$f(n)$
$1$	$2$
$2$	$4$
$3$	$6$
$4$	$8$
$\vdots$	$\vdots$

Σύμφωνα με τον ορισμό του Cantor, τα σύνολα $\mathbb{N}$ και $\mathbb{E}$ έχουν το ίδιο μέγεθος (ακόμα κι αν το πρώτο είναι υπερσύνολο του δεύτερου!).

Ορισμός 7 Το σύνολο $A$ καλείται μετρήσιμο αν είναι πεπερασμένο ή έχει το ίδιο μέγεθος με το $\mathbb{N}$ .

Σύμφωνα με την προηγούμενη πρόταση, το σύνολο των άρτιων αριθμών είναι μετρήσιμο. Είναι εύκολο να δεί κανείς ότι το ίδιο ισχύει και για το σύνολο των περιττών αριθμών $\mathbb{O} = \{ 1, 3, 5, \ldots \}$ .

Το σύνολο των ρητών αριθμών $\mathbb{Q} = \{ \frac{m}{n} | m,n \in \mathbb{N} \}$ είναι μετρήσιμο.

Απόδειξη Το σύνολο $\mathbb{Q}$ είναι μη πεπερασμένο, οπότε θα πρέπει να δείξουμε ότι έχει το ίδιο μέγεθος με το $\mathbb{N}$ , δηλαδή να ορίσουμε μια αντιστοιχία $f : \mathbb{Q} \to \mathbb{N}$ που να αντιστοιχεί τους φυσικούς αριθμούς στους ρητούς. Ένας εύκολος τρόπος δημιουργήσουμε μια λίστα με όλους τους ρητούς αριθμούς και στη συνέχεια να αντιστοιχίσουμε τον αριθμό $1$ με τον πρώτο αριθμό στη λίστα, τον αριθμό $2$ με τον δεύτερο αριθμό στη λίστα, κ.ο.κ. Πρέπει ωστόσο να προσέξουμε κάθε ρητός αριθμός να εμφανίζεται μόνο μια φορά στη λίστα.

Ας θεωρήσουμε ένα μη πεπερασμένο πίνακα από κλασματικούς αριθμούς όπου η $i$ -οστή γραμμή του περιέχει αριθμούς με αριθμητή $i$ και η $j$ -οστή στήλη του περιέχει αριθμούς με παρανομαστή $j$ . Έτσι, ο αριθμός $\frac{i}{j}$ θα είναι το στοιχείο της $i$ -οστής γραμμής και της $j$ -οστής γραμμής του πίνακα.

Ένας τρόπος για να πάρουμε τη λίστα των ρητών αριθμών είναι να ξεκινήσουμε με τα στοιχεία της πρώτης γραμμής του πίνακα. Ωστόσο, η πρώτη γραμμή περιέχει μη πεπερασμένο πλήθος στοιχείων, οπότε στη λίστα δεν θα συμπεριλάβουμε ποτέ τα στοιχεία των υπολοίπων γραμμών. Το ίδιο ισχύει και για τις στήλες του πίνακα. Ο σωστός τρόπος είναι να εισάγουμε στη λιστα τα στοιχεία σύμφωνα με τη σειρά που εμφανίζονται στις διαγωνίους του πίνακα: ξεκινάμε από την πρώτη διαγώνιο, επάνω αριστερα στον πίνακα (που περιέχει μόνο το στοιχείο $\frac{1}{1}$ ), στη συνέχεια με την δεύτερη διαγώνιο (που περιέχει τα στοιχεία $\frac{2}{1}$ και $\frac{1}{2}$ , κ.ο.κ. Προσέχουμε ωστόσο, κάθε φορά, κα μην εισάγουμε στη λίστα στοιχεία των διαγωνίων τα οποία υπάρχουν ήδη στη λίστα, όπως συμβαίνει για παράδειγμα με το στοιχείο $\frac{2}{2}$ της τρίτης διαγωνίου.

Μπορέσαμε, έτσι, να βρούμε μια αντιστοιχία μεταξύ του συνόλου $\mathbb{N}$ των φυσικών αριθμών και του συνόλου $\mathbb{Q}$ των ρητών αριθμών. Αρα το σύνολο $\mathbb{Q}$ είναι μετρήσιμο.

Ίσως να έχει δημιουργηθεί η εντύπωση ότι όλα τα μη περεπασμένα σύνολα έχουν το ίδιο μέγεθος. Ωστόσο, όπως θα δούμε στη συνέχεια, αυτό δεν ισχύει. Συγκεκριμένα, ας θεωρήσουμε το σύνολο $\mathbb{R}$ των πραγματικών αριθμών. Θα χρησιμοποιήσουμε τη μέθοδο της διαγωνιοποίησης για να αποδείξουμε ότι το $\mathbb{R}$ είναι μη μετρήσιμο σύνολο. Η απόδειξη του θεωρήματος που ακολουθεί, όπως και η τεχνική της διαγωνιοποίησης, αποδίδεται στον Georg Cantor.

Πρόταση 3 Το σύνολο $\mathbb{R}$ των πραγματικών αριθμών είναι μη μετρήσιμο.

Απόδειξη Θα αποδείξουμε ότι δεν είναι δυνατή η ύπαρξη αντιστοιχίας από το $\mathbb{N}$ στο $\mathbb{R}$ . Ας υποθέσουμε ότι κάτι τέτοιο δεν ισχύει. Θα καταλήξουμε σε άτοπο.

Έστω ότι υπάρχει αντιστοιχια $f$ από το $\mathbb{N}$ στο $\mathbb{R}$ . Η $f$ αντιστοιχεί κάθε φυσικό αριθμό με ακριβώς έναν πραγματικό αριθμό και, επίσης, για κάθε πραγματικό αριθμό υπάρχει φυσικός αριθμός τον οποίο η $f$ αντιστοιχεί σε αυτόν. Μια τέτοια αντιστοιχία θα είναι όπως αυτή που παρουσιάζουμε στον πίνακα που ακολουθεί.

$n$	$f(n)$
$1$	$2.374284\ldots$
$2$	$35.458927\ldots$
$3$	$0.333333\ldots$
$4$	$123.543578\ldots$
$5$	$47.123456\ldots$
$6$	$0.999999\ldots$
$\vdots$	$\vdots$

Θα δείξουμε ότι υπάρχει πραγματικός αριθμός $x$ ο οποίος δεν έχει συμπεριληφθεί στην παραπάνω αντιστοιχία, δηλαδή, $x \not = f(n)$ για κάθε $n\in \mathbb{N}$ . Ο αριθμός αυτός θα πρέπει να είναι διαφορετικός από όλους τους αριθμούς που εμφανίζονται στη δεύτερη στήλη του πίνακα και προκύπτει αν αλλάξουμε τα ψηφία της διαγωνίου που αντιστοιχεί στο δεκαδικό μέρος του κάθε αριθμού. Έτσι μπορούμε να θέσουμε αυθαίρετα το 1ο δεκαδικό ψηφίο του $x$ ίσο με 7, έτσι ώστε ο $x$ να διαφέρει από τον αριθμό $f(1)=2.\underline{3}74284$ στο 1ο δεκαδικό ψηφίο (τουλάχιστον). Όμοια, μπορούμε να θέσουμε αυθαίρετα το 2ο δεκαδικό ψηφίο του $x$ ίσο με 3, έτσι ώστε ο $x$ να διαφέρει από το $f(2)=35.4\underline{5}8927$ στο 2ο δεκαδικό ψηφίο, κ.ο.κ. Έτσι, για παράδειγμα, ο αριθμός $x=0.736284\ldots$ δεν ανήκει στον παραπάνω πίνακα αφού διαφέρει από κάθε $f(n)$ στο $n$ -οστό δεκαδικό ψηφίο.

Συνεπώς δεν υπάρχει αντιστοιχία από το $\mathbb{N}$ στο $\mathbb{R}$ , οπότε το σύνολο $\mathbb{R}$ είναι μη μετρήσιμο.

Αρχή της σελίδας

Επιλύσιμα και μη επίλυσιμα προβλήματα

Πριν ασχοληθούμε με τη μελέτη της δυσκολίας επίλυσης υπολογιστικών προβλημάτων είναι απαραίτητο να αναφερθούμε σε ένα βασικό ερώτημα που αντιμετωπίζουμε κάθε φορά που μας ζητείται να λύσουμε ένα πρόβλημα: το πρόβλημα λύνεται; Ένα πρόβλημα είναι επιλύσιμο αν μπορεί να σχεδιαστεί κάποιος αλγόριθμος που να το επιλύει, δηλαδή μια σαφής και πεπερασμένου μήκους ακολουθία από ενέργειες που λύνουν το πρόβλημα. Ο ορισμός που δώσαμε για την έννοια του αλγορίθμου είναι διαισθητικός και χρησιμοποιείται από τα αρχαία χρόνια στην βιβλιογραφία για το σχεδιασμό αλγορίθμων που επιλύουν διαφόρων ειδών προβλήματα. Ωστόσο, ο διαισθητικός ορισμός του αλγορίθμου περιόριζε τους μαθηματικούς στο να κατανοήσουν πλήρως τους αλγορίθμους, γεγονός που έκανε επιτακτική την ανάγκη του αυστηρού ορισμό της έννοιας του αλγορίθμου.

Στις αρχές του 1900 όταν ο David Hilbert θέλησε να σχεδιάσει έναν αλγόριθμο ο οποίος να εξετάζει αν ένα πολυώνυμο έχει ακέραια λύση. Το πρόβλημα αυτό, γνωστό ως το δέκατο πρόβλημα του Hilbert, απαιτούσε γνώση του αυστηρού μαθηματικού ορισμού της έννοιας του αλγορίθμου. Ο ακριβής ορισμός δώθηκε το 1936 από τους Alonzo Church και Alan Turing. Ο Church όρισε την έννοια του αλγορίθμου μέσω του λογισμού λάμδα ( $\lambda$ calculus) και ο Turing μέσω μιας μηχανής, της γνωστής μας πλέον μηχανής Turing. Απεδείχθη ότι ο διαισθητικός ορισμός είναι ισοδύναμος με τον αυστηρό ορισμό της έννοιας του αλγορίθμου και η σχέση που συνδέει τους δυο ορισμούς καλείται Θέση των Church--Turing. Η θέση αυτή, με απλά λόγια, μας λέει ότι όλοι οι λογικοί ορισμοί που δόθηκαν για την έννοια του αλγορίθμου είναι μεταξύ τους ισοδύναμοι και, επιπλέον, κάθε λογικός ορισμός που ενδεχομένος δοθεί στο μέλλον θα είναι επίσης ισοδύναμος με ήδη υπάρχοντες.

Η ύπαρξη της καθολικής μηχανής Turing οδήγησε σύντομα σε προβλήματα τα οποία δεν έχουν λύση, προβλήματα για τα οποία αποδεδειγμένα δεν υπάρχει αλγόριθμος που να τα επιλύει. Ο λόγος που συμβαίνει αυτό είναι προφανής: υπάρχουν περισότερες γλώσσες (προβλήματα) από τις μηχανές Turing (αλγόριθμοι) που τις αποφασίζουν. Τα προβλήματα αυτά καλούνται \textit{μη επιλύσιμα} (unsolvable) ή μη αποκρίσιμα (undecidable) αν πρόκειται για προβλήματα απόφανσης, και οι γλώσσες που αντιστοιχούν σε αυτά είναι μη αναδρομικές.

Το πιο φημισμένο, ίσως, μη αποκρίσιμο πρόβλημα είναι το πρόβλημα του τερματισμού (the halting problem). Στο πρόβλημα αυτό δίνεται ένα πρόγραμμα μαζί με τις προδιαγραφές του (δηλαδή οδηγίες για το τι πρέπει να κάνει το πρόγραμμα) και μια είσοδος του προγράμματος και ζητείται απάντηση για το αν το πρόγραμα θα τερματίσει τη λειτουργία του για τη συγκεκριμένη είσοδο. Θα μελετήσουμε το πρόβλημα του τερματισμού στην ενότητα που ακολουθεί.

Κλείνοντας την παρούσα ενότητα να αναφέρουμε ότι το δέκατο πρόβλημα του Hilbert είναι μη επιλύσιμο, ένα αποτέλεσμα που εδόθη το 1970 από τον Yuri Matijasevic.

Αρχή της σελίδας

Το πρόβλημα του τερματισμού

Ο τυπικός ορισμός του προβλήματος του τερματισμού είναι ο ακόλουθος:

ΤΕΡΜΑΤΙΣΜΟΣ (HALTING)

Στιγμιότυπο:	Η κωδικοποίηση μιας μηχανής Turing $M$ και η κωδικοποίηση μιας συμβολοσειράς $x$ .
Ερώτηση:	Τερματίζει η $M$ με είσοδο $x$ ;

Η γλώσσα που αντιστοιχεί στο πρόβλημα του τερματισμού είναι η γλώσσα που περιλαμβάνει όλες τις συμβολοσειρές που κωδικοποιούν μια μηχανή Turing και μια είσοδο, έτσι ώστε η μηχανή να τερματίζει με αυτήν την είσοδο, δηλαδή, $H =\{ \langle M, x \rangle ~|~$ η $M$ τερματίζει με είσοδο $x \}$ = ${ \langle M, x \rangle ~|~ M(x) \neq \nearrow }.$

Είναι εύκολο να αποδείξουμε την ακόλουθη πρόταση:

Πρόταση 4 Η γλώσσα $H$ είναι αναδρομικά αριθμήσιμη.

Απόδειξη

Θα κατασκευάσουμε μηχανή Turing $M_H$ η οποία θα αναγνωρίζει τη γλώσσα $H$ . Η κατασκευή είναι απλή: H $M_H$ με είσοδο $\langle M, x \rangle$ θα προσομοιώνει τη λειτουργία της $M$ με είσοδο $x$ . Αν $M(x) \neq \nearrow$ τότε $M_H(\langle M, x \rangle)$ = ΝΑΙ, διαφορετικά $M_H(\langle M, x \rangle) = \nearrow.$ Είναι φανερό ότι η $M_H$ αναγνωρίζει τη γλώσσα $H$ , άρα $H$ είναι αναδρομικά αριθμήσιμη.

Είναι εύλογο να αναρωτηθεί κανείς αν η γλώσσα $H$ είναι και αναδρομική, δηλαδή αν το πρόβλημα του τερματισμού είναι αποκρίσιμο. Δείτε ότι η $H$ δεν είναι απλά μια αναδρομικά αριθμήσιμη γλώσσα αλλά έχει επιπλέον μια πολύ σημαντική ιδιότητα: αν υποθέσουμε ότι υπάρχει αλγόριθμος που επιλύει το πρόβλημα του τερματισμού, τότε μπορούμε να χρησιμοποιήσουμε κατάλληλα τον αλγόριθμο αυτό για να αποφασίσουμε κάθε αναδρομικά αριθμήσιμη γλώσσα $L$ , ως εξής: Έστω $M_H$ η υποτιθέμενη μηχανή Turing που αποφασίζει την γλώσσα $H$ και $M_L$ η μηχανή Turing που αναγνωρίζει την $L$ . Καλούμε την $M_H$ με είσοδο $\langle M_L, x \rangle$ . Αν η $M_H$ απορρίψει την είσοδο (η $M_L$ δεν τερματίζει με είσοδο $x$ ), τότε $x\not\in L$ . Διαφορετικά (η $M_L$ τερματίζει με είσοδο $x$ ), εκτελούμε την $M_L$ με είσοδο $x$ και αν $M_L(x)$ (x)= ΝΑΙ τότε $x\in L$ ενώ διαφορετικά $x\not\in L$ . Κατασκευάσαμε έτσι αλγόριθμο που αποφασίζει τη γλώσσα $L$ , άρα η $L$ είναι αναδρομική.

Δυστυχώς, όπως φανερώνει η επόμενη πρόταση, το πρόβλημα του τερματισμού είναι μη αποκρίσιμο.

Θεώρημα 3 Η γλώσσα $H$ δεν είναι αναδρομική.

Απόδειξη Ας υποθέσουμε ότι η γλώσσα $H$ είναι αναδρομική, υπάρχει δηλαδή μηχανή Turing, έστω $M_H$ , η οποία αποφασίζει την $H$ . Χρησιμοποιούμε την $M_H$ για να κατασκευάσουμε μηχανή Turing $D$ ως εξής: Η $D$ με είσοδο $\langle M \rangle$ ,

1. Προσομοιώνει τη λειτουργία της $M_H$ με είσοδο $\langle M, M \rangle$ .

2. Αν $M_H (\langle M, M \rangle) =$ ΝΑΙ, τότε $D(M) = \nearrow$ . Διαφορετικά, $D(M) =$ ΝΑΙ.

Σύμφωνα με την παραπάνω κατασκευή η μηχανή $D$ είτε αποδέχεται την είσοδο της είτε δεν τερματίζει ποτέ. Ας δούμε την λειτουργία της $D$ με είσοδο την κωδικοποίηση του εαυτού της.

Αν $D(\langle D \rangle) =$ ΝΑΙ τότε $M_H (\langle D, D \rangle) =$ ΟΧΙ, οπότε η $D$ δεν τερματίζει με είσοδο τον εαυτό της, δηλαδή $D(\langle D \rangle) = \nearrow.$ Επίσης, αν $D(\langle D \rangle) = \nearrow$ τότε $M_H (\langle D, D \rangle) =$ ΝΑΙ, οπότε η $D$ τερματίζει με είσοδο τον εαυτό της, δηλαδή $D(\langle D \rangle) =$ ΝΑΙ.

Η μηχανή $D$ , λοιπόν, με είσοδο $\langle D \rangle$ τερματίζει όταν δεν τερματίζει και δεν τερματίζει όταν τερματίζει! Καταλήξαμε σε άτοπο, λόγω της υπόθεσης της ύπαρξης της μηχανής $M_H$ που αποφασίζει τη γλώσσα $H$ . Συνεπώς δεν είναι δυνατή η ύπαρξη της $M_H$ , άρα η $H$ δεν είναι αναδρομική.

Η απόδειξη του προηγούμενου θεωρήματος ομοιάζει μη την τεχνική της διαγωνιοποίησης που χρησιμοποίησε ο Cantor για να αποδείξει ότι το σύνολο των πραγματικών αριθμών είναι μη μετρήσιμο. Ας θεωρήσουμε τον Πίνακα 1 όπου περιέχει όλα τα ζευγάρια $\langle M, M \rangle$ . Οι γραμμές του πίνακα είναι όλες οι μηχανές Turing ενώ οι στήλες του πίνακα είναι οι κωδικοποιήσεις αυτών. Δίνουμε τυχαίες τιμές στα στοιχεία του πίνακα, ανάλογα με το αν η μηχανή $M_i$ τερματίζει ή οχι με είσοδο $\langle M_j \rangle$ . Η μηχανή $D$ αποτελεί και αυτή στοχείο του πίνακα και, σύμφωνα με τον τρόπο που την κατασκευάσαμε, αλλάζει τα διαγώνια στοιχεία του Πίνακα 1. Για παράδειγμα, θα είναι $D(\langle M_1 \rangle) = \nearrow$ αφού $M_1(\langle M_1 \rangle) =$ ΝΑΙ. Όταν θελήσουμε να συμπληρώσουμε το στοιχείο $D(\langle D \rangle)$ καταλήγουμε σε αντίφαση.

	$\langle M_1 \rangle$	$\langle M_2 \rangle$	$\langle M_3 \rangle$	$\langle M_4 \rangle$	$\langle M_5 \rangle$	$\cdots$	$\langle D \rangle$	$\cdots$
$M_1$	$\underline{NAI}$	NAI	$\nearrow$	NAI	$\nearrow$	$\nearrow$
$M_2$	NAI	$\underline{\nearrow}$	$\nearrow$	NAI	NAI		NAI
$M_3$	$\nearrow$	NAI	$\underline{NAI}$	$\nearrow$	NAI		$\nearrow$
$M_4$	NAI	NAI	$\nearrow$	$\underline{\nearrow}$	$\nearrow$	$\cdots$	$\nearrow$	$\cdots$
$M_5$	$\nearrow$	$\nearrow$	$NAI$	$NAI$	$\underline{NAI}$		NAI
$\vdots$				$\vdots$
$D$	$\nearrow$	NAI	$\nearrow$	NAI	$\nearrow$		$\underline{?}$
$\vdots$				$\vdots$				$\ddots$

Ο υπολογισμός της $M_i$ με είσοδο $\langle M_j \rangle$ , $i,j =1,2,\dots$

Αρχή της σελίδας

Μη αποκρισιμότητα

Συμβολίζουμε με $R$ την κλάση των αναδρομικών γλωσσών και με $RE$ την κλάση των αναδρομικά αριθμήσιμων γλωσσών.\footnote{Ίσως έγινε ήδη εμφανές ότι μια κλάση γλωσσών (ή προβλημάτων) δεν είναι τίποτε άλλο παρά ένα σύνολο γλωσσών με κοινά χαρακτηριστικά και ιδιότητες (π.χ., αναγνωρίζονται από μηχανές Turing). Θα ορίσουμε αντίστοιχες κλάσεις σε επόμενα κεφάλαια, όταν θελήσουμε να μελετήσουμε την {πολυπλοκότητα} των προβλημάτων.} Γνωρίζουμε ότι κάθε αναδρομική γλώσσα είναι και αναδρομικά αριθμήσιμη, οπότε $R$ $\subseteq$ $RE$ . Στην πραγματικότητα ισχύει ότι $R$ $\subset$ $RE$ } αφού στην προηγούμενη ενότητα αποδείξαμε ότι $H \in RE$ (Πρόταση~\ref{HinRE}) ενώ $H \not\in R$ (Θεώρημα~\ref{HnotinR}).

Έχουμε ήδη αποδείξει κάποιες προτάσεις που συνδέουν τις κλάσεις $R$ και $RE:$

Πρόταση 5

Αν η γλώσσα $L$ είναι αναδρομική τότε και $\overline{L}$ είναι αναδρομική.

Πρόταση 6

H γλώσσα $L$ είναι αναδρομική αν και μόνο αν οι γλώσσες $L$ και $\overline{L}$ είναι αναδρομικά αριθμήσιμες.

Η Πρόταση 5 φανερώνει ότι η κλαση των αναδρομικών γλωσσών είναι κλειστή ως προς το συμπλήρωμα.\footnote{Θυμηθείτε ότι έχουμε αποδείξει αντίστοιχες προτάσεις αναφορικά με την ένωση και την τομή αναδρομικών ή αναδρομικά αριθμήσιμων γλωσσών.} Κάτι τέτοιο ωστόσο δεν ισχύει για την κλάση των αναδρομικά αριθμήσιμων γλωσσών: Ας θεωρήσουμε τη γλώσσα $\overline{H}$ , το συμπλήρωμα της γλώσσας $H$ . Η $\overline{H}$ δεν είναι αναδρομικά αριθμήσιμη διότι, διαφορετικά, σύμφωνα με την Πρόταση 6, η $H$ θα ήταν αναδρομική. Στο Σχήμα 1 παρουσιάζουμε τις κλάσεις $R$ και $RE$ . Η κλάση $coRE$ περιέχει τα συμπληρώματα των αναδρομικά αριθμήσιμων γλωσσών. Έχουμε συναντήσει αρκετές γλώσσες στο $R$ και $RE$ . Επίσης δείξαμε ότι $H \in RE$ $\setminus R$ ( η $H$ είναι αναδρομικά αριθμήσιμη αλλά όχι αναδρομική) ενώ είναι εύκολο να δούμε ότι $\overline{H} \in coRE \setminus R$ .

Σχήμα 1: Οι κλάσεις των αναδρομικών και αναδρομικά αριθμήσιμων γλωσσών.

Γνωρίζοντας ότι ένα πρόβλημα είναι μη αποκρίσιμο μπορούμε να αποδείξουμε ότι και άλλα προβλήματα είναι μη αποκρίσιμα χρησιμοποιώντας την μέθοδο της αναγωγής (reduction). Θα λέμε ότι το πρόβλημα $\Pi_1$ ανάγεται στο πρόβλημα $\Pi_2$ αν υπάρχει ένας κατάλληλος μετασχηματισμός που μετατρέπει κάθε νόμιμο στιγμιότυπο του $\Pi_1$ σε νόμιμο στιγμιότυπο του $\Pi_2$ έτσι ώστε μια λύση του $\Pi_2$ να αντιστοιχεί σε λύση του $\Pi_1$ . Υποθέτοντας ότι υπάρχει μια τέτοια αναγωγή του προβλήματος $\Pi_1$ στο πρόβλημα $\Pi_2$ , τότε

1.αν το $\Pi_2$ είναι αποκρίσιμο, τότε και το $\Pi_1$ είναι αποκρίσιμο, ενώ

2.αν το $\Pi_1$ είναι μη αποκρίσιμο, τότε και το $\Pi_2$ είναι μη αποκρίσιμο.

Στην πραγματικότητα η αναγωγή του προβλήματος $\Pi_1$ στο πρόβλημα $\Pi_2$ φανερώνει ότι το $\Pi_2$ είναι τουλάχιστον τόσο δύσκολο όσο το $\Pi_1$ . Θα χρησιμοποιήσουμε την τεχνική της αναγωγής σε επόμενα κεφάλαια όταν θα μελετήσουμε τη δυσκολία επίλυσης των προβλημάτων. Όσο αφορά στη μη αποκρισιμότητα, για να αποδείξούμε ότι ένα πρόβλημα είναι μη αποκρίσιμο ακολουθούμε την εξής διαδικασία: Επιλέγουμε ένα μη αποκρίσιμο πρόβλημα, έστω το $\Pi_1$ , και το ανάγουμε στο πρόβλημα που θέλουμε να δείξουμε ότι είναι μη αποκρίσιμο, έστω το $\Pi_2$ : Υποθέτουμε ότι υπάρχει αλγόριθμος που επιλύει το $\Pi_2$ και κατασκευάζουμε αλγόριθμο που επιλύει το $\Pi_1$ --- άτοπο!

Η επιλογή του κατάλληλου μη αποκρίσιμου προβλήματος απαιτεί εξοικείωση και πείρα στις αναγωγές. Μέχρι στιγμής γνωρίζουμε ένα μόνο μη αποκρίσιμο πρόβλημα, το πρόβλημα του τερματισμού. Θα χρησιμοποιήσουμε αυτό για να αποδείξουμε κι άλλα μη αποκρίσιμα προβλήματα.

Το πρόβλημα της αποδοχής (the acceptance problem) ορίζεται ως το πρόβλημα στο οποίο δοθείσης μιας μηχανής Turing $M$ και μιας συμβολοσειράς $x$ , ζητείται να αποφανθούμε αν η μηχανή $M$ αποδέχεται τη συμβολοσειρά $x$ . Σε μορφή γλώσσας, το πρόβλημα της αποδοχής ορίζεται ως

$A = \{ \langle M, x \rangle |$ η $M$ αποδέχεται τη συμβολοσειρά $x$ }.

Θα αποδείξουμε ότι δεν υπάρχει αλγόριθμος που να επιλύει το πρόβλημα της αποδοχής, δηλαδή ότι το πρόβλημα αυτό είναι μη αποκρίσιμο.

Θεώρημα 4

Η γλώσσα $A$ είναι μη αναδρομική.

Απόδειξη

Η απόδειξη ομοιάζει με αυτήν του προβλήματος του τερματισμού. Έστω ότι η γλώσσα $A$ είναι αναδρομική. Τότε υπάρχει μηχανή Turing, έστω $M_A$ , η οποία αποφασίζει την $A$ . Χρησιμοποιούμε την $M_A$ για να κατασκευάσουμε μηχανή Turing $D$ ως εξής: Η $D$ με είσοδο $\langle M \rangle$ ,

1. Προσομοιώνει τη λειτουργία της $M_A$ με είσοδο $\langle M, M \rangle$ . 2. Αν $M_A (\langle M, M \rangle) =$ ΝΑΙ τότε $D(M) =$ ΟΧΙ. Διαφορετικά, $D(M) =$ ΝΑΙ.

Σύμφωνα με την παραπάνω κατασκευή η μηχανή $D$ είτε αποδέχεται την είσοδο της είτε την απορρίπτει. Ας δούμε τον υπολογισμό της $D$ με είσοδο την κωδικοποίηση του εαυτού της.

Αν $D(\langle D \rangle) =$ ΝΑΙ} τότε $M_A (\langle D, D \rangle) =$ OXI, οπότε η $D$ δεν αποδέχεται την κωδικοποίηση του εαυτού της, δηλαδή $D(\langle D \rangle) =$ ΟΧΙ. Επίσης, αν $D(\langle D \rangle) =$ OXI τότε $M_A (\langle D, D \rangle) =$ ΝΑΙ, οπότε η $D$ αποδέχεται την κωδικοποίηση του εαυτού της, δηλαδή $D(\langle D \rangle) =$ NAI.

Η μηχανή $D$ , λοιπόν, με είσοδο $\langle D \rangle$ αποδέχεται όταν απορρίπτει και απορρίπτει όταν αποδέχεται! Καταλήξαμε σε άτοπο, λόγω της υπόθεσης της ύπαρξης της μηχανής $M_A$ που αποφασίζει τη γλώσσα $A$ . Συνεπώς δεν είναι δυνατή η ύπαρξη της $M_A$ , άρα η γλώσσα $A$ είναι μη αναδρομική.

Θα αποδείξουμε τώρα ένα ακόμα μη αποκρίσιμο πρόβλημα:

Άσκηση 12 Δείξτε ότι η παρακάτω γλώσσα είναι μη αναδρομική: $L$ = { $\langle M \rangle |$ η μηχανή Turing $M$ τερματίζει για κάθε είσοδο }.

θα ανάγουμε τη γλώσσα $H$ στη γλώσσα $L$ . Έστω ότι η $L$ είναι αναδρομική. Τότε υπάρχει μηχανή Turing, έστω $M_L$ , η οποία αποφασίζει την $L$ , δηλαδή

$M_L(\langle M \rangle) = \left\{ \begin{array}{ll} {\textrm NAI}, & \eta \ M \ \tau\epsilon\rho\mu\alpha\tau\iota\zeta\epsilon\iota \ \gamma\iota\alpha \ \kappa\alpha\theta\epsilon \ \epsilon\iota\sigma o \delta o, \\ {\textrm OXI}, & \delta\iota\alpha\phi o \rho\epsilon\tau\iota\kappa\alpha. \end{array} \right.$

Θα κατασκευάσουμε μηχανή Turing $M_H$ η οποία θα αποφασίζει τη γλώσσα $H$ , δηλαδή,

$M_H(\langle M,x \rangle) = \left\{ \begin{array}{ll} {\textrm NAI}, & \eta \ M \ \tau\epsilon\rho\mu\alpha\tau\iota\zeta\epsilon\iota\ \mu\epsilon\ \epsilon\iota\sigma o \delta o \ x \, \\ {\textrm OXI}, & \delta\iota\alpha\phi o \rho\epsilon\tau\iota\kappa\alpha. \end{array} \right.$

Η λειτουργία της $M_H$ θα είναι η εξής: η $M_H$ με είσοδο $\langle M, x \rangle$ ,

1. Κατασκευάζει μηχανή Turing $U$ η οποία με είσοδο $y$ ,

(a) Αν $y = x$ , προσομοιώνει τη λειτουργία της $M$ με είσοδο $x$ .

(b) Διαφορετικά, τερματίζει.

2. Εκτελεί την $M_L$ με είσοδο $\langle U \rangle$ .

3. Αν $M_L(\langle U \rangle)= NAI$ , τότε $M_H(\langle M, x \rangle)= NAI$ . Διαφορετικά, $M_H(\langle M, x \rangle)=OXI$ .

Η μηχανή $M_H$ αποφασίζει τη γλώσσα $H$ . Πράγματι, $M_H(\langle M, x \rangle)=NAI$ $\Leftrightarrow M_L(\langle U \rangle)= NAI$ , δηλαδή αν και μόνο αν η $U$ τερματίζει για κάθε είσοδο, δηλαδή αν και μόνο αν η $M$ τερματίζει με είσοδο $x$ . Επίσης, $M_H(\langle M, x \rangle)=OXI$ $\Leftrightarrow M_L(\langle U \rangle)= OXI$ , δηλαδή αν και μόνο αν η $U$ δεν τερματίζει για κάθε είσοδο, δηλαδή αν και μόνο αν η $M$ δεν τερματίζει με είσοδο $x$ . Συνεπώς η γλώσσα $H$ είναι αναδρομική --- άτοπο. ʼAρα η γλώσσα $L$ είναι μη αναδρομική.

Άσκηση 13 Δείξτε ότι η παρακάτω γλώσσα είναι μη αναδρομική: ${L = \langle M \rangle |}$ η $M$ δεν αποδέχεται καμία είσοδο, δηλ. $L(M) = \emptyset$ .

θα ανάγουμε τη γλώσσα $A$ στην $L$ . Έστω ότι η $L$ είναι αναδρομική. Τότε υπάρχει μηχανή Turing, έστω $M_L$ , η οποία αποφασίζει τη γλώσσα $L$ , δηλαδή

$M_L(\langle M \rangle ) = \left\{ \begin{array}{ll} {\textrm NAI}, & \alpha\nu\ L(M)=\emptyset, \\ {\textrm OXI}, & \delta\iota\alpha\phi o \rho\epsilon\tau\iota\kappa\alpha. \end{array} \right.$

Θα κατασκευάσουμε μηχανή Turing $M_A$ η οποία θα αποφασίζει τη γλώσσα $A$ , δηλαδή,

$M_A(\langle M,x \rangle ) = \left\{ \begin{array}{ll} {\textrm NAI}, & \alpha\nu\ \eta \ M \ \alpha\pi o \delta\epsilon\chi\epsilon\tau\alpha\iota\ \tau\eta\ \sigma\upsilon\mu\beta o \lambda o \sigma\epsilon\iota\rho\alpha\ \ x,\ \\ {\textrm OXI}, & \delta\iota\alpha\phi o \rho\epsilon\tau\iota\kappa\alpha. \end{array} \right.$

Η λειτουργία της $M_A$ θα είναι η εξής: η $M_A$ με είσοδο $\langle M,x \rangle$ ,

1. Κατασκευάζει μηχανή Turing $U$ η οποία, με είσοδο $y$ , αγνοεί την είσοδο της και προσομοιώνει τη λειτουργία της $M$ με είσοδο $x$ .

2. Εκτελεί την $M_L$ με είσοδο $\langle U \rangle$ .

3. Αν $M_L(\langle U \rangle)= NAI$ , τότε $M_A(\langle M,x \rangle)= OXI$ . \\ Διαφορετικά, $M_A(\langle M, x \rangle) = NAI$ .

Πράγματι, $M_A(\langle M, x \rangle) = NAI \Leftrightarrow$ $M_L(\langle U \rangle) = OXI \Leftrightarrow L(U) \neq \emptyset$ , δηλαδή, αν και μόνο αν η $U$ αποδέχεται κάποια είσοδο, δηλαδή, αν και μόνο αν η $M$ αποδέχεται την είσοδο $x$ . Επίσης, $M_A(\langle M,x \rangle)= OXI$ $\Leftrightarrow M_E(\langle U \rangle)= NAI \Leftrightarrow L(U) = \emptyset$ , δηλαδή, αν και μόνο αν η $U$ δεν αποδέχεται καμία είσοδο, δηλαδή, αν και μόνο αν η $M$ δεν αποδέχεται την είσοδο $x$ . ʼAρα η $M_A$ αποφασίζει τη γλώσσα $A$ --- άτοπο. Συνεπώς, η γλώσσα $L$ είναι μη αναδρομική.

Άσκηση 14 Δείξτε ότι η παρακάτω γλώσσα είναι μη αναδρομική: $L = \langle M \rangle |$ η $M$ αποδέχεται κάθε είσοδο, δηλ. $L(M) = \Sigma^\ast\}$ .

θα ανάγουμε τη γλώσσα $A$ στην $L$ . Έστω ότι η $L$ είναι αναδρομική. Τότε υπάρχει μηχανή Turing, έστω $M_L$ η οποία αποφασίζει τη γλώσσα $L$ , δηλαδή

$M_L(\langle M \rangle ) = \left\{ \begin{array}{ll} {\textrm NAI}, & \alpha\nu\ \eta\ M\ \alpha\pi o\delta\epsilon\chi\epsilon\tau\alpha\iota\ \kappa\alpha\theta\epsilon\ \epsilon\iota\sigma o\delta o , \\ {\textrm OXI}, & \delta\iota\alpha\phi o \rho\epsilon\tau\iota\kappa\alpha. \end{array} \right.$

Θα κατασκευάσουμε μηχανή Turing $M_A$ η οποία θα αποφασίζει τη γλώσσα $A$ , δηλαδή

$M_A(\langle M,x \rangle ) = \left\{ \begin{array}{ll} {\textrm NAI}, & \alpha\nu\ \eta\ M\ \alpha\pi o\delta\epsilon\chi\epsilon\tau\alpha\iota\ \tau\eta\ \sigma\upsilon\mu\beta o \lambda o \sigma\epsilon\iota\rho\alpha\ \ x, \ \\ {\textrm OXI}, & \delta\iota\alpha\phi o \rho\epsilon\tau\iota\kappa\alpha. \end{array} \right.$

Η λειτουργία της $M_A$ θα είναι η εξής: η $M_A$ με είσοδο $\langle M,x\rangle$ ,

1. Κατασκευάζει μηχανή Turing $U$ η οποία με είσοδο $y$ , αγνοεί την είσοδο της και προσομοιώνει τη λειτουργία της $M$ με είσοδο $x$ .

2. Εκτελεί την $M_L$ με είσοδο $\langle U \rangle$ .

3. Αν $M_L(\langle U \rangle)= NAI$ , τότε $M_A(\langle M,x \rangle)=NAI$ .

Διαφορετικά, $M_A(\langle M,x \rangle)=OXI$ .

Η μηχανή $M_A$ αποφασίζει τη γλώσσα $A$ . Πράγματι, $M_A(\langle M,x \rangle)=NAI \Leftrightarrow M_L(\langle U \rangle)= NAI$ , δηλαδή αν και μόνο αν η $'$ αποδέχεται κάθε είσοδο, δηλαδή αν και μόνο αν η $M$ αποδέχεται τη συμβολοσειρά $x$ . Επίσης, $M_A(\langle M,x \rangle)=OXI$ $\Leftrightarrow M_L(\langle U \rangle)= OXI$ , δηλαδή αν και μόνο αν η $U$ δεν αποδέχεται κάθε είσοδο, δηλαδή αν και μόνο αν η $M$ δεν αποδέχεται τη συμβολοσειρά $x$ . Συνεπώς η γλώσσα $A$ είναι αναδρομική --- άτοπο. ʼAρα η γλώσσα $L$ είναι μη αναδρομική.

Άσκηση 15

Δείξτε ότι η παρακάτω γλώσσα είναι μη αναδρομική:

$L = \langle M \rangle |$ η $M$ αποδέχεται τη συμβολοσειρά $s$ .

θα ανάγουμε τη γλώσσα $A$ στην $L$ . Έστω ότι η $L$ είναι αναδρομική. Τότε υπάρχει μηχανή Turing, έστω $M_L$ , η οποία αποφασίζει τη γλώσσα $L$ , δηλαδή

$M_L(\langle M \rangle ) = \left\{ \begin{array}{ll} {\textrm NAI}, & \alpha\nu\ \eta\ M\ \alpha\pi o\delta\epsilon\chi\epsilon\tau\alpha\iota\ \tau\eta\ \sigma\upsilon\mu\beta o \lambda o \sigma\epsilon\iota\rho\alpha\ \ s, \ \\ {\textrm OXI}, & \delta\iota\alpha\phi o \rho\epsilon\tau\iota\kappa\alpha. \end{array} \right.$

Θα κατασκευάσουμε μηχανή $M_A$ η οποία θα αποφασίζει τη γλώσσα $A$ , δηλαδή

$M_A( \langle M, x \rangle ) = \left\{ \begin{array}{ll} {\textrm NAI}, & \alpha\nu\ \eta\ M\ \alpha\pi o\delta\epsilon\chi\epsilon\tau\alpha\iota\ \tau\eta\ \sigma\upsilon\mu\beta o \lambda o \sigma\epsilon\iota\rho\alpha\ \ x, \ \\ {\textrm OXI}, & \delta\iota\alpha\phi o \rho\epsilon\tau\iota\kappa\alpha. \end{array} \right.$

Η λειτουργία της $M_A$ θα είναι η εξής: η $M_A$ με είσοδο $\langle M, x \rangle$ ,

1. Κατασκευάζει μηχανή Turing $U$ η οποία με είσοδο $y$ ,

(a) Αν $y=s$ , προσομοιώνει τη λειτουργία της $M$ με είσοδο $x$ .

Διαφορετικά, απορρίπτει.

2. Εκτελεί την $M_L$ με είσοδο $\langle U \rangle$ .

3. Αν $M_L(\langle U \rangle)= NAI$ , τότε $M_A(\langle M,x \rangle) =NAI$ .

Διαφορετικά, $M_A(\langle M, x \rangle)=OXI$ .

Πράγματι, $M_A(\langle M, x \rangle)= NAI \Leftrightarrow M_L(\langle U \rangle) = NAI$ , δηλαδή, αν και μόνο αν η $U$ αποδέχεται την $s$ , δηλαδή, αν και μόνο αν η $M$ αποδέχεται την είσοδο $x$ . Επίσης, $M_A(\langle M, x \rangle) = OXI \Leftrightarrow M_L(\langle U \rangle)= OXI$ , δηλαδή, αν και μόνο αν η $U$ δεν αποδέχεται την $s$ , δηλαδή, αν και μόνο αν η $M$ δεν αποδέχεται την είσοδο $x$ . Συνεπώς, η $M_A$ αποφασίζει τη γλώσσα $A$ --- άτοπο. ʼAρα η γλώσσα $L$ είναι μη αναδρομική.

Αρχή της σελίδας

Αναδρομικά μη διαχωρίσιμες γλώσσες

Ορίσαμε ως R την κλάση των αναδρομικών γλωσσών και ως RE την κλάση αναδρομικά αριθμήσιμων γλωσσών. Δείξαμε ότι η κλάση R είναι κλειστή ως προς το συμπλήρωμα (δηλαδή μια γλώσσα είναι αναδρομική αν και μόνο αν το συμπλήρωμα της είναι αναδρομική γλώσσα) ενώ η κλάση RE δεν είναι. Έχουμε δει αρκετά παραδείγματα αναδρομικών γλωσσών, αποδείξαμε ότι $H \in RE \setminus R$ και $\overline{H} \in coRE \setminus R$ , όπου coRE είναι η κλάση που περιέχει τα συμπληρώματα των αναδρομικά αριθμήσιμων γλωσσών. Ας δούμε τώρα μια ιδιότητα που μπορεί να έχουν δυο ξένες μεταξύ τους γλώσσες $L_1$ και $L_2$ .\footnote{Οι γλώσσες $L_1$ και $L_2$ είναι ξένες μεταξύ τους αν γλώσσες $L_1 \cap L_2 = \emptyset$ .}

Ορισμός 8

Δύο γλώσσες $L_1$ και $L_2$ καλούνται αναδρομικά μη διαχωρίσιμες (recursively inseparable) εάν δεν υπάρχει αναδρομική γλώσσα $\mathcal R$ τέτοια ώστε $L_1 \cap \mathcal R = \emptyset$ και $L_2 \subset \mathcal R$ .

Αν υπάρχει μια τέτοια γλώσσα $\mathcal R$ , οι γλώσσες $L_1$ και $L_2$ καλούνται αναδρομικά διαχωρίσιμες. Στο Σχήμα 2 παρουσιάζουμε δυο αναδρομικά διαχωρίσιμες γλώσσες.

Σχήμα 2: Αναδρομικά διαχωρίσιμες γλώσσες

Είναι εύκολο να δούμε ότι οι γλώσσες $H$ και $\overline{H}$ είναι αναδρομικά μη διαχωρίσιμες. Ας δούμε ~~ ενα ακόμα παράδειγμα αναδρομικά μη διαχωρίσιμων γλωσσών.

Άσκηση 16

Να αποδειχθεί ότι οι γλώσσες $L_1 = \{ \langle M \rangle ~|~$ $M(\langle M \rangle) = NAI$ } και $L_2 = \{ \langle M \rangle ~|~$ $M(\langle M \rangle) = OXI$ } είναι αναδρομικά μη διαχωρίσιμες.

Απόδειξη Ας υποθέσουμε ότι οι $L_1$ και $L_2$ είναι αναδρομικά διαχωρίσιμες. Τότε υπάρχει αναδρομική γλώσσα $\mathcal R$ τέτοια ώστε $L_1 \cap \mathcal R = \emptyset$ και $L_2 \subset \mathcal R$ . Εφόσον η $\mathcal R$ είναι αναδρομική θα υπάρχει μηχανή Turing, έστω $M_{\mathcal R}$ , που αποφασίζει τη γλώσσα $\mathcal R$ , δηλαδή

$M_{\mathcal R}(x) = \left\{ \begin{array}{ll} {\textrm NAI}, & x \in \mathcal R, \\ {\textrm OXI}, & x \not \in \mathcal R. \\ \end{array} \right.$

Ας δούμε τον υπολογισμό της μηχανής $M_{\mathcal R}$ με είσοδο την κωδικοποίηση του εαυτού της, $\langle M_{\mathcal R} \rangle$ . Υπάρχουν δύο περιπτώσεις:

-- Αν $M_{\mathcal R}(\langle M_{\mathcal R} \rangle) = NAI$ τότε, εξ ορισμού της γλώσσας $L_1$ , θα είναι $\langle M_{\mathcal R} \rangle \in L_1$ . Όμως, $L_1 \cap \mathcal R = \emptyset$ , οπότε $\langle M_{\mathcal R} \rangle\not\in \mathcal R$ , δηλαδή, $M_{\mathcal R}(\langle M_{\mathcal R} \rangle) =OXI$ --- άτοπο!

-- Αν $M_{\mathcal R}(\langle M_R \rangle) = OXI$ τότε, εξ ορισμού της γλώσσας $L_2$ , θα είναι $\langle M_{\mathcal R} \rangle \in L_2$ . Όμως, $L_2 \subset \mathcal R$ , οπότε $\langle M_{\mathcal R} \rangle \in \mathcal R$ , δηλαδή, $M_{\mathcal R}(\langle M_{\mathcal R} \rangle) = NAI$ --- άτοπο!

Σε κάθε περίπτωση καταλήξαμε σε άτοπο. ʼAρα οι γλώσσες $L_1$ και $L_2$ είναι αναδρομικά μη διαχωρίσιμες.

Ας δούμε έναν εναλλακτικό τρόπο απόδειξης της πρότασης: Υποθέτουμε, όπως και πριν, ότι οι γλώσσες $L_1$ και $L_2$ είναι αναδρομικά διαχωρίσιμες, οπότε υπάρχει αναδρομική γλώσσα $\mathcal R$ τέτοια ώστε $L_1 \cap \mathcal R =\emptyset$ και $L_2 \subset \mathcal R$ . Εφόσον η $\mathcal R$ είναι αναδρομική, και η γλώσσα $L_2 \subset \mathcal R$ θα είναι αναδρομική. ʼAρα θα υπάρχει μηχανή Turing, έστω $M_2$ , που αποφασίζει την $L_2$ , δηλαδή

$M_2(x) = \left\{ \begin{array}{ll} {\textrm NAI}, & x \in L_2, \\ {\textrm OXI} & x \not \in L_2. \\ \end{array} \right.$

Ας δούμε τώρα τον υπολογισμό της $M_2$ με είσοδο την κωδικοποίηση του εαυτού της, $\langle M_2 \rangle$ . Υπάρχουν δύο περιπτώσεις:

Αν $M_2(\langle M_2 \rangle) = NAI$ τότε $\langle M_2 \rangle \in L_2$ , οπότε $M_2(\langle M_2 \rangle) = OXI$ --- άτοπο!

Αν $M_2(\langle M_2 \rangle) = OXI$ τότε $\langle M_2 \rangle \not \in L_2$ , οπότε $M_2(\langle M_2 \rangle) = NAI$ --- άτοπο!

Σε κάθε περίπτωση λοιπόν, καταλήξαμε σε άτοπο. ʼAρα οι γλώσσες $L_1$ και $L_2$ είναι αναδρομικά μη διαχωρίσιμες.

Αρχή της σελίδας

Κλάσεις πολυπλοκότητας

Έχουμε αναφερεί ήδη ότι για τη μελέτη της υπολογιστικής πολυπλοκότητας των υπολογιστικών προβλήματος θα χρησιμοποιήσουμε τη μηχανή Turing, ένα θεωρητικό υπολογιστικό μοντέλο που είναι ισοδύναμο με κάθε σύγχρονο υπολογιστικό μέσο. Για να μελετήσουμε τα υπολογιστικά προβλήματα και να τα κατηγοριοποιήσουμε ανάλογα με τη δυσκολία επίλυσης τους θα πρέπει να ορίσουμε πρώτα την έννοια του χρόνου (time) που διαρκεί ένας υπολογισμός αλλά και του χώρου (space) που απαιτεί μια μηχανή Turing.\footnote{Κάποιοι από τους ορισμούς που διατυπώνονται στις παρούσες σημειώσεις είναι διαφορετικοί από αυτούς που υπάρχουν στο σύγγραμμα διδασκαλίας. Αντικαταστήστε τους τελευταίους.}

Ορισμός 9 Ο χρόνος που απαιτεί μια ντετερμινιστική μηχανή Turing $M$ με είσοδο τη συμβολοσειρά $x$ είναι το πλήθος των βημάτων (κινήσεων) που κάνει η $M$ ξεκινώντας από την αρχική διαμόρφωση για τον υπολογισμό του $M(x)$ . Αν η $M$ αποκλίνει τότε ο χρόνος είναι ίσος με $\infty$ .

Στην περίπτωση της μη ντετερμινιστικής μηχανής Turing ο ορισμός του χρόνου είναι διαφορετικός (θυμηθείτε ότι ο τρόπος αποδοχής μιας μη ντετερμινιστικής μηχανής είναι διαφορετικός απο τον τρόπο αποδοχής μιας ντετερμινιστικής μηχανής):

Ορισμός 10 Ο χρόνος που απαιτεί μια μη ντετερμινιστική μηχανή Turing $M$ με είσοδο τη συμβολοσειρά $x$ είναι το μικρότερο πλήθος βημάτων που μπορεί να κάνει η $M$ ξεκινώντας από την αρχική διαμόρφωση για να φτάσει σε κατάσταση αποδοχής. Σε κάθε άλλη περίπτωση, ο χρόνος της $M$ είναι, συμβατικά, ίσος με $1$ .

Ορίζουμε τώρα την πολυπλοκότητα χρόνου (time complexity) μιας μηχανής Turing:

Ορισμός 11

Η πολυπλοκότητα χρόνου μιας μηχανής Turing $M$ (ντετερμινιστικής ή μη) είναι μια συνάρτηση $T_M: \mathbb{Z}_+ \to \mathbb{Z}_+$ που ορίζεται ως εξής:

$T_M(n)=\max \{ m: \exists x \in (\Sigma \setminus \{ \sqcup \})^*,$ $|x|=n$ έτσι ώστε ο χρόνος που απαιτεί η $M$ με είσοδο $x$ είναι $m$ .

Συνεπώς, ο χρόνος που απαιτεί μια μηχανή Turing με είσοδο μήκους $n$ είναι ο μέγιστος χρόνος πάνω σε όλες τις εισόδους μήκους $n$ . Συνήθως υποθέτουμε ότι $T_M(n)\ge n$ αφού $n$ βήματα πρέπει να κάνει η μηχανή μόνο για να διαβάσει όλα τα σύμβολα της εισόδου μήκους $n$ .

Για τον ορισμό του χώρου που απαιτεί μια μηχανή Turing θα ορίσουμε μια μικρή παραλλαγή της μηχανής Turing $k$ -ταινιών, τη μηχανή $k$ -ταινιών με είσοδο και έξοδο: πρόκειται για μια συνηθισμένη μηχανή με $k$ -ταινίες εκ των οποίων η πρώτη είναι μόνο ανάγνωσης (η ταινία εισόδου) και η τελευταία είναι μόνο εγγραφής (η ταινία εξόδου). Κατά τη διάρκεια του υπολογισμού της η μηχανή μπορεί να χρησιμοποιεί μόνο τα κύτταρα των υπολοίπων $k-2$ ταινιών. Χρησιμοποιούμε αυτό το μοντέλο υπολογισμού για να ορίσουμε το χώρο που απαιτεί ο υπολογισμός μιας μηχανής Turing.

Ορισμός 12

Ο χώρος που απαιτεί μια ντετερμινιστική μηχανή Turing $k$ '-ταινιών με είσοδο και έξοδο, $M$ , με είσοδο τη συμβολοσειρά $x$ ισούται με το πλήθος των κυττάρων που χρησιμοποιεί η $M$ στις $k-2$ τανίες της ξεκινώντας από την αρχική διαμόρφωση για τον υπολογισμό του $M(x)$ . Αν η $M$ αποκλίνει στο $x$ τότε ο χώρος είναι ίσος με $\infty$ .

Ο ορισμός του χώρου μιας μη ντετερμινιστικής μηχανής είναι ο ακόλουθος:

Ορισμός 13

Ο χώρος που απαιτεί μια μη ντετερμινιστική μηχανή Turing $k$ -ταινιών με είσοδο και έξοδο, $M$ , με είσοδο τη συμβολοσειρά $x$ είναι το μικρότερο πλήθος κυττάρων που μπορεί να χρησιμοποιήσει η $M$ ξεκινώντας από την αρχική διαμόρφωση για να φτάσει σε κατάσταση αποδοχής. Σε κάθε άλλη περίπτωση, ο χρόνος της $M$ είναι, συμβατικά, ίσος με $1$ .

Ορίζουμε τώρα την πολυπλοκότητα χώρου (space complexity) μιας μηχανής Turing:

Ορισμός 14

Η πολυπλοκότητα χώρου μιας μηχανής Turing $M$ (ντετερμινιστικής ή μη) είναι μια συνάρτηση $S_M: \mathbb{Z}_+ \to \mathbb{Z}_+$ που ορίζεται ως εξής:

$S_M(n)= \max \{ m: \exists x \in (\Sigma \setminus \{ \sqcup \})^*, |x|=n$ έτσι ώστε ο χώρος που απαιτεί η $M$ με είσοδο $x$ είναι $m$ }.

Για κάθε ντετερμινιστική μηχανή Turing $k$ -ταινιών, $M$ , πολυπλοκότητας χρόνου $f(n)$ , μπορούμε να κατασκευάσουμε μια ντετερμινιστική μηχανή Turing $k+2$ -ταινιών με είσοδο και έξοδο, $M'$ , η οποία αρχικά θα αντιγράφει την είδοσο στην πρώτη της ταινία, στη συνέχεια θα προσομοιώνει τη λειτουργία της $M$ στις επόμενες $k$ ταινίες και στο τέλος του υπολογισμού της θα αντιγράφει την έξοδο της $M$ στην τελευταία της ταινία. Η $M'$ είναι ισοδύναμη με την $M$ και λειτουργεί σε χρόνο $O(f(n))$ . Αποδείξαμε συνεπώς την ακόλουθη πρόταση:

Πρόταση 7 Για κάθε ντετερμινιστική μηχανή Turing $k$ -ταινιών πολυπλοκότητας χρόνου $f(n)$ υπάρχει ισοδύναμη ντετερμινιστική μηχανή Turing $k+2$ -ταινιών με είσοδο και έξοδο πολυπλοκότητας χρόνου $O(f(n))$ .

Έχουμε αποδείξει σε προηγούμενη ενότητα ότι για κάθε ντετερμινιστική μηχανή Turing $k$ -ταινιών υπάρχει ισοδύναμη ντετερμινιστική μηχανή Turing μιας ταινίας. Με βάση την προσομοίωση που είχαμε κάνει τότε μπορούμε να αποδείξουμε την ακόλουθη πρόταση:

Θεώρημα 5

Για κάθε ντετερμινιστική μηχανή Turing $k$ -ταινιών πολυπλοκότητρας χρόνου $f(n)$ υπάρχει ισοδύναμη ντετερμινιστική μηχανή Turing μιας ταινίας πολυπλοκότητας χρόνου $O(f(n)^2)$ .

Η προηγούμενη πρόταση φανερώνει ότι η αύξηση των ταινιών σε μια ντετερμινιστική μηχανή Turing δεν αυξάνει την υπολογιστική ικανότητα του μοντέλου μας. Αντιθέτως, αυτό δεν ισχύει στην περίπτωση του μη ντετερμινισμού. Είχαμε αποδείξει σε προηγούμενη ενότητα ότι για κάθε μη ντετερμινιστική μηχανή Turing υπάρχει ισοδύναμη ντετερμινιστική μηχανή. Με βάση την προσομοίωση που είχαμε κάνει τότε μπορούμε να αποδείξουμε την ακόλουθη πρόταση:

Θεώρημα 6

Για κάθε μη ντετερμινιστική μηχανή Turing πολυπλοκότητρας χρόνου $f(n)$ υπάρχει ισοδύναμη ντετερμινιστική μηχανή Turing πολυπλοκότητας χρόνου $O(2^{f(n)})$ .

Ας περάσουμε τώρα στην έννοια της κλάσης πολυπλοκότητας (complexity class). Μια κλάση πολυπλοκότητας δεν είναι τίποτε άλλο παρά ένα σύνολο γλωσσών με κοινές ιδιότητες. Υπάρχουν διάφορες παράμετροι που προσδιορίζουν μια κλάση πολυπλοκότητας. Κατ' αρχήν το μοντέλο του υπολογισμού. Έχουμε ήδη συμφωνήσει ότι θα χρησιμοποιούμε τη μηχανή Turing $k$ -ταινιών. Μια κλάση πολυπλοκότητας χαρακτηρίζεται επίσης από τον τρόπο του υπολογισμού, δηλαδή αν η μηχανή μας θα είναι ντετερμινιστική ή μη. Μια ακόμα παράμετρος είναι ο υπολογιστικός πόρος που θέλουμε να μετρήσουμε, δηλαδή τον χρόνο ή το χώρο της μηχανής Turing και τέλος, πρέπει να καθορίσουμε ένα φράγμα για τον υπολογισμό, δηλαδή μια συνάρτηση $f: \mathbb{Z}_+ \to \mathbb{Z}_+$ . Με βάση τα παραπάνω, μια κλάση πολυπλοκότητας ορίζεται ως εξής:

Ορισμός 15

Μια κλάση πολυπλοκότητας είναι το σύνολο των γλωσσών που αποφασίζονται από μια μηχανή Turing $k$ -ταινιών που λειτουργεί με τον κατάλληλο τρόπο (ντετερμινιστικά ή μη) έτσι ώστε, για οποιαδήποτε είσοδο $x$ , η μηχανή να χρειάζεται το πολύ $f(|x|)$ μονάδες υπολογιστικού πόρου (χρόνου ή χώρου), όπου $f: \mathbb{Z}_+ \rightarrow \mathbb{Z}_+$ είναι η συνάρτηση πολυπλοκότητας της μηχανής.

Ορίζουμε στη συνέχεια τέσσερεις γενικές κλάσεις πολυπλοκότητας, λαμβάνοντας υπόψη μας κάθε φορά τον τρόπο του υπολογισμού και τον υπολογιστικό πόρο που θέλουμε να μετρήσουμε:

Ορίζουμε σαν TIME $(f(n))$ το σύνολο των γλωσσών που αποφασίζονται από κάποια ντετερμινιστική μηχανή Turing με πολυπλοκότητα χρόνου $f(n)$ .

Ορίζουμε σαν NTIME $(f(n))$ $το σύνολο των γλωσσών που αποφασίζονται από κάποια μη ντετερμινιστική μηχανή Turing με πολυπλοκότητα χρόνου $f(n)$ .

Ορίζουμε σαν SPACE $(f(n))$ το σύνολο των γλωσσών που αποφασίζονται από κάποια ντετερμινιστική μηχανή Turing με πολυπλοκότητα χώρου $f(n)$ .

Ορίζουμε σαν NSPACE $(f(n))$ το σύνολο των γλωσσών $L$ που αποφασίζονται από κάποια μη ντετερμινιστική μηχανή Turing με πολυπλοκότητα χώρου $f(n)$ .

Ας δούμε κάποιες απλές σχέσεις που συνδέουν τις κλάσεις πολυπλοκότητας που μόλις ορίσαμε. Μπορούμε εύκολα να δούμε ότι TIME $(f(n)) \subseteq$ NTIME $(f(n))$ και SPACE $(f(n)) \subseteq$ NSPACE $(f(n))$ . Επίσης, σύμφωνα με το Θεώρημα 6,

TIME $(f(n)) \subseteq$ TIME $(2^{f(n)})$ .

Τέλος, μια ντετερμινιστική μηχανή Τuring πολυπλοκότητας χρόνου $f(n)$ δεν είναι δυνατό να χρησιμοποιήσει παραπάνω από $f(n)$ κύτταρα, άρα TIME $(f(n)) \subseteq$ SPACE $(f(n))$ .

Υπάρχουν καποίες αρκετά σημαντικές κλάσεις πολυπλοκότητας, όπως η κλάση $P$ , το σύνολο όλων των γλωσσών που μπορούν να αποφασιστούν από μια ντετερμινιστική μηχανή Turing $M$ με πολυπλοκότητα χρόνου $O(n^k)$ , όπου $k$ θετικός ακέραιος, δηλαδή, $P = \bigcup_k TIME (n^k)$ .

Η κλάση $P$ περιέχει τις γλώσσες που μπορούν να αποφασιστούν αποδοτικά, δηλαδή σε χρόνο ο οποίος φράσσεται από κάποιο πολυώνυμο στο μέγεθος της εισόδου.

Μια εξίσου σημαντική κλάση είναι η κλάση $NP$ , το σύνολο όλων των γλωσσών που μπορούν να αποφασιστούν από μια μη ντετερμινιστική μηχανή Turing $M$ με πολυπλοκότητα χρόνυο $O(n^k)$ , όπου $k$ θετικός ακέραιος, δηλαδή, $NP = \bigcup_k NTIME (n^k)$ .

Όπως θα δούμε σε επόμενη ενότητα, η κλάση $NP$ περιέχει τις γλώσσες που μπορούν να επαληθευτούν αποδοτικά, δηλαδή υπάρχει γι' αυτές επαληθευτής (verifier) που λειτουργεί σε χρόνο που φράσσεται από κάποιο πολυώνυμο στο μέγεθος της εισόδου.

Προφανώς $P \subseteq NP$ (αφού κάθε ντετερμινιστική μηχανή μπορεί να θεωρηθεί ως μη ντετερμινιστική όπου σε κάθε βήμα της έχει μία μόνο επιλογή) ενώ το κατά πόσο ισχύει ότι $P \neq NP$ παραμένει το σημαντικότερο αναπάντητο πρόβλημα στην θεωρητική Επιστήμη των Υπολογιστών.

Αρχή της σελίδας

Στοιχεία από τη Λογική

Τα υπολογιστικά προβλήματα που προέρχονται από το χώρο της Λογικής παίζουν σημαντικό ρόλο στην θεωρία Πολυπλοκότητας. Είναι αρκετά εκφραστικά και χρησιμοποιούνται για να εκφράσουν την υπολογιστική δυνατότητα σε διάφορα επίπεδα. Πολλά από τα προβλήματα αυτά θα μας απασχολήσουν στις επόμενες ενότητες. Στη συνέχεια περιγράφουμε βασικές έννοιες από τη θεωρία της Λογικής και ορίζουμε ένα από τα πιο κεντρικά προβλήματα, το πρόβλημα της ικανοποιησιμότητας λογικών εκφράσεων.

Έστω $X=\{x_1,\ldots,x_n\}$ ένα πεπερασμένο σύνολο από μεταβλητές Boole (λογικές μεταβλητές). Κάθε μεταβλητή (variable) $x_i \in X$ μπορεί να πάρει δύο δυνατές τιμές αληθείας: την τιμή ψέμα ( $0$ ) και την τιμή αλήθεια ( $1$ ). Οι μεταβλητές συνδέονται μεταξύ τους μέσω των λογικών συνδέσμων $\neg$ (λογική άρνηση), $\vee$ (λογικό είτε), και $\wedge$ (λογικό και) για τη δημιουργία εκφράσεων Boole λογικών εκφράσεων όπως ακριβώς συνδέονται στην άλγεβρα οι πραγματικές μεταβλητές μέσω των $-$ , $+$ και $\times$ για να σχηματίσουν αριθμητικές εκφράσεις.

O συντακτικός ορισμός μιας λογικής έκφρασης δίνεται αναδρομικά ως εξής:

Ορισμός 16

Μια λογική έκφραση μπορεί να είναι:

1. είτε μια σταθερά $0$ ή $1$ ,

2. είτε μια λογική μεταβλητή $x_i \in X$ ,

3. είτε μια έκφραση της μορφής $\neg \phi$ , όπου $\phi$ είναι μια λογική έκφραση,

4. είτε μια έκφραση της μορφής ( $\phi_1 \vee \phi_2$ ), όπου $\phi_1$ και $\phi_2$ είναι λογικές εκφράσεις,

5.είτε έκφραση της μορφής ( $\phi_1 \wedge \phi_2$ ), όπου $\phi_1$ και $\phi_2$ είναι λογικές εκφράσεις.

Η έκφραση $\neg \phi$ καλείται άρνηση της $\phi$ . Σύμφωνα με τον ορισμό, σε μια λογική έκφραση $\phi$ κάθε μεταβλητή $x_i \in X$ μπορεί να έχει είτε θετική ( $x_i$ ) είτε αρνητική εμφανίση ( $\neg x_i$ (ή $\overline{x_i}$ )). Κάθε προσημασμένη μεταβλητή καλείται άτομο(literal). H έκφραση $\phi_1 \vee \phi_2$ καλείται διάζευξη (disjunction) των $\phi_1$ και $\phi_2$ ενώ η έκφραση $\phi_1 \wedge \phi_2$ καλείται σύζευξη (conjunction) αυτών. Μήκος της λογικής έκφρασης $\phi$ καλείται το πλήθος των ατόμων που εμφανίζονται σε αυτήν.

Παράδειγμα 1 Η $\phi = ((\overline{x_1} \vee x_2) \wedge x_3)$ είναι μια λογική έκφραση ορισμένη στις μεταβλητές $x_1, x_2, x_3$ .

Εκτός από την συντακτική μορφή μιας λογικής έκφρασης, αυτό που πρέπει επίσης να ορίσουμε είναι η σημαντική της (semantics), δηλαδή η σημασία της. Μια λογική έκφραση μπορεί να είναι ψευδής ή αληθής ( $0$ ή $1$ ) ανάλογα με το αν οι μεταβλητές που εμφανίζονται σε αυτήν είναι αληθείς ή ψευδείς. Ο ορισμός της σημαντικής μιας λογικής έκφρασης είναι επαγωγικός: ξεκινάμε από τις τιμές των μεταβλητών και στη συνέχεια συνθέτουμε απλές εκφράσεις με λογικούς συνδέσμους για να σχηματίσουμε πιο σύνθετες. Η τελική τιμή της λογικής έκφρασης προκύπτει σύμφωνα με τον ορισμό των λογικών συνδέσμων που δίνεται στον Πίνακα 2.

$x$	$y$	$\neg x$	$x \wedge y$	$x \vee y$	$x \oplus y$	$x \Rightarrow y$	$x \Leftrightarrow y$
$0$	$0$	$1$	$0$	$0$	$0$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$1$	$1$	$0$
$1$	$0$	$0$	$0$	$1$	$1$	$0$	$0$
$1$	$1$	$0$	$1$	$1$	$0$	$1$	$1$

Πίνακας 2 Ορισμοί λογικών συνδέσμων

Ορισμός 17

Έστω μια λογική έκφραση $\phi$ που ορίζετε στο σύνολο των μεταβλητών $X=\{x_1,\ldots,x_n\}$ . Μια αποτίμηση αλήθειας (truth assignment) $t$ της $\phi$ είναι μια απεικόνιση $t : X \rightarrow \{0,1\}$ .

Αν $t$ είναι μια αποτίμηση αλήθειας της $\phi$ , γράφουμε $t(x)=0$ ( $t(x)=1$ ) για να δηλώσουμε ότι η $t$ αποδίδει την τιμή $0$ (αντίστοιχα, $1$ ) στη μεταβλητή $x$ . Επίσης, συμβολίζουμε με $\phi(t)$ την τιμή που παίρνει η $\phi$ μέσω της $t$ .

Ορισμός 18

Έστω $\phi$ μια λογική έκφραση που ορίζεται στο σύνολο $X$ και έστω $t$ μια αποτίμηση αλήθειας της $\phi$ . Θα λέμε ότι η $t$ ικανοποιεί (satisfies) την $\phi$ ( $t \models \phi$ ) εάν ισχύουν τα παρακάτω: \begin{enumerate} 1. Αν η $\phi$ είναι μια μεταβλητή $x \in X$ , τότε $t \models \phi$ αν $t(x)=1$ .

2. Αν $\phi = \neg \phi_1$ , τότε $t \models \phi$ αν $t \not \models \phi_1$ .

3. Αν $\phi = (\phi_1 \vee \phi_2)$ , τότε $t \models \phi$ αν $t \models \phi_1$ ή $t \models \phi_2$ .

4. Αν $\phi = (\phi_1 \wedge \phi_2)$ , τότε $t \models \phi$ αν $t \models \phi_1$ και $t \models \phi_2$ .

Παράδειγμα 2

Η αποτίμηση αλήθειας $t$ για την οποία $t(x_1)=t(x_3)=1$ και $t(x_2)=0$ δεν ικανοποιεί τη λογική έκφραση $\phi = ((\overline{x_1} \vee x_2) \wedge x_3)$ . Ωστόσο, η αποτίμηση αλήθειας $t'$ με $t'(x_1)=t'(x_2)=0$ και $t'(x_3)=1$ , ικανοποιεί την $\phi$ .

Ορισμός 19

Για δύο λογικές εκφράσεις $\phi_1$ και $\phi_2$ με σύνολο μεταβλητών $X$ , θα λέμε ότι η $\phi_1$ συνεπάγεται την $\phi_2$ ( $\phi_1 \models \phi_2$ ) εάν κάθε αποτίμηση αληθείας που ικανοποιεί την $\phi_1$ ικανοποιεί και την $\phi_2$ .

Ορισμός 20

θα λέμε ότι δύο λογικές εκφράσεις $\phi_1$ και $\phi_2$ με σύνολο μεταβλητών $X$ είναι ισοδύναμες ( $\phi_1 \equiv \phi_2$ ) εάν $\phi_1 \models \phi_2$ και $\phi_2 \models \phi_1$

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

Υπάρχουν δύο ακόμα λογικοί σύνδεσμοι: o $\Rightarrow$ λογική συνεπαγωγή και o $\Leftrightarrow$ λογική ισοδυναμία. Οι ορισμοί τους φαίνονται στον Πίνακα 2. Για τους συνδέσμους αυτούς ισχύει ότι:

$(\phi_1 \Rightarrow \phi_2)$ $\equiv( \neg \phi_1 \vee \phi_2 )$ \\ $(\phi_1 \Leftrightarrow \phi_2)$ $\equiv ((\phi_1 \Rightarrow \phi_2) \wedge (\phi_2 \Rightarrow \phi_1))$

Για τους λογικούς συνδέσμους ισχύουν βασικές ιδιότητες όπως η αντιμεταθετική και η προσεταιριστική ιδιότητα, αντίστοιχες με αυτές που ισχύουν για τους αριθμητικούς τελεστές. Οι ιδιότητες αυτές αναφέρονται στον Πίνακα 3 και δίνουν την δυνατότητα της απλούστερης γραφικής αναπαράστασης μιας λογικής έκφρασης.

Παράδειγμα 3

Η λογική έκφραση $\phi = (( x_1 \vee \overline{x_3}) \vee x_2) \vee x_4 \vee (x_2 \vee x_5))$ γράφεται πιο απλά ως $\phi = x_1 \vee x_2 \vee \overline{x_3} \vee x_4 \vee x_5$ .

(1)	$(\phi_1 \vee \phi_2) \equiv (\phi_2 \vee \phi_1)$
(2)	$(\phi_1 \wedge \phi_2) \equiv (\phi_2 \wedge \phi_1)$ &	αντιμεταθετικότητα
(3)	$\neg \neg \phi_1 \equiv \phi_1$	διπλή άρνηση
(4)	$((\phi_1 \vee \phi_2) \vee \phi_3) \equiv (\phi_1 \vee (\phi_2 \vee \phi_3)$
(5)	$((\phi_1 \wedge \phi_2) \wedge \phi_3) \equiv (\phi_1 \wedge (\phi_2 \wedge \phi_3)$	προσεταιριστικότητα
(6)	$((\phi_1 \wedge \phi_2) \vee \phi_3) \equiv ((\phi_1 \vee \phi_3) \wedge (\phi_2 \vee \phi_3))$
(7)	$((\phi_1 \vee \phi_2) \wedge \phi_3) \equiv ((\phi_1 \wedge \phi_3) \vee (\phi_2 \wedge \phi_3))$	μεταβατικότητα
(8)	$\neg (\phi_1 \vee \phi_2) \equiv (\neg\phi_1 \wedge \neg\phi_1)$
(9)	$\neg (\phi_1 \wedge \phi_2) \equiv (\neg\phi_1 \vee \neg\phi_1)$	κανόνας De Morgan
(10)	$\phi_1 \vee \phi_1 \equiv \phi_1$
(11)	$\phi_1 \wedge \phi_1 \equiv \phi_1$	αυτοδυναμία
(12)	$\phi_1 \vee (\phi_1 \wedge \phi_2) \equiv \phi_1$
(13)	$\phi_1 \wedge (\phi_1 \vee \phi_2) \equiv \phi_1$	απορρόφηση

Πίνακας 3 . Ιδιότητες λογικών συνδέσμων.

Επιπλέον, οι ιδιότητες του Πίνακα 3 μας δίνουν τη δυνατότητα της ισοδύναμης γραφής μιας λογικής έκφρασης σε πιο βολικές, κανονικές μορφές. Οι κανονικές μορφές που χρησιμοποιούνται ευρέως στην προτασιακό λογισμό είναι η συζευκτική κανονίκη μορφή (conjunctive normal form, CNF) και η διαζευκτική κανονική μορφή (disjunctive normal form, DNF):

Ορισμός 21 (Συζευκτική Κανονική Μορφή)

Μια λογική έκφραση $\phi$ είναι σε συζευκτική κανονική μορφή εάν

$\phi = \bigwedge\nolimits_{i=1}^{m}$ $C_i = C_1 \wedge C_2 \wedge \cdots \wedge C_m,$ όπου $C_i, i=1,\ldots,m$ , είναι η διάζευξη ενός ή περισσοτέρων ατόμων της $\phi$ .

Ορισμός 22 (Διαζευκτική Κανονική Μορφή)

Μια λογική έκφραση $\phi$ είναι σε διαζευκτική κανονική μορφή εάν $\phi = \bigvee\nolimits_{j=1}^{l}$ $D_j = D_1 \vee D_2 \vee \cdots \vee D_l$ , όπου $D_j, j=1,\ldots,l$ , είναι η σύζευξη ενός ή περισσοτέρων ατόμων της $\phi$ .

Κάθε $C_i$ καλείται πρόταση (clause) της $\phi$ ενώ κάθε $D_j$ καλείται όρος (term) αυτής. Αν η $\phi$ είναι σε συζευκτική κανονική μορφή, τότε για κάθε πρόταση $C_i$ αυτής ισχυει ότι $\phi \models C_i$ . Αν η $\phi$ είναι σε διαζευκτική κανονική μορφή, τότε για κάθε όρο $D_j$ αυτής ισχύει ότι $D_j \models \phi$ .

Θεώρημα 7

Κάθε λογική έκφραση $ $\phi$ $ είναι ισοδύναμη με μια λογική έκφραση σε συζευκτική κανονική μορφή και με μια άλλη λογική έκφραση σε διαζευκτική κανονική μορφή.

Απόδειξη Η απόδειξη γίνεται με επαγωγή στη συντακτική δομή της $\phi$ .

$\phi = x_i$ . Η πρόταση είναι αληθής (τετριμμένη περίπτωση) .

$\phi = \neg \phi_1$ . Ας κάνουμε την επαγωγική υπόθεση ότι έχουμε

μετατρέψει την $\phi_1$ σε διαζευκτική κανονική μορφή με όρους $D_1, D_2,\ldots, D_m$ . Οπότε, $\phi = \neg \phi_1 = \neg ( D_1 \vee D_2 \vee \ldots\vee D_m )$ και με εφαρμογή του κανόνα De Morgan, $\phi = \neg D_1 \wedge \neg D_2 \wedge \ldots \wedge \neg D_m$ . Αλλά κάθε όρος $D_j$ είναι της μορφής $x_{1_j} \wedge x_{2_j} \wedge \ldots \wedge x_{k_j}$ , οπότε αν εφαρμόσουμε πάλι τον κανόνα De Morgan έχουμε ότι $\neg D_j = \neg x_{1_j} \vee \neg x_{2_j} \vee \ldots \vee \neg x_{k_j}$ . Αν τότε εφαρμόσουμε την μεταβατική ιδιότητα στις προτάσεις της $\phi$ , είναι φανερό ότι η $\phi$ γράφεται σε διαζευκτική κανονική μορφή.

Με τον ίδιο τρόπο μπορούμε να αποδείξουμε ότι η $\phi$ γράφεται σε συζευκτική κανονική μορφή, αν κάνουμε την υπόθεση ότι η $\phi_1$ είναι σε συζευκτική κανονική μορφή.

$\phi = \phi_1 \vee \phi_2$ . Αν υποθέσουμε ότι οι $\phi_1$ και $\phi_2$

είναι σε διαζευκτική κανονική μορφή, τότε και η $\phi$ είναι σε διαζευκτική κανονική μορφή.

Ας υποθέσουμε τώρα ότι οι $\phi_1$ και $\phi_2$ είναι σε συζευκτική κανονική μορφή, δηλαδή έστω ότι $\phi_1 = C_1 \wedge C_2 \wedge \ldots \wedge C_k$ και $\phi_2 = C'_1 \wedge C'_2 \wedge \ldots \wedge C'_{k'}$ . Αν εφαρμόσουμε στην $\phi$ την μεταβατική ιδιότητα, είναι εύκολο να δούμε ότι η $\phi$ ισούται με την σύζευξη $k \cdot k'$ προτάσεων, δηλαδή γράφεται σε ισοδύναμη συζευκτική κανονική μορφή.

$\phi = \phi_1 \wedge \phi_2$ . Προκύπτει με τρόπο συμμετρικό ως προς την

προηγούμενη περίπτωση.

Εάν κάθε πρόταση μιας λογικής έκφρασης $\phi$ περιέχει $k$ άτομα, τότε η $\phi$ είναι σε $k$ -CNF. Ομοίως, εάν κάθε όρος μιας λογικής έκφρασης $\phi$ περιέχει $k$ άτομα, τότε η $\phi$ είναι σε $k$ -DNF. Ιδιαίτερο ενδιαφέρον παρουσιάζουν λογικές εκφράσεις σε $2$ -CNF. Μια πρόταση είναι Horn εάν σε αυτήν εμφανίζεται ένα το πολύ θετικό άτομο. Σύμφωνα με τον ορισμό, μια πρόταση Horn είτε περιέχει μόνο αρνητικά άτομα (είναι πλήρως αρνητική) είτε περιέχει ακριβώς ένα θετικό άτομο (είναι συνεπαγωγή, αφού η $ $\overline{x_1} \vee \overline{x_2} \vee \ldots \vee \overline{x_k} \vee y$ $ γράφεται ισοδύναμα ως $x_1 \wedge x_2 \wedge \ldots \wedge x_k \Rightarrow y$ ). Μια έκφραση Horn είναι μια έκφραση σε CNF όπου όλες οι προτάσεις της είναι τύπου Horn. Η συμμετρική περίπτωση της πρότασης Horn είναι η antiHorn πρόταση όπου περιέχει ένα το πολύ αρνητικό άτομο. Αντίστοιχος είναι ο ορισμός της antiHorn έκφρασης.

Μια άλλη μορφή αναπαράστασης μιας λογικής έκφρασης είναι μέσω πολυωνύμων στο υποχώρο $\mathbf Z_2$ . Ένα σύστημα εξισώσεων της μορφής $Ax = b \bmod 2,$ όπου $A$ είναι ένας δυαδικός πίνακας, $b$ είναι ένα δυαδικό διάνυσμα και $x$ είναι ένα διάνυσμα μεταβλητών καλείται αφινική λογική έκφραση ή λογική έκφραση αποκλειστικού είτε. To αποκλειστικό είτε ( $\oplus$ ) δύο λογικών μεταβλητών $x$ και $y$ ορίζεται ως $x \oplus y \equiv (x \wedge \overline{y}) \vee (\overline{x} \wedge y)$ (δες Πίνακα 2. Μπορούμε να θεωρήσουμε ένα τέτοιο σύστημα σαν την σύζευξη <<προτάσεων>>, όπου προτάσεις είναι οι εξισώσεις του συστήματος. Η έκφραση $\phi_1 \oplus \phi_2$ καλείται αποκλειστική διάζευξη των $\phi_1$ και $\phi_2$ . Μια αποτίμηση αλήθειας που ικανοποιεί μια αφινική λογική έκφραση είναι ένα δυαδικό διάνυσμα που ικανοποιεί κάθε πολυώνυμο του συστήματος.

Περνάμε τώρα σε μια άλλη σημαντική έννοια, αυτή της ικανοποιησιμότητας μιας λογικής έκφρασης.

Ορισμός 23

Μια λογική έκφραση $\phi$ καλείται ικανοποιήσιμη (satisfiable) αν υπάρχει αποτίμηση αλήθειας που να την ικανοποιεί. Διαφορετικά, η $\phi$ καλείται μη ικανοποιήσιμη (unsatisfiable).

Εάν η $\phi$ ικανοποιείται από όλες τις δυνατές αποτιμήσεις αληθείας, τότε η $\phi$ καλείται ταυτολογία (tautology) ή έγκυρη (valid).

Πρόταση 8

Μια λογική έκφραση είναι μη ικανοποιήσιμη αν και μόνο αν η άρνηση της είναι ταυτολογία.

Απόδειξη Έστω ότι η λογική έκφραση $\phi$ είναι μη ικανοποιήσιμη, δηλαδή $\phi(t)=0$ για κάθε αποτίμηση αλήθειας $t$ . Τότε, $\neg \phi(t)=1$ για κάθε $t$ . ʼΑρα η $\neg \phi$ είναι ταυτολογία.

Αν, αντίστροφα, $\neg \phi(t)=1$ για κάθε αποτίμηση αλήθειας $t$ , τότε $\neg \neg \phi(t)=0$ για κάθε $t$ , δηλαδή, $\phi(t)=0$ για κάθε $t$ . ʼΑρα η $\phi$ είναι μη ικανοποιήσιμη.

Παράδειγμα 4

Η λογική έκφραση $\phi_1 = (x_1 \vee \overline{x_2}) \wedge \overline{x_1}$ είναι ικανοποιήσιμη αφού ικανοποιείται από την αποτίμηση αληθείας $t$ για την οποία $t(x_1)= t(x_2) = 0$ .

Η λογική έκφραση $\phi_2 = (x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee \overline{x_2})$ $\wedge (x_2 \vee \overline{x_3}) \wedge (\overline{x_1} \vee x_3) \wedge (\overline{x_1}$ $\vee \overline{x_2} \vee\overline{x_3})$ είναι μη ικανοποιήσιμη. Συνεπώς, η $\neg\phi_2$ είναι ταυτολογία.

Το πρόβλημα της ικανοποιησιμότητας μιας λογικής εκφράσης ορίζεται ως εξής:

ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑ (SATISFIABILITY , SAT)

Στιγμιότυπο Λογική έκφραση $\phi$ σε CNF, ορισμένη σε $n$ μεταβλητές με $m$ προτάσεις.

Ερώτημα Είναι η $\phi$ ικανοποιήσιμη;

Σε μορφή γλώσσας, το πρόβλημα της ικανοποιησιμότητας ορίζεται ως $L_{SAT} = \{ \langle \phi \rangle |$ η λογική έκφραση $\phi$ είναι ικανοποιήσιμη.

Στον τυπικό ορισμό του προβλήματος της ικανοποιησιμότητας, η λογική έκφραση $\phi$ δίνεται σε CNF. Είναι φανερό ότι αυτή η απαίτηση δεν είναι περιοριστική αφού κάθε λογική έκφραση μπορεί να γραφεί σε μια ισοδύναμη CNF. Επίσης, αυτή η ειδική μορφή εκφράζει πλήρως την πολυπλοκότητα του προβλήματος.

Ενδιαφέρουσες περιπτώσεις του προβλήματος της ικανοποιησιμότητας είναι οι περιπτώσεις όπου η λογική έκφραση είναι σε $k$ -CNF ( $k$ -SAT), είναι $2$ -CNF ( $2$ -SAT), είναι $3$ -CNF ( $3$ -SAT), είναι Horn (HORN-SAT) ή αντι-Horn (ANTIHORN-SAT) και αφινική (AFFINE-SAT).

Το πρόβλημα της ικανοποιησιμότητας μιας λογικής έκφρασης $\phi$ με $n$ μεταβλητές μπορεί να λυθεί από έναν εξαντλητικό αλγόριθμο μετά από εκθετικό αριθμό βημάτων $O(n^2 2^n)$ . Ο αλγόριθμος αυτός εξετάζει εάν κάθε δυνατή αποτίμηση αλήθειας $t$ ικανοποιεί την $\phi$ . Ωστόσο, το SAT μπορεί να λυθεί πολυωνυμικά από έναν μη ντετερμινιστικό αλγόριθμο ο οποίος μαντεύει μια αποτίμηση αληθείας $t$ και σε πολυωνυμικό χρόνο επαληθεύει εάν η $t$ ικανοποιεί κάθε πρόταση της $\phi$ . Όπως θα δούμε σε επόμενα μαθήματα, το SAT ανήκει στην κλάση NP, την κλάση των προβλημάτων απόφανσης που μπορούν να αποφασιστούν από έναν μη ντετερμινιστικό αλγόριθμο σε πολυωνυμικό χρόνο. Υπάρχουν ωστόσο ειδικές περιπτώσεις του SAT, όπως π.χ., το $2$ -SAT και το HORNSAT που λύνονται ντετερμινιστικά σε πολυωνυμικό χρόνο, ανήκουν δηλαδή στην κλάση P.

Αρχή της σελίδας

Προβλήματα στη κλάση ΝΡ

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

Ορισμός 24

Έστω η δυαδική σχέση $R \subseteq \Sigma^\ast \times \Sigma^\ast$ . Η σχέση $R$ καλείται πολυωνυμικά αποφασίσιμη αν υπάρχει ντετερμινιστική μηχανή Turing η οποία αποφασίζει τη γλώσσα $\{ (x;y) : (x,y) \in R\}$ σε πολυωνυμικό χρόνο. Επίσης, η σχέση $R$ καλείται πολυωνυμικά ισορροπημένη αν $(x,y) \in R$ συνεπάγεται ότι $|y| \leq |x|^k$ για κάποιο $k \geq 1$ (δηλαδή το μήκος του $y$ είναι πολυωνυμικά μεγαλύτερο από το μήκος του $x$ ).

Θα διατυπώσουμε τώρα και θα αποδείξουμε μια πρόταση που χαρακτηρίζει την κλάση NP.

Πρόταση 9

Έστω μια γλώσσα $L \subseteq \Sigma^\ast$ . Η $L$ ανήκει στην κλάση NP αν και μόνο αν υπάρχει μια πολυωνυμικά αποφασίσιμη και πολυωνυμικά ισορροπημένη σχέση $R$ τέτοια ώστε $L = \{ x : (x,y) \in R$ για κάποιο $y \}$ .

Απόδειξη Έστω ότι $L \in NP$ . Τότε υπάρχει μη ντετερμινιστική μηχανή Turing, έστω $N$ , που αποφασίζει τη γλώσσα $L$ σε χρόνο $|x|^k$ , για κάποιο $k \geq 1$ . Ορίζουμε την εξής σχέση $R$ : $(x,y) \in R$ αν και μόνο αν το $y$ είναι η κωδικοποίηση ενός <<ΝΑΙ>> υπολογισμού της $N$ με είσοδο $x$ . H $R$ είναι πολυωνυμικά ισορροπημένη αφού $|y| \leq |x|^k$ . Επίσης, η $R$ είναι και πολυωνυμικά αποφασίσιμη αφού σε χρόνο γραμμικό στο $x;y$ μπορούμε να ελέγξουμε (επαληθεύσουμε) αν το $y$ αντιστοιχεί στην κωδικοποίηση ενός "ΝΑΙ" υπολογισμού της $N$ με είσοδο $x$ . Συνεπώς, αφού η $N$ αποφασίζει την $L$ , θα είναι $L = \{ x : (x,y) \in R$ για κάποιο $y \}$ .

Αντίστροφα τώρα, έστω ότι υπάρχει μια πολυωνυμικά αποφασίσιμη και πολυωνυμικά ισορροπημένη σχέση $R$ τέτοια ώστε $L = \{ x : (x,y) \in R$ για κάποιο $y \}$ . Αφού η $R$ είναι πολυωνυμικά αποφασίσιμη θα υπάρχει ντετερμινιστική μηχανή Turing, έστω $M_R$ , που αποφασίζει τη γλώσσα $\{ (x;y) ~|~ (x,y) \in R\}$ σε πολυωνυμικό χρόνο. Επίσης, αφού η $R$ είναι πολυωνυμικά ισορροπημένη θα ισχύει ότι $(x,y) \in R \implies |y| \leq |x|^k$ για κάποιο $k \geq 1$ . Κατασκευάζουμε μη ντετεμινιστική μηχανή Turing $N$ η οποία με είσοδο $x$ , αρχικά μαντεύει μια συμβολοσειρά $y$ μήκους $|x|^k$ και στη συνέχεια καλεί την $M_R$ για να αποφασίζει αν $(x,y) \in R$ . Αν $(x,y) \in R$ (δηλαδή $x \in L$ ), τότε η $N$ αποδέχεται την είσοδο $x$ , διαφορετικά την απορρίπτει. Είναι φανερό ότι η $N$ αποφασίζει την $L$ , άρα $L \in NP$ .

Η μηχανή $N$ που κατασκευάσαμε ένας επαληθευτής πολυωνυμικού χρόνου για τη γλώσσα $L$ . Για κάθε $x \in L$ , αρκεί να μαντέψουμε ένα $y$ με μήκος πολυωνυμικά μεγαλύτερο από το μήκος του $x$ , και στη συνέχεια χρησιμοποιώντας αυτό το $y$ μπορούμε σε πολυωνυμικό χρόνο, ντετερμινιστικά πλέον, να επαληθεύσουμε ότι πράγματι $x \in L$ . Έτσι, κάθε πρόβλημα στην κλάση NP έχει την εξής ιδιότητα: για κάθε "ΝΑΙ" στιγμιότυπο $x$ υπάρχει τουλάχιστον ένα σύντομο πιστοποιητικό $y$ το οποίο πιστοποιεί ότι το $x$ είναι πράγματι ένα "ΝΑΙ" στιγμιότυπο του προβλήματος. Η τεχνική "μαντέυω και επαληθεύω" είναι αυτή που θα χρησιμοποιούμε απ' εδώ και στο εξής για να αποδεικνύουμε ότι ένα πρόβλημα ανήκει στην κλάση NP.

Στην συνέχεια δίνουμε τη μεθοδολογία που θα πρέπει να ακολουθούμε για να αποδεικνύουμε ότι ένα πρόβλημα ανήκει στην κλάση NP. Η μεθοδολογία αυτή βασίζεται στην ύπαρξη επαληθευτή πολυωνυμικού χρόνου για κάθε πρόβλημα που ανήκει στην κλάση NP. Δηλαδή, για κάθε "ΝΑΙ" στιγμιότυπο $x$ του προβλήματος, υπάρχει τουλάχιστον ένα σύντομο πιστοποιητικό $y$ το οποίο πιστοποιεί ότι το $x$ είναι πράγματι ένα "ΝΑΙ" στιγμιότυπο. Έτσι, για να αποδείξουμε ότι ένα πρόβλημα ανήκει στην κλάση NP θα εφαρμόζουμε την μέθοδο "μαντεύω και επαληθεύω", ως εξής:

1. Μαντεύουμε ένα σύντομο πιστοποιητικό $y$ . Προσοχή, το $y$ πρέπει να είναι πολυωνυμικά μεγαλύτερο από το $x$ .

2. Επαληθεύουμε, χρησιμοποιώντας το $y$ , ότι το $x$ είναι ένα "ΝΑΙ" στιγμιότυπο του προβλήματος. Προσοχή, η επαλήθευση πρέπει να γίνεται σε χρόνο πολυωνυμικό στο μέγεθος του $x$ .

Για παράδειγμα, το πρόβλημα της ικανοποιησιμότητας Λογικών εκφράσεων (ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑ, SAT) ανήκει στην κλάση NP. Η απόδειξη είναι ως εξής: Έστω $x$ ένα τυχαίο στιγμιότυπο της ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ (Λογική έκφραση $\phi$ σε συζευκτική κανονική μορφή, ορισμένη σε $n$ μεταβλητές, με $m$ προτάσεις). Το μήκος του $x$ χαρακτηρίζει το πλήθος $n$ των μεταβλητών στις οποίες ορίζεται η λογική έκφραση $\phi$ (είναι ένα πολυώνυμο του $n$ ). Μαντεύουμε μια αποτίμηση αληθείας $t$ στις $n$ μεταβλητές της $\phi$ (η $t$ είναι το πιστοποιητικό $y$ και έχει μήκος $n$ ) και επαληθεύουμε σε γραμμικό χρόνο στο μήκος της $\phi$ (άρα σε χρόνο πολυωνυμικό στο $n$ ) ότι η $t$ ικανοποιεί την $\phi$ (δηλαδή ότι το $x$ είναι ένα "ΝΑΙ" στιγμιότυπο του προβλήματος της (ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ).

Να σημειώσουμε εδώ ότι όσο κι αν φαίνεται απλό, δεν είναι πάντα εύκολο να δείξει κανείς ότι ένα πρόβλημα ανήκει στην κλάση NP. Παράδειγμα ενός τέτοιου προβλήματος, το οποίο δεν γνωρίζουμε αν ανήκει στην κλάση NP, είναι το $k$ -ΟΣΤΟ ΜΕΓΑΛΥΤΕΡΟ ΥΠΟΣΥΝΟΛΟ ( $k$ -th LARGEST SUBSET)[GJ79]

Αρχή της σελίδας

Πληρότητα κατά ΝΡ

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

Σύμφωνα με τον Ορισμό 4.2,\footnote{Παραπέμπουμε σε ορισμούς, λήμματα, κ.α. από το σύγγραμμα διδασκαλίας.} ένα πρόβλημα $\Pi$ είναι πλήρες για την κλάση NP αν (i) ανήκει στην κλάση NP και (ii) κάθε πρόβλημα $\Pi$ ' της κλασης NP ανάγεται αποδοτικά σε αυτό, δηλαδή $\Pi$ ' $\leq_{LS} \Pi$ . Θυμίζουμε τον ορισμό (Ορισμός 4.1) της αποδοτικής αναγωγής μεταξύ δύο προβλημάτων (γλωσσών): Η γλώσσα $L'$ ανάγεται αποδοτικά στη γλώσσα $L$ αν υπάρχει συνάρτηση $R : \Sigma^\ast \to \Sigma^\ast$ η οποία υπολογίζεται από μια μηχανή Turing με είσοδο και έξοδο σε λογαριθμικό χώρο, τέτοια ώστε $x\in L'$ αν και μόνο αν $R(x) \in L$ . Με άλλα λόγια, το $x$ είναι ένα "ΝΑΙ" στιγμιότυπο του προβλήματος $\Pi$ ' αν και μόνο αν το $R(x)$ είναι ένα "ΝΑΙ" στιγμιότυπο του προβλήματος $\Pi$ .

Για να αποδεικνύουμε ότι ένα πρόβλημα $\Pi$ είναι NP-πλήρες θα εφαρμόζουμε το Λήμμα 4.3: κατ' αρχήν θα δείχνουμε ότι το πρόβλημα ανήκει στην κλάση NP και στη συνέχεια θα ανάγουμε ένα γνωστό NP-πλήρες πρόβλημα, έστω το $\Pi$ ', στο $\Pi$ . Πιο αναλυτικά, τα βήματα που θα ακολουθούμε είναι τα εξής:

1. Δείχνουμε ότι το $\Pi$ ανήκει στην κλάση NP, μέσω της μεθόδου μάντεψε και επαλήθευσε.

2. Επιλέγουμε ένα γνωστό NP-πλήρες πρόβλημα, έστω το $\Pi$ '.

3. Κατασκευάζουμε αναγωγή $R$ που μετασχηματίζει κάθε τυχαίο στιγμιότυπο $x$ του προβλήματος $\Pi$ ' σε νόμιμο στιγμιότυπο $R(x)$ του προβλήματος $\Pi$ .

4. Δείχνουμε ότι η αναγωγή είναι ορθή, δηλαδή ότι το $x$ είναι ένα "ΝΑΙ" στιγμιότυπο του προβλήματος $\Pi$ ' αν και μόνο αν το $R(x)$ είναι ένα "ΝΑΙ" στιγμιότυπο του προβλήματος $\Pi$ .

5. Δείχνουμε ότι η αναγωγή είναι αποδοτική, δηλαδή είναι αναγωγή λογαριθμικού χώρου.

Έχουμε περιγράψει τη μέθοδο "μάντεψε και επαλήθευσε", που θα χρησιμοποιούμε στο 1ο βήμα, σε προηγούμενη ενότητα. Τις περισσότες φορές είναι εύκολο να δείξουμε ότι ένα πρόβλημα στην κλάση NP (προσοχή, υπάρχουν πολλές περιπτώσεις που αυτό δεν ισχύει).

Το 2ο βήμα απαιτεί την επιλογή ενός κατάλληλου NP-πλήρους προβλήματος. Η επιλογή αυτή απαιτεί εμπειρία και εξοικείωση με τις αναγωγές. Αν το προς απόδειξη NP-πλήρες πρόβλημα δεν κατευθύνει στην επιλογή του κατάλληλου προβλήματος, η καλύτερη επιλογή είναι να χρησιμοποιηθεί το πρόβλημα της 3ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ (3SAT).

Όσο αφορά στον τρόπο κατασκευής της αναγωγής (3ο βήμα), και εδώ απαιτείται εμπειρία, εξοικίωση αλλά και διαίσθηση. Θα μπορούσαμε να κατηγοριοποιήσουμε τους πιθανούς τρόπους κατασκευής σε τρεις βασικές κατηγορίες: (i) την ειδική περίπτωση, (ii) την τοπική αντικατάσταση, και (iii) την κατασκευή σκαριφημάτων. Τις τεχνικές αυτές έχουμε ήδη χρησιμοποιήσει και θα χρησιμοποιήσουμε στην κατασκευή αρκετών αναγωγών. Μπορείτε να βρείτε περισσότερα στοιχεία για αυτές στην Ενότητα 5.5.

Στο 4ο βήμα πρέπει να προσέξουμε στην απόδειξη της αρθότητας της αναγωγής: πρέπει να αποδειχθεί και το ευθύ αλλά και το αντίστροφο. Τέλος, στο 5ο βήμα αρκεί να αποδείξουμε ότι το μέγεθος του στιγμιότυπου $R(x)$ που κατασκευάσαμε είναι πολυωνυμικά μεγαλύτερο από το μέγεθος του $x$ .

Αρχή της σελίδας

ΝΡ-πλήρη προβλήματα

Συνεχίζουμε τη μελέτη προβλημάτων που είναι πλήρη για την κλάση NP παρουσιάζοντας δυο ακόμα παραλλαγές του προβλήματος της ικανοποιησιμότητας.

Οριζουμε το πρόβλημα της ΜΕΓΙΣΤΗΣ 2-ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ (MAX2SAT) ως εξής: Δίνεται Λογική έκφραση $\phi$ σε 2ΣΚΜ, ορισμένη σε $n$ μεταβλητές, με $m$ προτάσεις, και θετικός ακέραιος $k \leq m$ . Υπάρχει αποτίμηση αλήθειας η οποία να ικανοποιεί τουλάχιστον $k$ προτάσεις της $\phi$ ;

Είναι φανερό ότι το MAX2SAT αποτελεί γενίκευση του προβλήματος 2SAT αφού το 2SAT προκύπτει από το MAX2SAT αν θέσουμε $k = m$ . Το γεγονός αυτό ωστόσο δεν προσδιορίζει τη δυσκολία επίλυσης του γενικού προβλήματος αφού το ειδικό πρόβλημα επιλύεται αποδοτικά (είναι P-πλήρες), σε αντίθεση με τα ήδη γνωστά προβλήματα MAXSAT και SAT. Θα δείξουμε ότι το MAX2SAT είναι NP-πλήρες.

Το max2sat προφανώς ανήκει στην κλάση NP αφού για οποιαδήποτε Λογική έκφραση $\phi$ μπορούμε να μαντέψουμε μια αποτίμηση αλήθειας $t$ για τις $n$ μεταβλητές της $\phi$ και σε πολυωνυμικό χρόνο να επαληθεύσουμε ότι η $t$ ικανοποιεί την $\phi$ .

Στη συνέχεια θα ανάγουμε το ήδη γνωστό NP-πλήρες πρόβλημα 3SAT στο MAX2SAT. Έστω $\phi$ ένα τυχαίο στιγμιότυπο του 3SAT: Λογική έκφραση $\phi$ σε 3ΣΚΜ, ορισμένη στις $n$ μεταβλητές $x_1, \ldots, x_n$ , με $m$ προτάσεις. Κάθε πρόταση της $\phi$ είναι στη μορφή $C_i = (l_{i_1} \vee l_{i_2} \vee l_{i_3})$ , όπου $l_i = x_i$ ή $\overline{x_i}, i=1, \ldots,n$ . Θα κατασκευάσουμε στιγμιότυπο του MAX2SAT, δηλαδή Λογική έκφραση $\phi$ ' σε 2ΣΚΜ, ορισμένη σε $n$ ' μεταβλητές, με $m$ ' προτάσεις, και θετικό ακέραιο $k \leq m$ ', έτσι ώστε: η $\phi$ είναι ικανοποιήσιμη αν και μόνο αν υπάρχει αποτίμηση αλήθειας που ικανοποιεί τουλάχιστον $k$ προτάσεις της $\phi$ '.

Ας θεωρήσουμε κατ' αρχήν τις εξής δέκα προτάσεις:

$(x) (y) (z) (w)$

$(\overline{x} \vee \overline{y})$ $(\overline{y} \vee \overline{z})$ $(\overline{z} \vee \overline{x})$

$(x \vee \overline{w})$ $(y \vee \overline{w})$ $(z \vee \overline{w})$

Παρατηρούμε ότι οι προτάσεις αυτές είναι συμμετρικές ως προς τις μεταβλητές $x, y, z$ αλλά όχι ως προς την $w$ . Επίσης παρατηρούμε ότι δεν είναι δυνατόν να ικανοποιηθούν ταυτόχρονα και οι δέκα προτάσεις. Ας δούμε πόσες το πολύ προτάσεις είναι δυνατό να ικανοποιηθούν:

Έστω ότι και οι τρεις μεταβλητές $x, y, z$ είναι αληθείς. Τότε οι

προτάσεις τις 2ης σειράς είναι όλες ψευδείς και το μόνο που μπορούμε να κάνουμε είναι να θέσουμε αληθή και την μεταβλητή $w$ ώστε όλες οι προτάσεις της 1ης γραμμής να είναι αληθείς. Συνεπώς το πολύ επτά προτάσεις μπορούν να ικανοποιηθούν.

Έστω ότι δύο από τις μεταβλητές $x, y, z$ είναι αληθείς και η τρίτη

είναι ψευδής. Τότε δυό προτάσεις από κάθε σειρά είναι αληθείς ενώ μπορούμε κάνουμε αληθή μια ακόμα πρόταση από την 1η ή την 3η σειρά θέτοντας αληθή (ή ψευδή, αντίσοτιχα, τη μεταβλητή $w$ . ʼAρα και σε αυτή την περίπτωση το πολύ επτά προτάσεις μπορούν να ικανοποιηθούν.

Έστω ότι μία μόνο απο τις $x, y, z$ είναι αληθής ενώ οπι υπόλοιπες δύο

είναι ψευδής. Οι προτάσεις τις 2ης σειράς είναι αληθείς ενώ αν θέσουμε ψευδή τη μεταβλητή $w$ μπορούμε να ικανοποιήσουμε και τις τρεις προτάσεις της 3ης σειράς. ʼAρα και σε αυτή την περίπτωση επτά το πολύ προτάσεις μπορούν να ικανοποιηθούν.

Τέλος, έστω ότι και οι τρεις μεταβλητές $x, y, z$ είναι ψευδείς. Τότε οι

τρεις προτάσεις τις 2ης σειράς είναι αληθείς ενώ θέτοντας ψευδή και τη μεταβλητή $w$ μπορούμε να ικανοποιήσουμε και τις τρεις προτάσεις της 3ης σειράς. Συνεπώς, σε αυτή την περίπτωση μπορούν το πολύ έξι προτάσεις να ικανοποιηθούν.

Συνοψίζοντας, οι παραπάνω δέκα προτάσεις έχουν την εξής ιδιότητα: οποιαδήποτε αποτίμηση αλήθειας (από τις $2^3-1$ ) που ικανοποιεί την πρόταση $(x \vee y \vee z)$ μπορεί να επεκταθεί έτσι ώστε να ικανοποιεί το πολύ επτά από τις δέκα προτάσεις ενώ η όγδοη αποτίμηση αληθείας (που δεν ικανοποιεί την $(x \vee y \vee z$ )) αν επεκταθεί μπορεί να ικανοποιήσει το πολύ έξι απο τις δέκα προτάσεις.

Η ιδιότητα αυτή προτείνει μια άμεση αναγωγή από το 3SAT στο MAX2SAT: Για κάθε πρόταση $C_i = (l_{i1} \vee l_{i2} \vee l_{i3})$ της $\phi$ προσθέτουμε στη $\phi$ ' μια ομάδα από δέκα προτάσεις όπως προηγουμένως, όπου τη θέση των $x, y, z$ παίρνουν τα $l_{i_1}, l_{i_2}, l_{i_3}$ και τη θέση της $w$ παίρνει η νέα βοηθητική μεταβλητή $w_i$ . Έτσι, η $\phi$ ' αποτελείτε συνολικά από $m'$ $= 10 m$ προτάσεις οι οποίες ορίζονται σε $n' = n + m$ μεταβλητές. Επίσης θέτουμε $k = 7m$ . Ισχυριζόμαστε ότι η $\phi$ είναι ικανοποιήσιμη αν και μόνο αν υπάρχει αποτίμηση αλήθειας που ικανοποιεί το πολύ $7m$ προτάσεις τις $\phi'$ .

Έστω ότι η $\phi$ είναι ικανοποιήσιμη. Σϋμφωνα με την προηγούμενη συζήτηση, κάθε αποτίμηση αλήθειας που ικανοποιεί τη $\phi$ μπορεί να επεκταθεί κατάλληλα στις μεταβλητές $w_i, i=1, \ldots, w_m$ , ανάλογα με τις τιμές των μεταβλητών που συμμετέχουν στην πρόταση $C_i$ , έτσι ώστε να ικανοποιεί ακριβώς επτά προτάσεις σε κάθε ομάδα της $\phi'$ , δηλαδή συνολικά $7m$ προτάσεις της $\phi'$ . Αντίστροφα, έστω ότι υπάρχει αποτίμηση αλήθειας που ικανοποιεί $7m$ προτάσεις της $\phi'$ . Αφού σε κάθε ομάδα προτάσεων της $\phi'$ μπορούν να ικανοποιηθούν το πολύ επτά προτάσεις και υπάρχουν $m$ $ομάδες, ικανοποιούνται ακριβώς επτά προτάσεις σε κάθε ομάδα προτάσεων της $\phi'$ . Μια τέτοια αποτίμηση αλήθειας ικανοποιεί όλες τις προτάσεις της $\phi$ , συνεπώς η $\phi$ είναι ικανοποιήσιμη.

Για να ολοκληρώσουμε την απόδειξη της πληρότητας πρέπει να αναφέρουμε ότι η αναγωγή που κατασκευάσαμε είναι λογαριθμικού χώρου, αφού η $\phi'$ είναι πολυωνυνικά μεγαλύτερη από τη $\phi$ .

Στη συνέχεια ορίζουμε μια ακόμα παραλλαγή του προβλήματος της ικανοποιησιμότητας, την HORN 2-ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑ (HORN2SAT): Δίνεται Λογική έκφραση $\phi$ σε ΣΚΜ, ορισμένη σε $n$ μεταβλητές, με $m$ προτάσεις, όπου κάθε πρόταση της είτε είναι τύπου Horn (περιέχει το πολύ ένα θετικό άτομο) είτε είναι σε 2ΣΚΜ (περιέχει ακριβώς δύο άτομα). Είναι η $\phi$ ικανοποιήσιμη;

Κάθε στιγμιότυπο του HORN2SAT είναι ένα μίγμα από Horn ή/και 2ΣΚΜ προτάσεις. Θα μπορούσαμε να πούμε ότι το πρόβλημα αυτό αποτελεί γενίκευση των προβλημάτων HORNSAT και 2SAT τα οποία γνωρίζουμε ότι επιλύονται αποδοτικά (είναι P-πλήρη). Ωστόσο, η μίξη αυτών "χαλάει" την καλή συμπεριφορά των δύο προβλημάτων. Θα δείξουμε ότι το HORN2SAT είναι NP-πλήρες.

Το HORN2SAT προφανώς ανήκει στην κλάση NP αφού για οποιαδήποτε Λογική έκφραση $\phi$ μπορούμε να μαντέψουμε μια αποτίμηση αλήθειας $t$ για τις $n$ μεταβλητές της $\phi$ και σε πολυωνυμικό χρόνο να επαληθεύσουμε ότι η $t$ ικανοποιεί την $\phi$ .

Για να αποδείξουμε ότι το HORN2SAT είναι NP-πλήρες, θα ανάγουμε το 3SAT σε αυτό. Έστω $\phi$ ένα τυχαίο στιγμιότυπο του 3SAT: Λογική έκφραση $\phi$ σε 3ΣΚΜ, ορισμένη στις $n$ μεταβλητές $x_1, \ldots, x_n$ , με $m$ προτάσεις. Κάθε πρόταση της $\phi$ είναι στη μορφή $C_i =(l_{i_1} \vee l_{i_2} \vee l_{i_3})$ , όπου $ $l_i = x_i$ ή $\overline{x_i}, i=1, \ldots, n$ . Θα κατασκευάσουμε στιγμιότυπο του HORN2SAT, δηλαδή Λογική έκφραση $\phi'$ ορισμένη σε $n'$ μεταβλητές, με $m'$ προτάσεις, κάθε πρόταση της οποίας είναι είτε τύπου Horn είτε σε 2ΣΚΜ, έτσι ώστε: η $\phi$ είναι ικανοποιήσιμη αν και μόνο αν η $\phi'$ είναι ικανοποιήσιμη.

Η κατασκευή του στιγμιοτύπου του HORN2SAT βασίζεται στην τοπική αντικατάσταση των προτάσεων της $\phi$ που δεν είναι Horn ή σε 2ΣΚΜ με ένα σύνολο από προτάσεις στη $\phi'$ έτσι ώστε να διατηρείται τοπικά η λογική ισοδυναμία. Για κάθε πρόταση της $\phi$ θα προσθέσουμε στη $\phi'$ ένα ισοδύναμο σύνολο από προτάσεις οι οποίες θα είναι είτε Horn είτε σε 2ΣΚΜ.

Έστω $C_i,$ $i=1,\ldots,m,$ μια τυχαία πρόταση σε 3ΣΚΜ της $\phi$ . Αναφορικά με το πρόσημο των τριών μεταβλητών που εμφανίζονται σε αυτήν, η $C_i$ ανήκει σε έναν από τους παρακάτω τέσσερις διαφορετικούς τύπους:

Η $C_i$ δεν περιέχει καμία μεταβλητή με θετικό πρόσημο. Έστω, για

παράδειγμα, $C_i = (\overline{x}_{i_1} \vee \overline{x}_{i_2} \vee \overline{x}_{i_3})$ . Η $C_i$ είναι μια Horn πρόταση και μπορεί να χρησιμοποιηθεί ως ισοδύναμη πρόταση στη $\phi'$ . Προσθέτουμε λοιπόν την πρόταση $C_i$ στη $\phi'$ .

Η $C_i$ περιέχει μία μεταβλητή με θετικό πρόσημο. Έστω, $C_i = (x_{i_1} \vee \overline{x}_{i_2} \vee \overline{x}_{i_3})$ .

Όπως και στην προηγούμενη περίπτωση, η $C_i$ είναι μια Horn πρόταση την οποία προσθέτουμε στη $\phi'$ .

Η $C_i$ περιέχει δύο μεταβλητές με θετικό πρόσημο. Έστω, $C_i = (x_{i_1} \vee x_{i_2} \vee \overline{x}_{i_3})$ .

Η $C_i$ δεν είναι ούτε Horn ούτε σε 2ΣΚΜ και δεν μπορεί να προστεθεί στη $\phi'$ . Σε αυτή την περίπτωση προσθέτουμε στη $\phi'$ το σύνολο των προτάσεων $ $\{ (\overline{y}_{i_1} \vee x_{i_2} \vee \overline{x}_{i_3}),$ $( x_{i_1} \vee y_{i_1}) \}$ $. Οι προτάσεις αυτές είναι Horn ή σε 2ΣΚΜ και ορίζονται στις μεταβλητές που συμμετέχουν στη $C_i$ αλλά και σε μια ακόμα βοηθητική μεταβλητή, την $y_{i_1}$ , η οποία εξαρτάται από τη $C_i$ .\footnote{Εναλλακτικά, και για λόγους συμμετρίας, θα μπορούσαμε να ορίσουμε το σύνολο των προτάσεων $ $\{ (x_{i_1} \vee y_{i_1}), (\vee x_{i_2} \vee y_{i_2}),$ $( \overline{x}_{i_3} \vee y_{i_3}),$ $(\overline{y}_{i_1} \vee \overline{y}_{i_2} \vee \overline{y}_{i_3}) \}$ $ και να χρησιμοποιήσουμε τρεις βοηθητικές μεταβλητές.} Μπορούμε εύκολα να δούμε ότι αν υπάρχει αποτίμηση αλήθειας στις μεταβλητές της $C_i$ που ικανοποιεί τη $C_i$ , τότε η αποτίμηση αυτή μπορεί να επεκταθεί έτσι ώστε να ικανοποιεί το αντίστοιχο σύνολο προτάσεων της $\phi'$ . Ισχύει και το αντίστροφο.

Η $C_i$ περιέχει τρεις μεταβλητές με θετικό πρόσημο. Έστω,

$C_i = (x_{i_1} \vee x_{i_2} \vee x_{i_3})$ . Σε αυτή την περίπτωση προσθέτουμε στη $\phi'$ το σύνολο των προτάσεων $\{ (\overline{y}_{i_1} \vee \overline{y}_{i_2} \vee {x}_{i_3}),$ $( x_{i_1} \vee y_{i_1}), ( x_{i_2} \vee y_{i_2}) \}$ . Οι προτάσεις αυτές είναι Horn ή σε 2ΣΚΜ και ορίζονται στις μεταβλητές που συμμετέχουν στη $C_i$ αλλά και σε δύο ακόμα βοηθητικές μεταβλητή, τις $y_{i_1}, y_{i_2}$ , οι οποίες εξαρτώνται από τη $C_i$ .\footnote{Εναλλακτικά, και για λόγους συμμετρίας, θα μπορούσαμε να ορίσουμε το σύνολο των προτάσεων $ $\{ (x_{i_1} \vee y_{i_1}), (\vee x_{i_2} \vee y_{i_2}),$ $( x_{i_3} \vee y_{i_3}), (\overline{y}_{i_1} \vee \overline{y}_{i_2} \vee \overline{y}_{i_3}) \}$ και να χρησιμοποιήσουμε τρεις βοηθητικές μεταβλητές.} Μπορούμε εύκολα να δούμε ότι αν υπάρχει αποτίμηση αλήθειας στις μεταβλητές της $C_i$ που ικανοποιεί τη $C_i$ , τότε η αποτίμηση αυτή μπορεί να επεκταθεί έτσι ώστε να ικανοποιεί το αντίστοιχο σύνολο προτάσεων της $\phi'$ . Ισχύει και το αντίστροφο.

Η Λογική έκφραση $\phi'$ ορίζεται σε $n' \leq n + 2m$ μεταβλητές και αποτελείται από $m' \leq 3m$ προτάσεις. Ισχυριζόμαστε ότι η $\phi$ είναι ικανοποιήσιμη αν και μόνο αν η $\phi'$ είναι ικανοποιήσιμη.

Έστω ότι η $\phi$ είναι ικανοποιήσιμη. Κάθε αποτίμηση αλήθειας στις $n$ μεταβλητές της $\phi$ που ικανοποιεί τις προτασείς της $\phi$ μπορεί να επεκταθεί στις $n'$ μεταβλητές της $\phi'$ έτσι ώστε να ικανοποιεί και τα αντίστοιχα σύνολα προτάσεων της $\phi'$ . Αντίστροφα, έστω ότι η $\phi'$ είναι ικανοποιήσιμη. Για κάθε αποτίμηση αλήθειας στις μεταβλητές της $\phi'$ που ικανοποιεί τη $\phi'$ , η αποτίμηση αληθειας που αντιστοιχεί στις $n$ μεταβλητές της $\phi$ ικανοποιεί τη $\phi$ .

Για να ολοκληρώσουμε την απόδειξη της πληρότητας πρέπει να αναφέρουμε ότι η αναγωγή που κατασκευάσαμε είναι λογαριθμικού χώρου, αφού η $\phi'$ είναι πολυωνυμικά μεγαλύτερη από την $\phi$ .

Αρχή της σελίδας

Το συμπλήρωμα της κλάσης ΝΡ

Ορίσαμε την κλάση NP ως το σύνολο των προβλημάτων που έχουν σύντομο πιστοποιητικό. Με άλλα λόγια, για κάθε "ΝΑΙ" στιγμιότυπο ενός προβλήματος στην κλάση NP υπάρχει τουλάχιστον ένα σύντομο πιστοποιητικό το οποίο αποτελεί απόδειξη για το ότι το στιγμιότυπο αυτό είναι πράγματι ένα "ΝΑΙ" στιγμιότυπο. Το συμπλήρωμα της κλάσης NP συμβολίζεται με coNP και περιέχει τα συμπληρώματα των γλωσσών που ανήκουν στην κλάση NP. Δηλαδή, για κάθε "ΟΧΙ" στιγμιότυπο ενός προβλήματος στην κλάση coNP υπάρχει σύντομο πιστοποητικό το οποίο αποτελεί απόδειξη για το ότι το στιγμιότυπο αυτό είναι πράγματι ένα "ΟΧΙ" στιγμιότυπο. Τα παραπάνω θα γίνουν πιο κατανοητά με το ακόλουθο παράδειγμα.

Παράδειγμα Ας θεωρήσουμε το συμπλήρωμα του προβλήματος της ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ, το πρόβλημα της ΜΗ ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ (UNSAT) στο οποίο δίνεται μια Λογική έκφραση $\phi$ σε Συζευκτική Κανονική Μορφή και ζητείται απάντηση στο ερώτημα αν η $\phi$ είναι μη ικανοποιήσιμη. Μπορούμε εύκολα να απαντήσουμε για την άρνηση του προβλήματος αυτού: αν η $\phi$ δεν είναι μη ικανοποιήσιμη, μπορούμε να βρούμε ένα σύντομο πιστοποιητικό που επαληθεύει το γεγονός αυτό: μια αποτίμηση αλήθειας στις μεταβλητές της $\phi$ που ικανοποιεί τη $\phi$ . Κατά συνέπεια το πρόβλημα της ΜΗ ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ ανήκει στην κλάση coNP.

Το πρόβλημα της ΜΗ ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ είναι μια διαφορετική διατύπωση του προβλήματος της ΕΓΚΥΡΟΤΗΤΑΣ (VALIDITY). Να θυμηθούμε ότι μια Λογική έκφραση είναι έγκυρη (ή ταυτολογία) αν ικανοποιείται από κάθε δυνατή αποτίμηση αληθείας. Επίσης, είναι εύκολο να δει δείξει κανείς ότι μια Λογική έκφραση $\phi$ είναι έγκυρη αν και μόνο αν η άρνηση αυτής, $\neg \phi$ , είναι μη ικανοποιήσιμη.\footnote{Ανατρέξτε στις διδακτικές σημειώσεις $\#14$.} Συνεπώς τα προβλήματα της ΜΗ ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ και της ΕΓΚΥΡΟΤΗΤΑΣ είναι ισοδύναμα (το πρώτο ανάγεται στο δεύτερο, και αντίστροφα).

Είναι προφανές ότι όλα τα προβλήματα που ανήκουν στην κλάση P ανήκουν και στην κλάση coNP αφού η ντετερμινιστική κλάση P $\subseteq$ NP είναι κλειστή ως προς το συμπλήρωμα.

Το πρόβλημα της ΕΓΚΥΡΟΤΗΤΑΣ είναι ένα παράδειγμα ενός coNP-πλήρους προβλήματος. Θα αποδείξουμε την πρόταση αυτή χρησιμοποιώντας τον ορισμό της πληρότητας: θα ανάγουμε κάθε γλώσσα στην κλάση coNP στην ΕΓΚΥΡΟΤΗΤΑ. Έστω $L$ μια γλώσσα στην κλάση coNP. Το συμπλήρωμα αυτής, $\overline{L}$ , θα ανήκει στην κλάση NP, άρα θα υπάρχει αποδοτική αναγωγή R της $\overline{L}$ στην ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑ. Δηλαδή, για κάθε συμβολοσειρά $x$ , $x \in \overline{L}$ ανν η $R(x)$ είναι ικανοποιήσιμη. Η αναγωγή της $L$ στην ΕΓΚΥΡΟΤΗΤΑ είναι η $R'(x) = \neg R(x)$ . Για κάθε συμβολοσειρά $x$ θα αποδείξουμε ότι $x \in L$ ανν η $R'(x)$ είναι έγκυρη. Η απόδειξη είναι απλή: $x \in L$ ανν $x \not\in \overline{L}$ ανν η $R(x)$ είναι μη ικανοποιήσιμη δηλαδή ανν η $R'(x)$ είναι έγκυρη.

Η επόμενη πρόταση είναι άμεση συνέπεια των παραπάνω:

Πρόταση 10

Αν μια γλώσσα είναι NP-πλήρης, τότε το συμπλήρωμα αυτής, $\overline{L}$ , είναι coNP-πλήρης.

Έτσι, τα συμπληρωματικά προβλήματα όλων των προβλημάτων που μέχρι τώρα έχουμε αποδείξει ότι είναι NP-πλήρη (3 ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑ, ΜΕΓΙΣΤΗ ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑ, ΚΛΙΚΑ, ΑΝΕΞΑΡΤΗΤΟ ΣΥΝΟΛΟ, ΚΑΛΥΜΜΑ ΚΟΡΥΦΩΝ κ.α.) είναι coNP-πλήρη προβλήματα

Το κατά πόσο ισχύει ότι NP $\neq$ coNP αποτελεί ένα ακόμα θεμελιώδες ερώτημα, όπως το ερώτημα εάν P $\neq$ NP. Είναι σαφές ότι αν P = NP τότε και NP=coNP αφού η κλάση P είναι κλειστή ως προς το συμπλήρωμα. Πιστεύεται ότι οι κλάσεις NP και coNP είναι διαφορετικές. Τα προβλήματα που είναι πλήρη για την κλάση coNP είναι το λιγότερο πιθανό να ανήκουν στην κλάση P. Το λιγότερο πιθανό για ένα coNP-πλήρες πρόβλημα είναι να ανήκει και στην κλάση NP:

Πρόταση 11

Αν μια coNP-πλήρης γλώσσα ανήκει στην κλάση NP, τότε NP=coNP.

Απόδειξη

Θα αποδείξουμε ότι αν μια γλώσσα $L \in$ NP είναι coNP-πλήρης, τότε coNP $\subseteq$ NP --- ο αντίστροφος εγκλεισμός αποδεικνύεται συμμετρικά. Έστω μια γλώσσα $L' \in$ coNP. Θα δείξουμε ότι $L' \in$ NP. Αφού η L ανήκει στην κλάση NP υπάρχει πολυωνυμικού χρόνου μη ντετερμινιστική μηχανή Turing, έστω $M_{L}$ , που αποφασίζει την $L$ . Επίσης, αφού η $L$ είναι coNP-πλήρης, θα υπάρχει αποδοτική αναγωγή $R$ από την $L'$ στην $L$ έτσι ώστε $x \in L' \Longleftrightarrow R(x) \in L$ . Έστω $M_R$ η λογαριθμικού χώρου (άρα και πολυωνυμικού χρόνου) ντετερμινιστική μηχανή Turing που υπολογίζει την $R$ . Κατασκευάζουμε μη ντετερμινιστική μηχανή Turing $M_{L'}$ η οποία με είσοδο $x$ αρχικά προσομοιώνει τη λειτουργία της $M_R$ με είσοδο $x$ για τον υπολογισμό της $R(x)$ και στη συνέχεια προσομοιώνει τη λειτουργία της $M_{L}$ με είσοδο $R(x)$ . Η $M_{L'}$ αποδέχεται την είσοδο $x$ αν η $M_{L}$ αποδέχεται την είσοδο $R(x)$ . Είναι φανερό ότι η $M_{L'}$ αποφασίζει τη γλώσσα $L'$ σε χρόνο φραγμένο από ένα πολυώνυμο του μήκους της εισόδου της. ʼΑρα η γλώσσα $L'$ ανήκει στην κλάση NP.

Κλείνοντας θα αποδείξουμε ένα ακόμα πλήρες πρόβλημα για την κλάση NP (οπότε το συμπληρωματικό πρόβλημα αυτού θα είναι πλήρες για την κλάση coNP). Πρόκειται για την 4 ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑ (4 SAT), μια ακόμα παραλλαγή του προβλήματος της ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ, όπου δίνεται μια Λογική έκφραση σε Συζευκτική Κανονική Μορφή με κάθε πρόταση της να περιέχει $4$ προσημασμένες μεταβλητές, και ζητείται απάντηση στο ερώτημα εάν η $\phi$ είναι ικανοποιήσιμη.

Η διαδικασία της απόδειξης της πληρότητας ενός προβλήματος για την κλάση NP είναι πλέον γνωστή. Το πρόβλημα προφανώς ανήκει στην κλάση NP. Για την αναγωγή θα χρησιμοποιήσουμε, τι πιο εύλογο, το πρόβλημα της 3 ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ. Έστω $\phi_3$ ένα τύχαιο στιγμιότυπο της 3 ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ. Θα κατασκευάσουμε στιγμιότυπο $\phi_4$ της 4 ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ έτσι ώστε η $\phi_3$ είναι ικανοποιήσιμη αν και μόνο αν η $\phi_4$ είναι ικανοποιήσιμη.

Έστω $C_i = (l_{i1} \vee l_{i2} \vee l_{i3}), i = 1, \ldots, m$ , μια πρόταση της $\phi_3$ . Τα $l_{ij}$ , $j=1,2,3,$ είναι προσημασμένες μεταβλητές από το σύνολο $X_3 = \{x_1, \ldots, x_n \}$ . Για κάθε πρόταση $C_i$ ορίζουμε τις προτάσεις $(l_{i1} \vee l_{i2} \vee l_{i3} \vee y_i)$ και $(l_{i1} \vee l_{i2} \vee l_{i3} \vee \overline{y}_i)$ , όπου $y_i$ είναι μια νέα μεταβλητή που εξαρτάται από την $C_i$ . Το σύνολο όλων αυτών των προτάσεων συνιστά την έκφραση $\phi_4$ . Η $\phi_4$ ορίζεται σε $n+m$ μεταβλητές, αποτελείται από $2m$ προτάσεις (όπως ορίστηκαν παραπάνω) και αποτελεί ένα νόμιμο στιγμιότυπο του προβλήματος της 4 ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ.

Είναι εύκολο να δει κανείς, από τον τρόπο που κατασκευάσαμε τη $\phi_4$ , ότι η $\phi_3$ είναι ικανοποιήσιμη αν και μόνο αν η $\phi_4$ είναι ικανοποιήσιμη. Επίσης, η κατασκευή της $\phi_4$ είναι αποδοτική (απαιτεί λογαριθμικό χώρο). Συνεπώς το πρόβλημα της 4 ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ είναι NP-πλήρες.

Να σημειώσουμε εδώ ότι το παραπάνω αποτέλεσμα γενικεύεται για οποιοδήποτε θετικό ακέραιo $k \geq 3$ , κατασκευάζοντας κάθε φορά την κατάλληλη αναγωγή. Δηλαδή το πρόβλημα της $k$ -ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ ( $k \geq 3$ ) είναι NP-πλήρες.

Αρχή της σελίδας

Βιβλιογραφικές Πηγές

1.[Καβ04] Δημήτριος Ι. Καββαδίας. Υπολογιστική Πολυπλοκότητα. Φεβρουάριος 2004. Πανεπιστημιακές Παραδόσεις.

2.[GJ79] Μ. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco, 1979.

3.[Pap94] C. H. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company, Reading, Massachusetts, 1994.

4.[Sip97] M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, Menlo Park, CA, 1997.

Αρχή της σελίδας

↑ [Καβ04] Δημήτριος Ι. Καββαδίας. Υπολογιστική Πολυπλοκότητα. Φεβρουάριος 2004. Πανεπιστημιακές Παραδόσεις.
↑ [Pap94] C. H. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company, Reading, Massachusetts, 1994.
↑ [Sip97] M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, Menlo Park, CA, 1997.
↑ [GJ79] Μ. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco, 1979.

[1] [Καβ04] Δημήτριος Ι. Καββαδίας. Υπολογιστική Πολυπλοκότητα. Φεβρουάριος 2004. Πανεπιστημιακές Παραδόσεις.

[2] [Pap94] C. H. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company, Reading, Massachusetts, 1994.

[3] [Sip97] M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, Menlo Park, CA, 1997.

[4] [GJ79] Μ. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco, 1979.

[1]

[2]

[3]

[4]

Difference between revisions of "Υπολογιστική Πολυπλοκότητα"

Latest revision as of 13:55, 24 January 2017

Contents

Υπολογιστική Πολυπλοκότητα

Προβλήματα και Αλγόριθμοι

Μηχανή Turing

Αναδρομικές και αναδρομικά αριθμήσιμες γλώσσες

Παραλλαγές της μηχανής Turing

H μη ντετερμινιστική μηχανή Turing

H αρχή της διαγωνοποίησης

Επιλύσιμα και μη επίλυσιμα προβλήματα

Το πρόβλημα του τερματισμού

Μη αποκρισιμότητα

Αναδρομικά μη διαχωρίσιμες γλώσσες

Κλάσεις πολυπλοκότητας

Στοιχεία από τη Λογική

Προβλήματα στη κλάση ΝΡ

Πληρότητα κατά ΝΡ

ΝΡ-πλήρη προβλήματα

Το συμπλήρωμα της κλάσης ΝΡ

Βιβλιογραφικές Πηγές

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Tools

Revision as of 10:46, 21 December 2016 (view source) Admin (Talk \| contribs) m (Protected "Υπολογιστική Πολυπλοκότητα" ([Edit=Allow only administrators] (indefinite) [Move=Allow only administrators] (indefinite)) [cascading]) ← Older edit	Latest revision as of 13:55, 24 January 2017 (view source) Admin (Talk \| contribs) m (Changed protection level for "Υπολογιστική Πολυπλοκότητα" ([Edit=Allow only autoconfirmed users] (indefinite) [Move=Allow only administrators] (indefinite)))
(No difference)

$x$	$y$	$\neg x$	$x \wedge y$	$x \vee y$	$x \oplus y$	$x \Rightarrow y$	$x \Leftrightarrow y$
$0$	$0$	$1$	$0$	$0$	$0$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$1$	$1$	$0$
$1$	$0$	$0$	$0$	$1$	$1$	$0$	$0$
$1$	$1$	$0$	$1$	$1$	$0$	$1$	$1$

$x$	$y$	$\neg x$	$x \wedge y$	$x \vee y$	$x \oplus y$	$x \Rightarrow y$	$x \Leftrightarrow y$
$0$	$0$	$1$	$0$	$0$	$0$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$1$	$1$	$0$
$1$	$0$	$0$	$0$	$1$	$1$	$0$	$0$
$1$	$1$	$0$	$1$	$1$	$0$	$1$	$1$

$x$	$y$	$\neg x$	$x \wedge y$	$x \vee y$	$x \oplus y$	$x \Rightarrow y$	$x \Leftrightarrow y$
$0$	$0$	$1$	$0$	$0$	$0$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$1$	$1$	$0$
$1$	$0$	$0$	$0$	$1$	$1$	$0$	$0$
$1$	$1$	$0$	$1$	$1$	$0$	$1$	$1$