From Wikipedia, the free encyclopedia
Στη θεωρητική πληροφορική, ένα υπολογιστικό πρόβλημα είναι ένα μαθηματικό αντικείμενο που αντιπροσωπεύει ένα σύνολο ερωτημάτων τα οποία ένας υπολογιστής είναι ικανός να λύσει. Για παράδειγμα, το πρόβλημα της παραγοντοποίησης:
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
είναι ένα υπολογιστικό πρόβλημα. Τα υπολογιστικά προβλήματα αποτελούν ένα από τα βασικά αντικείμενα μελέτης στη θεωρητική πληροφορική. Ο τομέας των αλγορίθμων ερευνά μεθόδους αποδοτικής επίλυσης υπολογιστικών προβλημάτων. Ο συμπληρωματικός κλάδος της υπολογιστικής πολυπλοκότητας επιχειρεί να εξηγήσει το λόγο που κάποια υπολογιστικά προβλήματα είναι δυσεπίλυτα για τους υπολογιστές.
Ένα υπολογιστικό πρόβλημα μπορεί να θεωρηθεί ως ένα άπειρο σύνολο στιγμιοτύπων, μαζί με μία λύση για κάθε στιγμιότυπο. Για παράδειγμα, στο πρόβλημα της παραγοντοποίησης που αναφέρθηκε παραπάνω, τα στιγμιότυπα είναι οι ακέραιοι n και οι λύσεις είναι οι πρώτοι αριθμοί p που περιγράφουν μη τετριμμένους πρώτους παράγοντες του κάθε n.
Κατά σύμβαση αναπαριστούμε τόσο τα στιγμιότυπα όσο και τις λύσεις με δυαδικές συμβολοσειρές (binary strings), δηλαδή συμβολοσειρές με στοιχεία {0, 1}*. Για παράδειγμα, οι αριθμοί μπορούν να παρασταθούν με δυαδικές συμβολοσειρές χρησιμοποιώντας τη δυαδική κωδικοποίηση.
Ένα πρόβλημα απόφασης είναι ένα υπολογιστικό πρόβλημα του οποίου κάθε στιγμιότυπο δέχεται ως λύση ένα ναι ή ένα όχι. Ένα παράδειγμα υπολογιστικού προβλήματος είναι ο έλεγχος πρώτου:
Κατά κανόνα, ένα πρόβλημα απόφασης αναπαρίσταται ως το σύνολο όλων των στιγμιοτύπων για τα οποία η απάντηση είναι ναι. Για παράδειγμα, ο έλεγχος πρώτου μπορεί να αναπαρασταθεί με το άπειρο σύνολο:
Σε ένα πρόβλημα αναζήτησης, οι απαντήσεις μπορεί να είναι τυχαίες συμβολοσειρές. Για παράδειγμα, η παραγοντοποίηση αποτελεί ένα πρόβλημα αναζήτησης όπου τα στιγμιότυπα είναι θετικοί ακέραιοι (σε αναπαράσταση συμβολοσειράς) και οι λύσεις είναι σύνολα ακεραίων (σε αναπαράσταση συμβολοσειράς).
Ένα πρόβλημα αναζήτησης αναπαρίσταται ως μια σχέση που αποτελείται από όλα τα ζεύγη στιγμιοτύπου-λύσης, και αποκαλείται σχέση αναζήτησης. Για παράδειγμα, η παραγοντοποίηση μπορεί να αναπαρασταθεί ως η σχέση:
η οποία αποτελείται από όλα τα ζεύγη αριθμών (n, p) όπου p ο μη τετριμμένος πρώτος παράγοντας του n.
Σε ένα πρόβλημα απαρίθμησης αναζητούμε το πλήθος των λύσεων που επιδέχεται ένα συγκεκριμένο πρόβλημα αναζήτησης. Για παράδειγμα, ένα πρόβλημα απαρίθμησης σχετικό με την παραγοντοποίηση είναι:
Ένα πρόβλημα απαρίθμησης μπορεί να αναπαρασταθεί με μια συνάρτηση f από {0, 1}* σε μη αρνητικούς ακεραίους. Για μια σχέση αναζήτησης R, το πρόβλημα απαρίθμησης που σχετίζεται με την R είναι η συνάρτηση:
Σε ένα πρόβλημα βελτιστοποίησης αναζητούμε τη «βέλτιστη δυνατή» λύση ανάμεσα στο σύνολο όλων των πιθανών λύσεων σε ένα πρόβλημα αναζήτησης. Παράδειγμα τέτοιου τύπου προβλήματος είναι το πρόβλημα του μέγιστου ανεξάρτητου συνόλου:
Τα προβλήματα βελτιστοποίησης μπορούν να αναπαρασταθούν μέσω των σχέσεων αναζήτησής τους.
Σε ένα πρόβλημα συνάρτησης αναμένουμε μια μοναδική έξοδο (κάποιας ολικής συνάρτησης) για κάθε είσοδο, αλλά η έξοδος είναι πιο περίπλοκη από αυτή ενός προβλήματος απόφασης, διότι δεν περιορίζεται μόνο σε ένα «ναι» ή ένα «όχι». Ένα από τα πιο διάσημα παραδείγματα αποτελεί το πρόβλημα του περιπλανώμενου πωλητή (traveling salesman problem, TSP):
Το πρόβλημα αυτό είναι NP-hard στη συνδυαστική βελτιστοποίηση και έχει ιδιαίτερα μεγάλη σημασία στην επιχειρησιακή έρευνα και τη θεωρητική πληροφορική.
Στη θεωρία υπολογιστικής πολυπλοκότητας συχνά υποννοείται ότι κάθε συμβολοσειρά στο {0, 1}* αναπαριστά ένα στιγμιότυπο του εκάστοτε υπολογιστικού προβλήματος. Παρ' όλα αυτά, μερικές φορές δεν αποτελούν όλες οι συμβολοσειρές στο {0, 1}* έγκυρα στιγμιότυπα και θα πρέπει να προσδιοριστεί ένα κατάλληλο υποσύνολο του {0, 1}* ως το σύνολο των «έγκυρων στιγμιοτύπων». Υπολογιστικά προβλήματα αυτού του είδους ονομάζονται προβλήματα υπόσχεσης.
Το ακόλουθο είναι ένα παράδειγμα προβλήματος υπόσχεσης:
Σε αυτό το παράδειγμα όλα τα έγκυρα στιγμιότυπα είναι εκείνα των οποίων τα μέγιστα ανεξάρτητα σύνολα έχουν μέγεθος το πολύ 5 ή τουλάχιστον 10.
Τα προβλήματα απόφασης συνήθως αναπαρίστανται ως ζεύγη ξένων υποσυνόλων (Lyes, Lno) του {0, 1}*. Τα έγκυρα στιγμιότυπα είναι αυτά στο Lyes ∪ Lno. Τα Lyes και Lno αναπαριστούν στιγμιότυπα των οποίων η λύση είναι αντίστοιχα ναι (yes) και όχι (no).
Τα προβήματα υπόσχεσης διαδραματίζουν ιδιαίτερα σημαντικό ρόλο σε διάφορες περιοχές της υπολογιστικής πολυπλοκότητας, συμπεριλαμβανομένων των hardness of approximation, property testing και interactive proof systems.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.