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

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

Γενικά

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

Συμβολισμός

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

Η ζήτημα P=NP

Computational complexity theory | Komplexitätstheorie | Complexité algorithmique | 計算の複雑さ | Z%C5%82o%C5%BCono%C5%9B%C4%87 obliczeniowa | Komplexitetsteori