Our website is made possible by displaying online advertisements to our visitors.
Please consider supporting us by disabling your ad blocker.
NP-completeness
Στη θεωρία της υπολογιστικής πολυπλοκότητας, ένα πρόβλημα είναι NP-complete όταν:
- Είναι ένα πρόβλημα για το οποίο η ορθότητα κάθε λύσης μπορεί να επαληθευτεί γρήγορα (δηλαδή, σε πολυωνυμικό χρόνο ) και ένας αλγόριθμος αναζήτησης ωμής βίας (brute force) μπορεί να βρει μια λύση δοκιμάζοντας όλες τις πιθανές λύσεις.
- Το πρόβλημα μπορεί να χρησιμοποιηθεί για την προσομοίωση κάθε άλλου προβλήματος για το οποίο μπορούμε να επαληθεύσουμε γρήγορα ότι μια λύση είναι σωστή. Υπό αυτή την έννοια, τα NP-complete προβλήματα είναι τα δυσκολότερα προβλήματα στα οποία μπορούν να επαληθευτούν γρήγορα οι πιθανές λύσεις τους. Εάν μπορούσαμε να βρούμε γρήγορα λύσεις για κάποιο NP-complete πρόβλημα, θα μπορούσαμε να βρούμε γρήγορα τις λύσεις κάθε άλλου προβλήματος στο οποίο μια δεδομένη λύση μπορεί εύκολα να επαληθευτεί.
Το όνομα "NP-complete" είναι σύντομο για το "πλήρες μη ντετερμινιστικό πρόβλημα πολυωνυμικού χρόνου" (non-diterministic polynomial time problem). Σε αυτή την διατύπωση, το "μη ντετερμινιστικό" αναφέρεται σε μη ντετερμινιστικές μηχανές Turing, έναν τρόπο μαθηματικής επισημοποίησης της ιδέας ενός αλγορίθμου αναζήτησης ωμής βίας (brute force). Ο πολυωνυμικός χρόνος αναφέρεται σε ένα χρονικό διάστημα που θεωρείται "γρήγορο" για έναν ντετερμινιστικό αλγόριθμο να ελέγξει μια μεμονωμένη λύση ή για μια μη ντετερμινιστική μηχανή Turing για να εκτελέσει ολόκληρη την αναζήτηση. Το " Complete " (πλήρες) αναφέρεται στην ιδιότητα της δυνατότητας προσομοίωσης όλων των προβλημάτων που ανήκουν στην ίδια κατηγορία πολυπλοκότητας .
Πιο συγκεκριμένα, κάθε είσοδος στο πρόβλημα θα πρέπει να συσχετίζεται με ένα σύνολο λύσεων πολυωνυμικού μήκους, των οποίων η εγκυρότητα μπορεί να ελεγχθεί γρήγορα (σε πολυωνυμικό χρόνο ), [2] έτσι ώστε η έξοδος για οποιαδήποτε είσοδο είναι "ναι" εάν το σύνολο λύσεων δεν είναι κενό και "όχι" αν είναι κενό. Η κατηγορία πολυπλοκότητας των προβλημάτων αυτής της μορφής ονομάζεται NP, συντομογραφία του «μη ντετερμινιστικού πολυωνυμικού χρόνου». Ένα πρόβλημα λέγεται ότι είναι NP-σκληρό (np-hard) εάν μπορεί να μετατραπούν σε πολυωνυμικό χρόνο σε NP, παρόλο που μπορεί να μην είναι την κλάση NP αρχικά. Αντίθετα, ένα πρόβλημα είναι NP-πλήρες εάν είναι ταυτόχρονα στην κλάση NP και NP-hard. Τα προβλήματα NP-complete αντιπροσωπεύουν τα δυσκολότερα προβλήματα στο NP. Εάν κάποιο πρόβλημα NP-complete έχει αλγόριθμο πολυωνυμικού χρόνου, όλα τα προβλήματα στο NP έχουν. Το σύνολο των προβλημάτων NP-complete υποδηλώνεται συχνά με NP-C ή NPC .
Ενώ μια μέθοδος για τον υπολογισμό των λύσεων σε προβλήματα NP-πλήρης παραμένει γρήγορα άγνωστη, οι επιστήμονες υπολογιστών και οι προγραμματιστές εξακολουθούν να αντιμετωπίζουν συχνά προβλήματα NP-complete. Τα προβλήματα NP-πλήρης αντιμετωπίζονται συχνά χρησιμοποιώντας ευρετικές μεθόδους και αλγόριθμους προσέγγισης .
- ↑ For example, simply assigning true to each variable renders the 18th conjunct (and hence the complete formula) false.
- ↑ Cobham, Alan (1965). «The intrinsic computational difficulty of functions». Proc. Logic, Methodology, and Philosophy of Science II. North Holland.
Previous Page Next Page
