Πίνακας περιεχομένων:
- Ορισμός - Τι σημαίνει μη-προσδιοριστικός χρόνος πολυωνύμου (NP);
- Η Techopedia εξηγεί τη μη καθοριστική πολυωνυμική ώρα (NP)
Ορισμός - Τι σημαίνει μη-προσδιοριστικός χρόνος πολυωνύμου (NP);
Ο μη καθοριστικός πολυωνυμικός χρόνος (NP) είναι στην πραγματικότητα ένας δείκτης που χρησιμοποιείται για την επισήμανση ενός συνόλου προβλημάτων και ορίων της ικανότητας ορισμένων τύπων υπολογιστών. Το NP αναφέρεται στο σύνολο των προβλημάτων που μπορούν να λυθούν σε πολυωνυμικό χρόνο από μη ντετερμινιστική μηχανή Turing.
Η Techopedia εξηγεί τη μη καθοριστική πολυωνυμική ώρα (NP)
Ο μη ντετερμινιστικός πολυωνυμικός χρόνος βασίζεται στη φράση "χρόνος πολυώνυμου", ο οποίος αναφέρεται στο αν ένας αλγόριθμος μπορεί να εκτελέσει εντός ορισμένων ορίων σχετικών με την ταχύτητα. Ο πολυωνυμικός χρόνος αναδείχθηκε ως ένας τρόπος για να μιλήσουμε για τη σκοπιμότητα της εργασίας και της ανάπτυξης του αλγορίθμου.
Εάν ένα πρόβλημα είναι σε μη καθοριστικό πολυωνυμικό χρόνο, η μη ντετερμινιστική μηχανή Turing μπορεί αρχικά να μαντέψει στη λύση και στη συνέχεια να εκτελέσει έναν επαληθεύσιμο αλγόριθμο ο οποίος θα επιβεβαιώσει εάν η εικασία ήταν σωστή ή όχι. Ο ορισμός που βασίζεται στον επαληθευτή ή τα προγράμματα ορισμού μηχανών θα ελέγξει ουσιαστικά τις αρχικές επιλογές της μη ντετερμινιστικής μηχανής Turing για την επαλήθευση των αποτελεσμάτων.
Όλα αυτά είναι εξαιρετικά θεωρητική υπολογιστική δομή. Ενώ η μηχανική μάθηση έχει κάνει επιρροές πέρα από τα ντετερμινιστικά συστήματα, η ιδέα της επαλήθευσης των μη-ντετερμινιστικών επιλογών είναι ακόμα στα σπάργανα. Ψάξτε για περισσότερη ανάπτυξη σε αυτό το σύνορο της πληροφορικής.
