More Related Content
What's hot (20)
Viewers also liked (20)
More from Dimitris Psounis (20)
Recently uploaded (20)
ΚΑΡΤΕΣ ΜΑΘΗΜΑΤΟΣ 6.1
- 1. Θεώρημα: Ισχύει ότι: ⊆ ⊆ • ⊆ είναι προφανές, αφού κάθε ντετερμινιστική Μ.Τ. είναι εξ’ορισμού και μη ντετερμινιστική. • ⊆ . Η απόδειξη στηρίζεται στην προσομοίωση μια μη ντετερμινιστικής Μ.Τ. Ν από μία ντετερμινιστική Μ ως εξής: • Η Ν είναι πολυωνυμικού χρόνου, άρα κάθε υπολογισμός της έχει πολυωνυμικό μήκος έστω p=nk, όπου n το μέγεθος της εισόδου. • Κάθε υπολογισμός της Ν είναι μια ακολουθία από μη ντετερμινιστικές επιλογές. Αν είναι d ο βαθμός του μη ντετερμινισμού, τότε υπάρχουν dp δυνατοί μη ντετερμινιστικοί υπολογισμοί. • Η Μ προσομοιώνει εξαντλητικά κάθε μη ντετερμινιστικό υπολογισμό διαπερνώντας όλο του δένδρο του μη ντετερμινιστικού υπολογισμού. • Συνεπώς ο χρόνος λειτουργίας της είναι p∙dp, άρα εκθετικός • Συνεπώς ⊆ -ΠΗΡΟΤΗΤΑΚΛΑΣΕΙΣ ΠΟΛΥΠΛΟΚΟΤΗΤΑΣ !"#$%& ' & ( ( !"#$%& ' & ) #* !"#$2,- ' & !"#$. % ' είναι το σύνολο των προβληµάτων που λύνονται σε ντετερµινιστικό χρόνο /$. % ' τότε: ( !"#$. % ' είναι το σύνολο των προβληµάτων που λύνονται σε µη ντετερµινιστικό χρόνο /$. % '
- 2. -ΠΗΡΟΤΗΤΑΗ ΚΛΑΣΗ των NP-COMPLETE ΠΡΟΒΛΗΜΑΤΩΝ Διαισθητικά σε μια κλάση προβλημάτων C ορίζουμε: • C-πλήρη (C-Complete) τα προβλήματα της κλάσης που: • Είναι τα δυσκολότερα προβλήματα της κλάσης (υπό την έννοια ότι κάθε πρόβλημα της κλάσης είναι το πολύ τόσο δύσκολα όσο αυτά) • Είναι ισοδύναμα μεταξύ τους (δηλαδή αντίστοιχης υπολογιστικής δυσκολίας) • Έτσι για την κλάση NP, ορίζουμε ότι ένα πρόβλημα είναι NP-πλήρες (ή NP-Complete): • Αν κάθε πρόβλημα στην κλάση NP, είναι το πολύ τόσο δύσκολο όσο αυτό. • έχει αποδειχθεί από τον (Cook,1970) ότι: Το SAT είναι NP-πλήρες • Συνεπώς οποιοδήποτε πρόβλημα του NP είναι το πολύ τόσο δύσκολο όσο το SAT! Τα προβλήματα της κλάσης NP-COMPLETE έχουν τις εξής ιδιότητες: 1. Λύνονται σε εκθετικό ντετερμινιστικό χρόνο (ανήκουν στο EXP) 2. Λύνονται σε πολυωνυμικό μη ντετερμινιστικό χρόνο (ανήκουν στο NP) 3. Δεν έχει αποδειχθεί ότι δεν λύνονται από ντετερμινιστικό πολυωνυμικό αλγόριθμο. • Αν αποδειχθεί ότι ένα από αυτά δεν λύνεται σε πολυωνυμικό ντετερμινιστικό χρόνο, τότε κανένα δεν λύνεται σε ντετερμινιστικό πολυωνυμικό χρόνο • Άρα 0 4. Δεν έχει αποδειχθεί ότι λύνονται από ντετερμινιστικό πολυωνυμικό αλγόριθμο. • Αν αποδειχθεί ότι ένα από αυτά λύνεται σε πολυωνυμικό ντετερμινιστικό χρόνο, τότε όλα λύνονται σε ντετερμινιστικό πολυωνυμικό χρόνο • Άρα 5. Όλα τα προβλήματα της κλάσης NP ανάγονται σε αυτά. Για να αποδειχθεί ότι ένα πρόβλημα είναι NP-πλήρες: • (Α) Δείχνουμε ότι ανήκει στο NP • (Β) Δείχνουμε ότι ένα NP-πλήρες πρόβλημα ανάγεται σε αυτό Για να αποδειχθεί ότι ένα πρόβλημα είναι NP-σκληρό (NP-Hard): • (A) Δείχνουμε ότι ένα NP-πλήρες πρόβλημα ανάγεται σε αυτό
- 3. -ΠΗΡΟΤΗΤΑΑΠΟΔΕΙΞΕΙΣ -ΠΗΡΟΤΗΤΑΣ Για να αποδείξουμε ότι ένα πρόβλημα Π είναι NP-πλήρες, ακολουθούμε την εξής διαδικασία: 1. Αποδεικνύουμε ότι 1 ∈ • Είτε δίνοντας μη ντετερμινιστική μηχανή Turing-μάντη που «μαντεύει» την λύση και έπειτα επαληθεύει ότι είναι όντως λύση του προβλήματος. • Είτε δίνοντας ντετερμινιστική μηχανή Turing-επαληθευτή που δεδομένης μιας λύσης (πιστοποιητικό) επαληθεύει σε πολυωνυμικό ντετερμινιστικό χρόνο ότι είναι λύση του προβλήματος. 2. Δίνουμε μια πολυωνυμική αναγωγή από ένα γνωστό NP-πλήρες πρόβλημα Π’ στο πρόβλημα Π (Η αναγωγή συμβολίζεται με Π’≤Π) • Όπου δίνουμε έναν κανόνα μετασχηματισμού της εισόδου Ε’ του γνωστού προβλήματος Π’ σε είσοδο E του αγνώστου προβλήματος Π έτσι ώστε για κάθε στιγμιότυπο: Αποτέλεσμα του Π(Ε) ισοδύναμο με αποτέλεσμα του Π’(Ε΄) Και δείχνουμε ότι η κατασκευή θέλει πολυωνυμικό χρόνο