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-πλήρης αντιμετωπίζονται συχνά χρησιμοποιώντας ευρετικές μεθόδους και αλγόριθμους προσέγγισης .

Επίσημος ορισμός Επεξεργασία

Πρόβλημα απόφασης $\scriptstyle C$ είναι NP-complete εάν:

$\scriptstyle C$ είναι στην κλάση NP, και
Κάθε πρόβλημα στην κλάση NP μπορεί να αναχθεί σε $\scriptstyle C$ σε πολυωνυμικό χρόνο. ^[3]

$\scriptstyle C$ μπορεί να αποδειχθεί ότι είναι στην κλάση NP αποδεικνύοντας ότι μια υποψήφια λύση για $\scriptstyle C$ μπορεί να επαληθευτεί σε πολυωνυμικό χρόνο.

Σημειώστε ότι ένα πρόβλημα που ικανοποιεί τη συνθήκη 2 λέγεται ότι είναι NP-hard, είτε ικανοποιεί είτε όχι τη συνθήκη 1. ^[4]

Μια συνέπεια αυτού του ορισμού είναι ότι εάν είχαμε έναν πολυωνυμικό αλγόριθμο χρόνου (σε ένα UTM, ή σε οποιαδήποτε άλλη αφηρημένη μηχανή ισοδύναμη με Turing ) για $\scriptstyle C$ , θα μπορούσαμε να λύσουμε όλα τα προβλήματα στο NP σε πολυωνυμικό χρόνο.

Ονομασία Επεξεργασία

Σύμφωνα με τον Donald Knuth, το όνομα "NP-complete" έγινε δημοφιλές από τους Alfred Aho, John Hopcroft και Jeffrey Ullman στο διάσημο εγχειρίδιο τους "The Design and Analysis of Computer Algorithms". Αναφέρει ότι εισήγαγαν την αλλαγή στις αποδείξεις για το βιβλίο (από "πολυωνυμικό-πλήρες"), σύμφωνα με τα αποτελέσματα μιας δημοσκόπησης που είχε διεξαγάγει στην κοινότητα της θεωρητικής επιστήμης των υπολογιστών . ^[5] Άλλες προτάσεις που έγιναν στη δημοσκόπηση ^[6] περιελάμβαναν το « Herculean », « τρομερό », το «σκληρό» του Steiglitz προς τιμήν του Cook και το ακρωνύμιο «PET» του Shen Lin, το οποίο σήμαινε «πιθανώς εκθετικός χρόνος», αλλά ανάλογα με ποιον τρόπο προχώρησε το πρόβλημα P έναντι NP, θα μπορούσε να σημαίνει " provably εκθετικό χρόνο" ή "προηγουμένως εκθετικό χρόνο".

Παραπομπές Επεξεργασία

↑ For example, simply assigning true to each variable renders the 18th conjunct ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ (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.
↑ J. van Leeuwen (1998). Handbook of Theoretical Computer Science. Elsevier. σελ. 84. ISBN 978-0-262-72014-4.
↑ J. van Leeuwen (1998). Handbook of Theoretical Computer Science. Elsevier. σελ. 80. ISBN 978-0-262-72014-4.
↑ Don Knuth, Tracy Larrabee, and Paul M. Roberts, Mathematical Writing Σφάλμα στο πρότυπο webarchive: Ελέγξτε την τιμή |url=. Empty. § 25, MAA Notes No. 14, MAA, 1989 (also Stanford Technical Report, 1987).
↑ Knuth, D. F. (1974). «A terminological proposal». SIGACT News 6 (1): 12–18. doi:10.1145/1811129.1811130.

[1] For example, simply assigning true to each variable renders the 18th conjunct ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ (and hence the complete formula) false.

[2] Cobham, Alan (1965). «The intrinsic computational difficulty of functions». Proc. Logic, Methodology, and Philosophy of Science II. North Holland.

[3] J. van Leeuwen (1998). Handbook of Theoretical Computer Science. Elsevier. σελ. 84. ISBN 978-0-262-72014-4.

[4] J. van Leeuwen (1998). Handbook of Theoretical Computer Science. Elsevier. σελ. 80. ISBN 978-0-262-72014-4.

[5] Don Knuth, Tracy Larrabee, and Paul M. Roberts, Mathematical Writing Σφάλμα στο πρότυπο webarchive: Ελέγξτε την τιμή |url=. Empty. § 25, MAA Notes No. 14, MAA, 1989 (also Stanford Technical Report, 1987).

[6] Knuth, D. F. (1974). «A terminological proposal». SIGACT News 6 (1): 12–18. doi:10.1145/1811129.1811130.

[1]

[2]

[3]

[4]

[5]

[6]