Υπολογιστικός πόρος

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

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

Ένα υπολογιστικό πρόβλημα ορίζεται γενικά με βάση την ενέργεια που απαιτείται να διεκπεραιώσει σε κάποια έγκυρη είσοδο. Παραδείγματα προβλημάτων είναι: «Δεδομένου ενός ακέραιου n, να αποφανθεί εάν το n είναι πρώτος», ή «Δεδομένων δύο αριθμών x και y, να υπολογιστεί το γινόμενο x*y». Καθώς η είσοδος μεγαλώνει, αυξάνεται και το πλήθος των υπολογιστικών πόρων που απαιτούνται για την επίλυση του προβλήματος. Έτσι οι αναγκαίοι πόροι περιγράφονται με όρους ασυμπτωτικής ανάλυσης, εκφράζοντάς τους ως συνάρτηση του μήκους ή του μεγέθους της εισόδου. Η χρήση πόρων συχνά ποσοτικοποιείται εν μέρει με Big O notation.

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