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

μ
καμία σύνοψη επεξεργασίας
(Δημιουργήθηκε από μετάφραση της σελίδας "Decision problem")
 
μ
<span class="cx-segment" data-segmentid="71"></span>Ένα πρόβλημα απόφασης Α καλείται ''αποκρίσιμο'' (''decidable''), ''αποφασίσιμο'' ή ''αποτελεσματικά επιλύσιμο'' (''effectively solvable'') αν αποτελεί [[αναδρομικό σύνολο]]. Ένα πρόβλημα καλείται ''μερικώς αποκρίσιμο'' (''partially decidable''), ''ημι-αποκρίσιμο'' (''semidecidable''), ''επιλύσιμο'' (''solvable'') ή ''αποδείξιμο'' (''provable'') αν αποτελεί [[αναδρομικά απαριθμίσιμο σύνολο]]. Προβλήματα που δεν είναι αποκρίσιμα ονομάζονται ''μη αποκρίσιμα'' (''undecidable'').
 
Το [[πρόβλημα τερματισμού]] αποτελεί ένα σημαντικό μη αποκρίσιμο πρόβλημα απόφασης.<span class="cx-segment" data-segmentid="86"></span>
 
<span class="cx-segment" data-segmentid="86"></span>
 
== Ισοδυναμία με προβλήματα συνάρτησης ==
Ένα [[πρόβλημα συνάρτησης]] αποτελείται από μια [[μερική συνάρτηση]] ''f''. Άτυπα, το πρόβλημα είναι ο υπολογισμός των τιμών της ''f'' στις εισόδους για τις οποίες ορίζεται.
 
Κάθε πρόβλημα συνάρτησης μπορεί να μετασχηματιστεί σε πρόβλημα απόφασης, αφού το τελευταίο αποτελεί ουσιαστικά το γράφο της αντίστοιχης συνάρτησης (Ο γράφος μιας συνάρτησης ''f'' είναι το σύνολο των ζευγών (''x'',''y'') για τα οποία ''f''(''x'') = ''y''). Αν το πρόβλημα απόφασης είναι αποτελεσματικά επιλύσιμο, τότε το ίδιο θα είναι και το αντίστοιχο πρόβλημα συνάρτησης. Όμως αυτή η μετατροπή δε διατηρεί την υπολογιστική πολυπλοκότητα. Για παράδειγμα, είναι πιθανό ο γράφος μιας συνάρτησης να είναι αποκρίσιμος σε [[Πολυωνυμικός χρόνος|πολυωνυμικό χρόνο]] (στην οποία περίπτωση ο χρόνος εκτέλεσης υπολογίζεται ως συνάρτηση του ζεύγους (''x,y'')) ενώ η συνάρτηση να μην είναι υπολογίσιμη σε πολυωνυμικό χρόνο (της οποίας ο χρόνος εκτέλεσης υπολογίζεται ως συνάρτηση μόνο του ''x''). Μια συνάρτηση με αυτή την ιδιότητα είναι η ''f''(''x'') = ''2''<sup>''x''</sup>.<span class="cx-segment" data-segmentid="114"></span>
 
 
<span class="cx-segment" data-segmentid="114"></span>
 
== Παραπομπές ==
* Daniel Kroening & Ofer Strichman, ''Decision procedures'', Springer, [[:en:Special:BookSources/9783540741046|ISBN 978-3-540-74104-6]]
* Aaron Bradley & Zohar Manna, ''The calculus of computation'', Springer, [[:en:Special:BookSources/9783540741121|ISBN 978-3-540-74112-1]]
[[Κατηγορία:Θεωρία υπολογισιμότητας]]
[[Κατηγορία:Υπολογιστικά προβλήματα]]
56

επεξεργασίες