Η θεωρία υπολογιστικής πολυπλοκότητας(computational complexity theory)

Η θεωρία υπολογιστικής πολυπλοκότητας(computationalcomplexity theory) είναι

η περιοχή της θεωρητικής επιστήµης των υπολογιστών που εξετάζει τους λόγους για

τους οποίουςµερικά προβλήµατα είναι δύσκολο ή και αδύνατον να λυθούν από έναν

υπολογιστή. Η υπολογιστική πολυπλοκότητα(ή απλά πολυπλοκότητα), που, ουσια-στικά, δεν υπήρχε σαν επιστηµονική περιοχή πριν εικοσιπέντε χρόνια, γνώρισε

ραγδαία ανάπτυξη, και σήµερα αποτελείµία από τις σηµαντικότερες περιοχές της

θεωρητικής επιστήµης των υπολογιστών.

Η θεωρία πολυπλοκότητας προσπαθεί κατ’ αρχήν να αναγνωρίσει τα προβλήµατα

που δενµπορούν να λυθούν από έναν υπολογιστή. Ένα παράδειγµα προβλήµατος που

δενµπορεί να λυθεί είναι το διάσηµο πρόβληµα του τερµατισµού(Halting Problem)

µιαςµηχανήςTuring.

Από την άλλη πλευρά, υπάρχει ηµεγάλη κατηγορία των προβληµάτων πουµπορούν

να λυθούν από τους υπολογιστές. Γι΄ αυτά τα προβλήµατα, η θεωρία πολυπλο-κότητας µελετά την ποσότητα των υπολογιστικών πόρων που είναι απαραίτητοι για

την επίλυση κάθε προβλήµατος σε διάφορα αντιπροσωπευτικά υπολογιστικάµοντέ-λα. Ένα κεντρικό ερώτηµα είναι η επίδραση του υπολογιστικούµοντέλου στους

πόρους που απαιτεί η επίλυση του προβλήµατος.

Εξετάζοντας τη συµπεριφορά των προβληµάτων όσον αφορά τους υπολογιστικούς

πόρους που απαιτούνται για την επίλυσή τους σε διάφορα υπολογιστικάµοντέλα, η

θεωρία πολυπλοκότητας προσπαθεί να εντάξει τα προβλήµατα σε κλάσεις πολυπλο-κότητας(complexity classes), δηλαδή οµάδες προβληµάτωνµε παρόµοια συµπερι-φορά. Τα προβλήµατα κάθε κλάσης ανάγονται σε έναν σχετικάµικρό αριθµό προβλη-µάτων που θεωρούνται αντιπροσωπευτικά για όλη την κλάση. Τα προβλήµατα αυτά

ονοµάζονται πλήρη(complete) για την κλάση και οιµέθοδοι αναγωγής εξασφαλίζουν

ότι, αν κάποια σηµαντική πρόοδος συµβεί στην επίλυση ενός από τα πλήρη προβλή-µατα, αυτή θα έχει εφαρµογή στην επίλυση όλων των προβληµάτων της κλάσης.

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

Το κεφάλαιο αυτό περιέχει τις παρακάτω ενότητες:

7.1. Αλγόριθµοι και Προβλήµατα

7.2. Ντετερµινιστικές ΜηχανέςTuring

7.3. Χρονική Πολυπλοκότητα και η Κλάση P

7.4. Αναγωγή και Πληρότητα