Πρόβλημα υπόσχεσης

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Πήδηση στην πλοήγηση Πήδηση στην αναζήτηση

Στη θεωρία υπολογιστικής πολυπλοκότητας, ένα πρόβλημα υπόσχεσης είναι μια γενίκευση κάποιου προβλήματος απόφασης, για το οποίο μάς δίνεται η διαβεβαίωση ότι δέχεται εισόδους από ένα συγκεκριμένο υποσύνολο όλων των πιθανών εισόδων.[1]Σε αντίθεση με τα προβλήματα απόφασης, τα ναι στιγμιότυπα (οι είσοδοι για τις οποίες ο αλγόριθμος πρέπει υποχρεωτικά να επιστρέψει ναι) και τα όχι στιγμιότυπα δεν εξαντλούν το σύνολο όλων των πιθανών εισόδων. Διαισθητικά, ο αλγόριθμος έχει λάβει τη διαβεβαίωση (υπόσχεση) ότι η είσοδος θα ανήκει σε κάποιο σύνολο ναι στιγμιοτύπων ή όχι στιγμιοτύπων. Μπορεί όμως να υπάρχουν και είσοδοι που δεν είναι ούτε ναι ούτε όχι. Εάν δοθεί στον αλγόριθμο μια τέτοια είσοδος για την επίλυση κάποιου προβλήματος υπόσχεσης, τότε αυτός μπορεί να επιστρέψει οτιδήποτε, ή ακόμα και να τερματίσει.

Τυπικός ορισμός[Επεξεργασία | επεξεργασία κώδικα]

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

Παραδείγματα[Επεξεργασία | επεξεργασία κώδικα]

Πολλά φυσικά προβλήματα είναι στην πραγματικότητα προβλήματα υπόσχεσης. Για παράδειγμα, θεωρήστε το ακόλουθο πρόβλημα: «Δεδομένου ενός κατευθυνόμενου ακυκλικού γράφου, να αποφανθείτε αν ο γράφος αυτός διαθέτει μονοπάτι μήκους 10». Τα ναι στιγμιότυπα είναι κατευθυνόμενοι ακυκλικοί γράφοι με μονοπάτι μήκους 10, ενώ τα όχι στιγμιότυπα είναι κατευθυνόμενοι ακυκλικοί γράφοι που δε διαθέτουν κανένα μονοπάτι μήκους 10. Η υπόσχεση είναι το σύνολο των κατευθυνόμενων ακυκλικών γράφων. Σε αυτό το παράδειγμα η υπόσχεση μπορεί εύκολα να ελεγχθεί. Πιο συγκεκριμένα, είναι ιδιαίτερα εύκολο να ελέγξουμε αν κάποιος δοσμένος γράφος είναι κυκλικός. Παρ' όλα αυτά, θα μπορούσε να είναι αρκετά δύσκολο να ελέγξουμε την υποσχόμενη ιδιότητα. Για παράδειγμα, θεωρήστε το πρόβλημα: «Δεδομένου ενός Χαμιλτονιανός γράφος, να αποφανθείτε αν ο γράφος αυτός περιέχει κύκλο μήκους 4». Τώρα ο έλεγχος της υπόσχεσης αποτελεί ένα NP-hard πρόβλημα, αλλά το πρόβλημα υπόσχεσης είναι αρκετά εύκολο να επιλυθεί αφού ο έλεγχος ύπαρξης κύκλων μεγέθους 4 μπορεί να γίνει σε πολυωνυμικό χρόνο.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

Μελέτες[Επεξεργασία | επεξεργασία κώδικα]