Πρόβλημα P=NP
From Wikipedia, the free encyclopedia
Το Πρόβλημα P vs NP είναι ένα σημαντικό ανοικτό πρόβλημα στην επιστήμη των υπολογιστών. Στην απλή διατύπωση του το ερώτημα που θέτει είναι, εάν κάθε πρόβλημα του οποίου η ύπαρξη λύσης μπορεί να επιβεβαιωθεί γρήγορα από έναν υπολογιστή μπορεί επίσης και να επιλυθεί γρήγορα από τον υπολογιστή.
Ουσιαστικά, αναφέρεται για πρώτη φορά σε μια επιστολή που γράφτηκε το 1956 από τον Κουρτ Γκέντελ στον Τζον φον Νόιμαν. Ο Γκέντελ ρώτησε αν ένα ορισμένο NP πλήρες πρόβλημα (το οποίο σημαίνει ότι μια οποιαδήποτε λύση μπορεί εύκολα να ελεγχθεί για το αν ικανοποιεί τις συνθήκες του προβλήματος) θα μπορούσε να λυθεί σε τετραγωνικό ή γραμμικό χρόνο.[2] Η ακριβής δήλωση του προβλήματος P vs NP εισήχθη το 1971 από τον Στήβεν Κουκ στη δημοσίευσή του «Η πολυπλοκότητα θεωρημάτων αποδεικτικών διαδικασιών»[3] και θεωρείται από πολλούς ως το πιο σημαντικό ανοικτό πρόβλημα στον τομέα αυτό.[4] Πρόκειται για ένα από τα επτά προβλήματα του βραβείου Μιλλέννιουμ (Millennium Prize) από το Ινστιτούτο Μαθηματικών Κλέι (Clay Mathematics Institute) με αμοιβή 1 εκατομμύριο δολάρια για την πρώτη σωστή λύση.
Ο όρος γρήγορα, που χρησιμοποιήθηκε παραπάνω, δηλώνει την ύπαρξη ενός αλγορίθμου για μια διαδικασία ή οποία τρέχει σε πολυωνυμικό χρόνο. Η γενική κλάση ερωτημάτων για το οποίο κάποιος αλγόριθμος δίνει την απάντηση σε πολυωνυμικό χρόνο ονομάζεται "κλάση P" ή απλούστερα "P". Για κάποια ερωτήματα δεν υπάρχει γνωστός τρόπος για την γρήγορη εύρεση απάντησης, αλλά αν κάποιος διαθέτει πληροφορίες που να αποδεικνύουν ποια είναι η απάντηση, είναι δυνατό να επιβεβαιώσει την απάντηση γρήγορα. Η κλάση των προβλημάτων που μπορούν να "επιβεβαιωθούν" σε πολυωνυμικό χρόνο ονομάζεται κλάση NP.
Μια περίπτωση αποτελεί το πρόβλημα αθροίσματος υποσυνόλου, ένα παράδειγμα προβλήματος που είναι εύκολο να επιβεβαιωθεί,του οποίου,όμως, η λύση μπορεί να είναι δύσκολο να υπολογιστεί. Δοθέντος ενός συνόλου ακεραίων, υπάρχει κάποιο μη κενό υποσύνολο που να αθροίζει στο 0; Για παράδειγμα, υπάρχει υποσύνολο του συνόλου {−2, −3, 15, 14, 7, −10} που να αθροίζει στο 0; Η απάντηση "ναι, επειδή το υποσύνολο {−2, −3, −10, 15} αθροίζει στο 0" μπορεί γρήγορα να επιβεβαιωθεί με τρεις προσθέσεις. Ωστόσο,δεν υπάρχει γνωστός αλγόριθμος που να βρίσκει τέτοια υποσύνολα σε πολυωνυμικό χρόνο (υπάρχει ένας, παρόλα αυτά, σε εκθετικό χρόνο, που αποτελείται απο 2n-n-1 προσπάθειες), αλλά τέτοιος αλγόριθμος υπάρχει αν P = NP. Συνεπώς το πρόβλημα είναι NP (γρήγορα ελέγξιμο) αλλά όχι απαραίτητα P (γρήγορα επιλύσιμο).
Μια απάντηση στο ερώτημα P = NP θα καθόριζε αν προβλήματα που μπορούν να επιβεβαιωθούν σε πολυωνυμικό χρόνο, όπως το πρόβλημα αθροίσματος υποσυνόλου, μπορούν και να λυθούν σε πολυωνυμικό χρόνο. Αν αποδειχθεί ότι P ≠ NP, θα σημαίνει ότι υπάρχει προβλήματα στην NP (όπως τα NP-πλήρη προβλήματα) τα οποία είναι δυσκολότερο να υπολογιστούν από το να επιβεβαιωθούν. Δεν θα μπορούν να υπολογιστούν σε πολυωνυμικό χρόνο αλλά η απάντηση μπορεί να επιβεβαιωθεί σε πολυωνυμικό χρόνο.
Εκτός από το να είναι ένα σημαντικό πρόβλημα στην Θεωρία Υπολογισμού, μια απόδειξη του θα εχει σημαντικές επιρροές στα Μαθηματικά, την Κρυπτογραφία, την μελέτη Αλγορίθμων, την Τεχνητή Νοημοσύνη, την Θεωρία Παιγνίων, την Φιλοσοφία, τα Οικονομικά και πολλά άλλα πεδία.