Κατανόηση της πολυπλοκότητας NP: Ορισμός και Παραδείγματα

Το NP σημαίνει "Μη ντετερμινιστικός πολυωνυμικός χρόνος". Είναι μια κατηγορία πολυπλοκότητας που αναφέρεται στο χρόνο που απαιτείται για την επίλυση ενός προβλήματος. Στο NP, ο χρόνος εκτέλεσης ενός αλγορίθμου μπορεί να είναι πολυωνυμικός στο μέγεθος της εισόδου, αλλά μπορεί επίσης να είναι μη ντετερμινιστικός, πράγμα που σημαίνει ότι ο χρόνος εκτέλεσης μπορεί να ποικίλλει ανάλογα με τη συγκεκριμένη λύση που επιλέγεται από τον αλγόριθμο.

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

Η τάξη πολυπλοκότητας NP είναι σημαντική επειδή περιλαμβάνει πολλά προβλήματα που είναι δύσκολο να λυθούν σε πολυώνυμα χρόνο, αλλά μπορεί να επαληθευτεί γρήγορα από μια ντετερμινιστική μηχανή. Αυτό σημαίνει ότι παρόλο που ένας αλγόριθμος μπορεί να μην είναι σε θέση να βρει μια λύση σε πολυωνυμικό χρόνο, μπορεί να είναι χρήσιμος εάν μπορεί να επαληθεύσει γρήγορα μια προτεινόμενη λύση.