Πρόβλημα απόφασης
From Wikipedia, the free encyclopedia
Στη θεωρία υπολογισιμότητας και τη θεωρία πολυπλοκότητας, ένα πρόβλημα απόφασης είναι ένα ερώτημα σε κάποιο τυπικό σύστημα που επιδέχεται μιας ναι ή όχι απάντησης, ανάλογα με τις τιμές κάποιων παραμέτρων εισόδου. Τα προβλήματα απόφασης εμφανίζονται συνήθως σε μαθηματικά ερωτήματα αποκρισιμότητας (αποφασισιμότητας), δηλαδή ερωτήματα σχετικά με την ύπαρξη ή μη κάποιας συστηματικής μεθόδου για να προσδιοριστεί αν κάποιο αντικείμενο υπάρχει ή αν ανήκει σε κάποιο σύνολο· κάποια από τα πιο σημαντικά προβλήματα των μαθηματικών είναι μη αποκρίσιμα (μη αποφασίσιμα).
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Για παράδειγμα, το ακόλουθο πρόβλημα: «δοθέντων δύο αριθμών x και y, διαιρεί τέλεια ο x τον y;» είναι ένα πρόβλημα απόφασης. Η απάντηση μπορεί να είναι είτε «ναι» είτε «όχι», και εξαρτάται από τις τιμές των x και y. Μια μέθοδος για την επίλυση τέτοιου προβλήματος, δοσμένης με τη μορφή αλγορίθμου, αποκαλείται διαδικασία απόφασης. Μια διαδικασία απόφασης για το παραπάνω πρόβλημα θα έδινε τα βήματα εκείνα για να διαπιστώσουμε αν ο x διαιρεί τέλεια τον y, δοσμένων των x και y. Ένας τέτοιος αλγόριθμος είναι η μακρά διαίρεση, που διδάσκεται σε πολλά σχολεία. Αν το υπόλοιπο είναι ίσο με μηδέν, τότε η απάντηση στο πρόβλημα είναι «ναι», σε αντίθετη περίπτωση είναι «όχι». Ένα πρόβλημα απόφασης που δύναται να επιλυθεί με κάποιον αλγόριθμο, όπως στο παράδειγμα, αποκαλείται αποκρίσιμο (ή αποφασίσιμο).
Ο τομέας της υπολογιστικής πολυπλοκότητας κατηγοριοποιεί τα αποκρίσιμα προβλήματα απόφασης με κριτήριο τη δυσκολία επίλυσής τους. Υπό αυτή την έννοια, το «δύσκολο» ορίζεται βάσει των υπολογιστικών πόρων που απαιτεί ο πιο αποδοτικός αλγόριθμος για ένα συγκεκριμένο πρόβλημα. Παράλληλα, ο τομέας της θεωρίας υπολογισιμότητας κατηγοριοποιεί τα μη αποκρίσιμα προβλήματα απόφασης με το βαθμό Turing, ο οποίος αποτελεί ένα μέτρο της μη υπολογισιμότητας που είναι εγγενής σε οποιαδήποτε λύση. Μια στενά συνδεδεμένη κατηγορία των προβλημάτων απόφασης αποτελούν τα προβλήματα συνάρτησης, τα οποία απαιτούν μια πιο περίπλοκη λύση από ένα απλό «ναι» ή «όχι». Ένα αντίστοιχο παράδειγμα προβλήματος είναι το εξής: «δοθέντων δύο αριθμών x και y, ποιο είναι το αποτέλεσμα του x διαιρούμενου με το y;». Τα προβλήματα απόφασης συνδέονται επίσης με τα προβλήματα βελτιστοποίησης, τα οποία απαιτούν τη βέλτιστη λύση για ένα συγκεκριμένο πρόβλημα. Υπάρχουν πρότυπες τεχνικές για το μετασχηματισμό προβλημάτων συνάρτησης σε βελτιστοποίησης, και το αντίστροφο, οι οποίες δεν αλλάζουν ιδιαίτερα την υπολογιστική δυσκολία των προβλημάτων. Για το λόγο αυτό, η έρευνα στη θεωρία υπολογισιμότητας και πολυπλοκότητας έχει επικεντρωθεί κυρίως στα προβλήματα απόφασης.