Στη θεωρία της υπολογιστικής πολυπλοκότητας, μια μείωση πολυωνυμικού χρόνου είναι μια μέθοδος για την επίλυση ενός προβλήματος χρησιμοποιώντας ένα άλλο. Οι αναγωγές πολυωνύμου χρόνου χρησιμοποιούνται συχνά στη θεωρία πολυπλοκότητας για τον ορισμό τόσο των κατηγοριών πολυπλοκότητας όσο και των πλήρων προβλημάτων για αυτές τις κλάσεις. …
Τι θεωρείται πολυωνυμικός χρόνος;
Ένας αλγόριθμος λέγεται ότι είναι πολυωνυμικού χρόνου εάν ο χρόνος εκτέλεσης του είναι ανώτερος οριοθετημένος από μια πολυωνυμική έκφραση στο μέγεθος της εισόδου για τον αλγόριθμο, δηλαδή T(n)=O(nk) για κάποια θετική σταθερά k.
Πώς καταλαβαίνετε αν κάτι είναι πολυώνυμος χρόνος;
3 Απαντήσεις. Ένας αλγόριθμος είναι πολυωνυμικός (έχει πολυωνυμικό χρόνο εκτέλεσης) εάν για κάποιο k, C>0, ο χρόνος λειτουργίας του σε εισόδους μεγέθους n είναι το πολύ Cnk. Ισοδύναμα, ένας αλγόριθμος είναι πολυωνυμικός εάν για κάποιο k>0, ο χρόνος λειτουργίας του σε εισόδους μεγέθους n είναι O(nk).
Τι θα συμβεί εάν η μείωση επιτρέπεται σε εκθετικό χρόνο;
Εάν η μείωση επιτρέπεται εκθετικός χρόνος, τότε μπορεί να λύσει πλήρως το αρχικό πρόβλημα και να δημιουργήσει ένα ασήμαντο παράδειγμα του προβλήματος στόχου Αυτό σημαίνει ότι κάθε πρόβλημα στο NP μπορεί να αναχθεί σε κάθε άλλο πρόβλημα από τέτοιου είδους αναγωγές, επομένως κάθε πρόβλημα στο NP είναι NP-πλήρες για εκθετικές μειώσεις χρόνου.
Τι είναι ένας εκθετικός αλγόριθμος;
Ένας αλγόριθμος λέγεται ότι είναι εκθετικός χρόνος, εάν το T(n) είναι άνω όριο με 2poly( ) , όπου το πολυ(n) είναι κάποιο πολυώνυμο στο n. Πιο τυπικά, ένας αλγόριθμος είναι εκθετικός χρόνος εάν το T(n) οριοθετείται από O(2nk) για κάποια σταθερά k. Αναφορά:Wiki.
