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

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

Τυπικός ορισμός

Ένα πρόβλημα απόφασης μπορεί να συνδέεται με μια γλώσσα $L\subseteq \{0,1\}^{*}$, όπου το πρόβλημα είναι η αποδοχή όλων των εισόδων που ανήκουν στην $L$ και η απόρριψη όσων δεν ανήκουν στην $L$. Για ένα πρόβλημα υπόσχεσης υπάρχουν δύο γλώσσες, η $L_{\text{YES}}$ και η $L_{\text{NO}}$, οι οποίες και πρέπει να είναι ξένες μεταξύ τους, δηλαδή πρέπει $L_{\text{YES}}\cap L_{\text{NO}}=\varnothing$, έτσι ώστε όλες οι είσοδοι που ανήκουν στην $L_{\text{YES}}$ να γίνονται αποδεκτές και όλες οι είσοδοι που ανήκουν στην $L_{\text{NO}}$ να απορρίπτονται. Το σύνολο $L_{\text{YES}}\cup L_{\text{NO}}$καλείται υπόσχεση. Αν η είσοδος δεν ανήκει στην υπόσχεση, τότε δεν υπάρχουν απαιτήσεις για την έξοδο. Αν η υπόσχεση ισούται με $\{0,1\}^{*}$, τότε αυτό είναι επίσης ένα πρόβλημα απόφασης και η υπόσχεση λέγεται ότι είναι ασήμαντη.

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

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

Δείτε επίσης

• Υπολογιστικό πρόβλημα
  
• Πρόβλημα απόφασης
  
• Πρόβλημα βελτιστοποίησης
  
• Πρόβλημα αναζήτησης
  
• Πρόβλημα απαρίθμησης
  
• Πρόβλημα συνάρτησης
  

Αναφορές

Μελέτες

• Goldreich, Oded (2006). On Promise Problems (a survey). LNCS. 3895. σελίδες 254–290. 
• Sahai, A.; Vadhan, S.P. (1997). «A complete promise problem for statistical zero-knowledge». FOCS 1997, pp. 448–457. doi:10.1109/SFCS.1997.646133. CiteSeerX: 10.1.1.34.6920. 
• Even, Shimon; Selman, Alan L.; Yacobi, Yacov (1984). «The complexity of promise problems with applications to public-key cryptography». Information and Control 61 (2): 159–173. doi:10.1016/S0019-9958(84)80056-X.