Θεωρία Πολυπλοκότητας

Από την Live-Pedia.gr

Θεωρία Πολυπλοκότητας

Η Θεωρία Πολυπλοκότητας είναι το μέρος εκείνο της Θεωρίας Υπολογισμού, το οποίο ασχολείται με την κοστολόγιση των πόρων που απαιτούνται για την αλγοριθμική επίλυση ενός προβλήματος.

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

Θέματα Πολυπλοκότητας

• Μηχανές Turing,
• Μέθοδος Διαγωνοποίησης,
• Αποφασίσιμες και Μη αποφασίσιμες γλώσσες
• Θεώρημα του Rice,
• Θεώρημα της Αναδρομής,
• Θεώρημα του Smn.
• Μέτρηση πολυπλοκότητας (χρόνος και χώρος),
• Περιορισμοί στους πόρους υπολογισμού,
• Κλάσεις P, NP, PSPACE, και NSPACE,
• Θεώρημα του Savitch,
• Σχέσεις μεταξύ κλάσεων πολυπλοκότητας,
• Ιεραρχία κλάσεων DSPACE και DTIME.
• θεώρημα του Cook,
• Πολυωνυμική ιεραρχία χρόνου,
• Πρόβλημα QBF,
• Αλγόριθμος Monte Carlo,
• Αλγόριθμος Las Vegas.

Το παρόν άρθρο βασίζεται στο λήμμα Θεωρία_Πολυπλοκότητας της Βικιπαίδειας (συνεισφορά).