Πρόβλημα απόφασης: Διαφορά μεταξύ των αναθεωρήσεων

[[Αρχείο:Decision_Problem.svg|μικρογραφία|249x249εσ|Ένα πρόβλημα απόφασης έχει μόνο δύο πιθανές εξόδους, ''ναι ''ή ''όχι''  (ή εναλλακτικά, 1 ή 0) για κάθε πιθανή είσοδο.]]

<span class="cx-segment" data-segmentid="11"></span>Στη [[θεωρία υπολογισιμότητας]] και τη [[θεωρία πολυπλοκότητας]], ένα '''πρόβλημα απόφασης''' είναι ένα ερώτημα σε κάποιο [[τυπικό σύστημα]] που επιδέχεται μιας ναι ή όχι απάντησης, ανάλογα με τις τιμές κάποιων παραμέτρων εισόδου. Τα προβλήματα απόφασης εμφανίζονται συνήθως σε μαθηματικά ερωτήματα [[Αποκρισιμότητα|αποκρισιμότητας]] (αποφασισιμότητας), δηλαδή ερωτήματα σχετικά με την ύπαρξη ή μη κάποιας συστηματικής μεθόδου για να προσδιοριστεί αν κάποιο αντικείμενο υπάρχει ή αν ανήκει σε κάποιο σύνολο· κάποια από τα πιο σημαντικά προβλήματα των μαθηματικών είναι [[Μη αποκρίσιμο πρόβλημα|μη αποκρίσιμα]] (μη αποφασίσιμα).