Υπολογιστικό πρόβλημα
 |
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Στη θεωρητική πληροφορική, ένα υπολογιστικό πρόβλημα είναι ένα μαθηματικό αντικείμενο που αντιπροσωπεύει ένα σύνολο ερωτημάτων τα οποία ένας υπολογιστής είναι ικανός να λύσει. Για παράδειγμα, το πρόβλημα της παραγοντοποίησης:
- «Δοθέντος ενός θετικού ακεραίου n, να βρεθεί ένας μη τετριμμένος πρώτος παράγοντας του n.»
είναι ένα υπολογιστικό πρόβλημα. Τα υπολογιστικά προβλήματα αποτελούν ένα από τα βασικά αντικείμενα μελέτης στη θεωρητική πληροφορική. Ο τομέας των αλγορίθμων ερευνά μεθόδους αποδοτικής επίλυσης υπολογιστικών προβλημάτων. Ο συμπληρωματικός κλάδος της υπολογιστικής πολυπλοκότητας επιχειρεί να εξηγήσει το λόγο που κάποια υπολογιστικά προβλήματα είναι δυσεπίλυτα για τους υπολογιστές.
Ένα υπολογιστικό πρόβλημα μπορεί να θεωρηθεί ως ένα άπειρο σύνολο στιγμιοτύπων, μαζί με μία λύση για κάθε στιγμιότυπο. Για παράδειγμα, στο πρόβλημα της παραγοντοποίησης που αναφέρθηκε παραπάνω, τα στιγμιότυπα είναι οι ακέραιοι n και οι λύσεις είναι οι πρώτοι αριθμοί p που περιγράφουν μη τετριμμένους πρώτους παράγοντες του κάθε n.
Κατά σύμβαση αναπαριστούμε τόσο τα στιγμιότυπα όσο και τις λύσεις με δυαδικές συμβολοσειρές (binary strings), δηλαδή συμβολοσειρές με στοιχεία {0, 1}*. Για παράδειγμα, οι αριθμοί μπορούν να παρασταθούν με δυαδικές συμβολοσειρές χρησιμοποιώντας τη δυαδική κωδικοποίηση.
Είδη υπολογιστικών προβλημάτων
[Επεξεργασία | επεξεργασία κώδικα]Ένα πρόβλημα απόφασης είναι ένα υπολογιστικό πρόβλημα του οποίου κάθε στιγμιότυπο δέχεται ως λύση ένα ναι ή ένα όχι. Ένα παράδειγμα υπολογιστικού προβλήματος είναι ο έλεγχος πρώτου:
- «Δοθέντος ενός θετικού ακεραίου n, να αποφασιστεί αν ο n είναι πρώτος.»
Κατά κανόνα, ένα πρόβλημα απόφασης αναπαρίσταται ως το σύνολο όλων των στιγμιοτύπων για τα οποία η απάντηση είναι ναι. Για παράδειγμα, ο έλεγχος πρώτου μπορεί να αναπαρασταθεί με το άπειρο σύνολο:
- L = {2, 3, 5, 7, 11, ...}
Σε ένα πρόβλημα αναζήτησης, οι απαντήσεις μπορεί να είναι τυχαίες συμβολοσειρές. Για παράδειγμα, η παραγοντοποίηση αποτελεί ένα πρόβλημα αναζήτησης όπου τα στιγμιότυπα είναι θετικοί ακέραιοι (σε αναπαράσταση συμβολοσειράς) και οι λύσεις είναι σύνολα ακεραίων (σε αναπαράσταση συμβολοσειράς).
Ένα πρόβλημα αναζήτησης αναπαρίσταται ως μια σχέση που αποτελείται από όλα τα ζεύγη στιγμιοτύπου-λύσης, και αποκαλείται σχέση αναζήτησης. Για παράδειγμα, η παραγοντοποίηση μπορεί να αναπαρασταθεί ως η σχέση:
- R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)...}
η οποία αποτελείται από όλα τα ζεύγη αριθμών (n, p) όπου p ο μη τετριμμένος πρώτος παράγοντας του n.
Σε ένα πρόβλημα απαρίθμησης αναζητούμε το πλήθος των λύσεων που επιδέχεται ένα συγκεκριμένο πρόβλημα αναζήτησης. Για παράδειγμα, ένα πρόβλημα απαρίθμησης σχετικό με την παραγοντοποίηση είναι:
- «Δοθέντος ενός θετικού ακεραίου n, να υπολογιστεί το πλήθος των μη τετριμμένων πρώτων παραγόντων του n.»
Ένα πρόβλημα απαρίθμησης μπορεί να αναπαρασταθεί με μια συνάρτηση f από {0, 1}* σε μη αρνητικούς ακεραίους. Για μια σχέση αναζήτησης R, το πρόβλημα απαρίθμησης που σχετίζεται με την R είναι η συνάρτηση:
- fR(x) = |{y: R(x, y) }|.
Σε ένα πρόβλημα βελτιστοποίησης αναζητούμε τη «βέλτιστη δυνατή» λύση ανάμεσα στο σύνολο όλων των πιθανών λύσεων σε ένα πρόβλημα αναζήτησης. Παράδειγμα τέτοιου τύπου προβλήματος είναι το πρόβλημα του μέγιστου ανεξάρτητου συνόλου:
- «Δοθέντος ενός γράφου G, να βρεθεί ένα ανεξάρτητο σύνολο του G με το μέγιστο δυνατό μέγεθος.»
Τα προβλήματα βελτιστοποίησης μπορούν να αναπαρασταθούν μέσω των σχέσεων αναζήτησής τους.
Σε ένα πρόβλημα συνάρτησης αναμένουμε μια μοναδική έξοδο (κάποιας ολικής συνάρτησης) για κάθε είσοδο, αλλά η έξοδος είναι πιο περίπλοκη από αυτή ενός προβλήματος απόφασης, διότι δεν περιορίζεται μόνο σε ένα «ναι» ή ένα «όχι». Ένα από τα πιο διάσημα παραδείγματα αποτελεί το πρόβλημα του περιπλανώμενου πωλητή (traveling salesman problem, TSP):
- «Δοθείσης μιας λίστας πόλεων και των αποστάσεων μεταξύ τους, να βρεθεί ο συντομότερος δρόμος που περνά από κάθε πόλη ακριβώς μία φορά κι επιστρέφει στην πόλη εκκίνησης.»
Το πρόβλημα αυτό είναι NP-hard στη συνδυαστική βελτιστοποίηση και έχει ιδιαίτερα μεγάλη σημασία στην επιχειρησιακή έρευνα και τη θεωρητική πληροφορική.
Προβλήματα υπόσχεσης
[Επεξεργασία | επεξεργασία κώδικα]Στη θεωρία υπολογιστικής πολυπλοκότητας συχνά υποννοείται ότι κάθε συμβολοσειρά στο {0, 1}* αναπαριστά ένα στιγμιότυπο του εκάστοτε υπολογιστικού προβλήματος. Παρ' όλα αυτά, μερικές φορές δεν αποτελούν όλες οι συμβολοσειρές στο {0, 1}* έγκυρα στιγμιότυπα και θα πρέπει να προσδιοριστεί ένα κατάλληλο υποσύνολο του {0, 1}* ως το σύνολο των «έγκυρων στιγμιοτύπων». Υπολογιστικά προβλήματα αυτού του είδους ονομάζονται προβλήματα υπόσχεσης.
Το ακόλουθο είναι ένα παράδειγμα προβλήματος υπόσχεσης:
- «Δοθέντος ενός γράφου G, να προσδιοριστεί αν κάθε ανεξάρτητο σύνολο του G έχει μέγεθος το πολύ 5, ή αν το G διαθέτει κάποιο ανεξάρτητο σύνολο με μέγεθος τουλάχιστον 10.»
Σε αυτό το παράδειγμα όλα τα έγκυρα στιγμιότυπα είναι εκείνα των οποίων τα μέγιστα ανεξάρτητα σύνολα έχουν μέγεθος το πολύ 5 ή τουλάχιστον 10.
Τα προβλήματα απόφασης συνήθως αναπαρίστανται ως ζεύγη ξένων υποσυνόλων (Lyes, Lno) του {0, 1}*. Τα έγκυρα στιγμιότυπα είναι αυτά στο Lyes ∪ Lno. Τα Lyes και Lno αναπαριστούν στιγμιότυπα των οποίων η λύση είναι αντίστοιχα ναι (yes) και όχι (no).
Τα προβήματα υπόσχεσης διαδραματίζουν ιδιαίτερα σημαντικό ρόλο σε διάφορες περιοχές της υπολογιστικής πολυπλοκότητας, συμπεριλαμβανομένων των hardness of approximation, property testing και interactive proof systems.
Παραπομπές
[Επεξεργασία | επεξεργασία κώδικα]- 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:.
- Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press, ISBN 978-0-521-88473-0.
- Goldreich, Oded; Wigderson, Avi (2008), «IV.20 Computational Complexity», στο: Gowers, Timothy; Barrow-Green, June; Leader, Imre, επιμ., The Princeton Companion to Mathematics, Princeton University Press, σελ. 575–604, ISBN 978-0-691-11880-2.