35
της αρχικής καμπύλης, εξάγεται η νέα καμπύλη που αποτελείται από όσα σημεία έχουν
μαρκαριστεί προς διατήρηση.
Εικόνα 2.12: Αλγόριθμος Ramer-Douglas-Peucker [
].
2.4 Κλάσεις Πολυπλοκότητας Προβλημάτων
Οι κλάσεις πολυπλοκότητας αποτελούν τον ακρογωνιαίο λίθο της θεωρίας
πολυπλοκότητας και κεντρικό ζήτημα του κλάδου της θεωρητικής πληροφορικής. Κάθε
κλάση περιέχει προβλήματα που απαιτούν ίδιο χώρο και χρόνο, ενώ συνήθως η ταξινόμηση
τους γίνεται εκτελώντας το πρόβλημα σε ένα αυτόματο όπως οι Μηχανές Turing. Η ιεραρχία
των κλάσεων δομείται με την οργάνωση τους σε σύνολα και υποσύνολα. Για παράδειγμα, η
κλάση P που περιέχει τα προβλήματα που επιλύονται σε ντετερμινιστικό πολυωνυμικό χρόνο
είναι υποσύνολο της κλάσης προβλημάτων NP που λύνονται σε μη ντετερμινιστικό
πολυωνυμικό χρόνο [Εικόνα 2.13] [48], [49].
Η μελέτη των κλάσεων συνεισφέρει στην πληροφορική ταξινομώντας τα προβλήματα
κατά το χώρο και το χρόνο που απαιτείται για την επίλυση και επαλήθευση της λύσης [50]. Η
χρονική πολυπλοκότητα ενός αλγορίθμου περιγράφεται από τον αριθμό βημάτων που
χρειάζονται για την επίλυση ενός προβλήματος, αλλά μπορεί να περιγράψει και πόσο χρόνο
παίρνει η επιβεβαίωση της λύσης. Γνωρίζοντας την χρονική πολυπλοκότητα οι
προγραμματιστές έχουν μία εικόνα για την απόδοση του αλγορίθμου τους. Η χωρική
πολυπλοκότητα περιγράφει τη μνήμη που απαιτεί ο αλγόριθμος για την εκτέλεσή του.
Μερικά από τα πιο μεγάλα προβλήματα που δεν έχουν επιλυθεί πραγματεύονται την
απόδειξη της ισότητας μεταξύ δύο υποσύνολων. Ένα από τα πιο γνωστά προβλήματα είναι το
P = NP που αναφέρθηκε κατά την εισαγωγή της εργασίας [51], [52]. Η επίλυση του
προβλήματος αυτού θα προκαλούσε χάος στην προγραμματιστική κοινότητα καθώς πολλοί