Θεωρία πολυπλοκότητας: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ Ρομπότ: Προσθήκη: tr:Hesap karmaşıklığı kuramı |
|||
Γραμμή 10:
== Κλάσεις πολυπλοκότητας ==
Η θεωρία πολυπλοκότητας ταξινομέο τα προβλήματα σε κλάσεις(σύνολα) ισοδυναμίας που ορίζουν ότι τα προβλήματα στην ίδια κλάση έχουν την ίδια δυσκολία.Ιδιαιτέρου ενδιαφέροντος στο πλαίσιο αυτό ειναι οι κλάσεις P(Deterministic Polynomial Time) και NP(Non Deterministic Polynomial Time).Γενικά θα μπορούσαμε να πούμε ότι η κλάση P περιλαμβάνει τα περισσότερα προβλήματα της NP.Θα προχωρήσουμε σε πιο τυπικούς ορισμούς οι οποιοι επαλυθεύουν τη διαίσθηση ότι P⊆NP.Θα πρέπει να τονίσουμε ότι οι κλάσεις P και NP ορίζονται ως προς '''προβλήματα απόφασης''', δηλαδή προβλήματα στα οποία καλούμαστε να απαντήσουμε μια συγκεκριμένη ερώτηση με ΝΑΙ ή ΟΧΙ.
*'''Ορισμoί'''
**Η κλάση P περιλαμβάνει όλα εκείνα τα προβλήματα απόφασης, τα οποία επιλύονται από ένα ντετερμινιστικό αυτόματο σε πολυωνυμικό χρόνο.
**Η κλάση NP περιλαμβάνει όλα τα προβλήματα απόφασης που επιλύονται από ένα μη ντετερμινιστικό αυτόματο σε πολυωνυμικό χρόνο.
***Ένας ισοδύναμος ορισμός της κλάσης NP έχει ως εξής: Η κλάση NP περιλαμβάνει όλα τα προβλήματα απόφασης για τα οποία αν μας δοθεί ένα πιστοποιητικό της απάντησης ΝΑΙ, μπορούμε να επαληθεύσουμε σε πολυωνυμικο χρόνο ότι είναι σωστή.
== Το ζήτημα P=NP ==
| |||