Η υπολογισιμότητα και η υπολογιστική πολυπλοκότητα μελετούν τα όρια των αλγορίθμων: τι μπορεί να λυθεί με καθορισμένες διαδικασίες και με πόσους πόρους (χρόνο, μνήμη) γίνεται αυτό. Με απλά λόγια, η υπολογισιμότητα ρωτά «γίνεται;», ενώ η πολυπλοκότητα ρωτά «πόσο κοστίζει;».
Για να ορίσουμε με ακρίβεια αυτές τις έννοιες χρησιμοποιούμε μοντέλα υπολογισμού, όπως οι μηχανές Turing και οι πεπερασμένοι αυτόματοι. Τα μοντέλα αυτά μάς επιτρέπουν να περιγράψουμε αλγορίθμους και προβλήματα με τυπικό τρόπο, ώστε να συγκρίνουμε λύσεις και όρια ανεξάρτητα από τη γλώσσα προγραμματισμού ή τον υπολογιστή.
Με βάση αυτά τα μοντέλα ταξινομούμε τα προβλήματα σε κλάσεις πολυπλοκότητας. Η κλάση P περιλαμβάνει προβλήματα που λύνονται αποδοτικά (σε πολυωνυμικό χρόνο), η NP εκείνα για τα οποία μια προτεινόμενη λύση ελέγχεται γρήγορα, ενώ τα NP-πλήρη θεωρούνται τα δυσκολότερα της NP. Παράλληλα, υπάρχουν προβλήματα μη αποφασίσιμα (undecidable), όπως παραλλαγές του «προβλήματος τερματισμού», για τα οποία δεν υπάρχει κανένας αλγόριθμος που να δίνει σωστή απάντηση σε όλες τις περιπτώσεις.
Το παρόν κείμενο λειτουργεί ως φόντο και ορισμολογικό πλαίσιο για αυτές τις ιδέες: τι σημαίνει αλγόριθμος σε τυπικό μοντέλο, πώς μετράμε την αποδοτικότητα, και πώς οι κλάσεις όπως P, NP και τα μη αποφασίσιμα προβλήματα οργανώνουν τον «χάρτη» του τι είναι εφικτό και με ποιο κόστος.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου