Πρόβλημα απόφασης

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

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

Για παράδειγμα, το ακόλουθο πρόβλημα: «δοθέντων δύο αριθμών x και y, διαιρεί τέλεια ο x τον y;» είναι ένα πρόβλημα απόφασης. Η απάντηση μπορεί να είναι είτε «ναι» είτε «όχι», και εξαρτάται από τις τιμές των x και y. Μια μέθοδος για την επίλυση τέτοιου προβλήματος, δοσμένης με τη μορφή αλγορίθμου, αποκαλείται διαδικασία απόφασης. Μια διαδικασία απόφασης για το παραπάνω πρόβλημα θα έδινε τα βήματα εκείνα για να διαπιστώσουμε αν ο x διαιρεί τέλεια τον y, δοσμένων των x και y. Ένας τέτοιος αλγόριθμος είναι η μακρά διαίρεση, που διδάσκεται σε πολλά σχολεία. Αν το υπόλοιπο είναι ίσο με μηδέν, τότε η απάντηση στο πρόβλημα είναι «ναι», σε αντίθετη περίπτωση είναι «όχι». Ένα πρόβλημα απόφασης που δύναται να επιλυθεί με κάποιον αλγόριθμο, όπως στο παράδειγμα, αποκαλείται αποκρίσιμο (ή αποφασίσιμο).

Ο τομέας της υπολογιστικής πολυπλοκότητας κατηγοριοποιεί τα αποκρίσιμα προβλήματα απόφασης με κριτήριο τη δυσκολία επίλυσής τους. Υπό αυτή την έννοια, το «δύσκολο» ορίζεται βάσει των υπολογιστικών πόρων που απαιτεί ο πιο αποδοτικός αλγόριθμος για ένα συγκεκριμένο πρόβλημα. Παράλληλα, ο τομέας της θεωρίας υπολογισιμότητας κατηγοριοποιεί τα μη αποκρίσιμα προβλήματα απόφασης με το βαθμό Turing, ο οποίος αποτελεί ένα μέτρο της μη υπολογισιμότητας που είναι εγγενής σε οποιαδήποτε λύση. Μια στενά συνδεδεμένη κατηγορία των προβλημάτων απόφασης αποτελούν τα προβλήματα συνάρτησης, τα οποία απαιτούν μια πιο περίπλοκη λύση από ένα απλό «ναι» ή «όχι». Ένα αντίστοιχο παράδειγμα προβλήματος είναι το εξής: «δοθέντων δύο αριθμών x και y, ποιο είναι το αποτέλεσμα του x διαιρούμενου με το y;». Τα προβλήματα απόφασης συνδέονται επίσης με τα προβλήματα βελτιστοποίησης, τα οποία απαιτούν τη βέλτιστη λύση για ένα συγκεκριμένο πρόβλημα. Υπάρχουν πρότυπες τεχνικές για το μετασχηματισμό προβλημάτων συνάρτησης σε βελτιστοποίησης, και το αντίστροφο, οι οποίες δεν αλλάζουν ιδιαίτερα την υπολογιστική δυσκολία των προβλημάτων. Για το λόγο αυτό, η έρευνα στη θεωρία υπολογισιμότητας και πολυπλοκότητας έχει επικεντρωθεί κυρίως στα προβλήματα απόφασης.

Ορισμός

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

Αυτές οι είσοδοι μπορεί να είναι φυσικοί αριθμοί, ή ακόμη και τιμές οποιουδήποτε είδους, όπως συμβολοσειρές στο δυαδικό αλφάβητο {0,1} ή κάποιο άλλο πεπερασμένο σύνολο συμβόλων. Το υποσύνολο των εισόδων για τα οποία το πρόβλημα επιλύεται με «ναι» αποτελεί μια τυπική γλώσσα και συχνά τα προβλήματα απόφασης ορίζονται κατ' αυτό τον τρόπο ως τυπικές γλώσσες.

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

Παραδείγματα

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

Αποκρισιμότητα (ή αποφασισιμότητα)

Ένα πρόβλημα απόφασης Α καλείται αποκρίσιμο (decidable), αποφασίσιμο ή αποτελεσματικά επιλύσιμο (effectively solvable) αν αποτελεί αναδρομικό σύνολο. Ένα πρόβλημα καλείται μερικώς αποκρίσιμο (partially decidable), ημι-αποκρίσιμο (semidecidable), επιλύσιμο (solvable) ή αποδείξιμο (provable) αν αποτελεί αναδρομικά απαριθμίσιμο σύνολο. Προβλήματα που δεν είναι αποκρίσιμα ονομάζονται μη αποκρίσιμα (undecidable).

Το πρόβλημα τερματισμού αποτελεί ένα σημαντικό μη αποκρίσιμο πρόβλημα απόφασης.

Ισοδυναμία με προβλήματα συνάρτησης

Ένα πρόβλημα συνάρτησης αποτελείται από μια μερική συνάρτηση f. Άτυπα, το πρόβλημα είναι ο υπολογισμός των τιμών της f στις εισόδους για τις οποίες ορίζεται.

Κάθε πρόβλημα συνάρτησης μπορεί να μετασχηματιστεί σε πρόβλημα απόφασης, αφού το τελευταίο αποτελεί ουσιαστικά το γράφο της αντίστοιχης συνάρτησης (Ο γράφος μιας συνάρτησης f είναι το σύνολο των ζευγών (x,y) για τα οποία f(x) = y). Αν το πρόβλημα απόφασης είναι αποτελεσματικά επιλύσιμο, τότε το ίδιο θα είναι και το αντίστοιχο πρόβλημα συνάρτησης. Όμως αυτή η μετατροπή δε διατηρεί την υπολογιστική πολυπλοκότητα. Για παράδειγμα, είναι πιθανό ο γράφος μιας συνάρτησης να είναι αποκρίσιμος σε πολυωνυμικό χρόνο (στην οποία περίπτωση ο χρόνος εκτέλεσης υπολογίζεται ως συνάρτηση του ζεύγους (x,y)) ενώ η συνάρτηση να μην είναι υπολογίσιμη σε πολυωνυμικό χρόνο (της οποίας ο χρόνος εκτέλεσης υπολογίζεται ως συνάρτηση μόνο του x). Μια συνάρτηση με αυτή την ιδιότητα είναι η f(x) = 2^x.

Παραπομπές

• Kozen, D.C. (1997), Automata and Computability, Springer.
• Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
• Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
• Robert I. Soare (1987), Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7
• Daniel Kroening & Ofer Strichman, Decision procedures, Springer, ISBN 978-3-540-74104-6
• Aaron Bradley & Zohar Manna, The calculus of computation, Springer, ISBN 978-3-540-74112-1