Ρ ≠ ΝΡ: Το πιο «σέξι» πρόβλημα στην επιστήμη των υπολογιστών

14 Αυγουστου 2010
Posted in Επικαιρότητα

Το διασημότερο, μεγαλύτερο και θεωρούμενο πιο «σέξι» (όπως χαρακτηρίστηκε από το έγκυρο επιστημονικό περιοδικό Nature) πρόβλημα στην ιστορία της επιστήμης των υπολογιστών φαίνεται πως λύθηκε από έναν ινδικής καταγωγής μαθηματικό της Hewlett-Packard, ο οποίος τώρα διεκδικεί το βραβείο του 1 εκατ. δολαρίων που είχε οριστεί από το Μαθηματικό Ινστιτούτο Clay για όποιον κατάφερνε να το λύσει πρώτος.

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

Ο Βινέι Ντεολαλικάρ, που εργάζεται στο ερευνητικό Εργαστήριο της ΗΡ στο Πάλο Άλτο της Καλιφόρνιας, δημοσίευσε ένα πρώτο αντίγραφο περίπου 100 σελίδων της εργασίας του (PDF) με το λιτό τίτλο «Ρ ≠ ΝΡ» (δηλαδή το Ρ δεν ισούται με το ΝΡ).

Αμέσως έγινε χαμός στον κύκλο των ειδικών των υπολογιστών και των μαθηματικών, καθώς για τους μυημένους ανοίγει πιθανώς ο δρόμος για σημαντικές μελλοντικές επιστημονικές ανακαλύψεις, ενώ διακυβεύεται η ασφάλεια των υπολογιστικών κρυπτογραφικών συστημάτων, που χρησιμοποιούνται από τα e-mail μέχρι την ηλεκτρονική τραπεζική.

Το συγκεκριμένο πρόβλημα, που απασχολεί τους ερευνητές από τη δεκαετία του ΄70, αποτελεί ένα από τα επτά μεγάλα άλυτα μαθηματικά προβλήματα για την επίλυση των οποίων το Ινστιτούτο Clay έχει εξαγγείλει επτά ισάριθμα «Βραβεία της Χιλιετίας» (Millennium Prizes) αξίας 1 εκατ. δολαρίων το καθένα.

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

Μερικές εργασίες ολοκληρώνονται με μια λογική ταχύτητα και τότε ανήκουν στην κατηγορία Ρ. Αν η απάντηση σε μια τέτοια εργασία (π.χ. την παραγοντοποίηση, δηλαδή την ανάλυση σε παράγοντες ενός αριθμού) μπορεί να ελεγχθεί γρήγορα, τότε η εργασία ανήκει στην κατηγορία ΝΡ.

Αν συνεπώς ισχύει η ισότητα Ρ=ΝΡ, τότε κάθε υπολογιστικό πρόβλημα που μπορεί να ελεγχθεί γρήγορα, μπορεί επίσης να εκτελεστεί γρήγορα. Αυτό θα είχε μεγάλες συνέπειες για την ασφάλεια του διαδικτύου και των υπολογιστών, καθώς η δυσκολία παραγοντοποίησης των πολύ μεγάλων αριθμών είναι το βασικό μέσο χάρη στο οποίο τα διακινούμενα δεδομένα (data) παραμένουν ασφαλή από τους χάκερ.

Επίσης αν ίσχυε η ισότητα, θα ήμασταν σίγουροι ότι υπάρχει μια λύση και στα πιο πολύπλοκα προβλήματα υπολογισμού.

Όμως αν ο Ντεολαλικάρ έχει δίκιο και η ισότητα Ρ=ΝΡ δεν ισχύει, τότε τα πράγματα αλλάζουν και, μεταξύ άλλων, η κρυπτογράφηση δεδομένων κινδυνεύει, ενώ επιπλέον τίθενται σοβαροί περιορισμοί στο τι μπορεί να πετύχει ένας υπολογιστής, σύμφωνα με το New Scientist. Οι ειδικοί της θεωρίας πολυπλοκότητας έχουν δεχτεί ήδη ευνοϊκά την μαθηματική λύση του Ινδο-αμερικανού, αλλά αναμένουν τη δημοσίευση της τελικής μορφής της εργασίας του για να αποφανθούν οριστικά.

Δεν είναι πάντως η πρώτη φορά που κάποιος ισχυρίζεται ότι έλυσε το πρόβλημα και μερικοί (αντίζηλοι) ερευνητές δεν έχουν πειστεί καθόλου ότι ο Ντεολαλικάρ το έλυσε πράγματι αυτή τη φορά.

Ο ειδικός των υπολογιστών Σκοτ Άρονσον (επιστήμονας που ασχολείται αποκλειστικά με το συγκεκριμένο θέμα) του πανεπιστημίου ΜΙΤ δήλωσε ότι θα βάλει από την τσέπη του άλλα 200.000 δολάρια, αν τελικά το βραβείο του 1 εκατ. δολ. απονεμηθεί στον Ντεολαλικάρ, ενώ δήλωσε πρόθυμος να στοιχηματίσει ακόμα και το σπίτι του ότι δεν πρόκειται για τη σωστή λύση.

Ήδη, σε συνεργασία με άλλους, βάλθηκε να βρει τα λάθη στην απόδειξη του Ινδού. Εδώ που τα λέμε, για 1 εκατ. δολάρια αξίζει κάθε προσπάθεια …

Λύθηκε το P vs NP πρόβλημα;

Πριν αρχίσει ο γενικός ενθουσιασμός και τα wow, οφείλουμε να πούμε ότι θα χρειαστεί πολύ έλεγχος μέχρι να εξακριβωθεί η αλήθεια ή όχι της απόδειξης. Επειδή ο ελληνικός τύπος δεν είναι και ο καλύτερος δυνατός για προβλήματα μαθηματικών, ας πούμε αρχικά ότι τα P και ΝP μπορείτε να τα σκέφτεστε σαν σύνολα προβλημάτων αν θέλετε. Το P έχει όλα εκείνα τα προβλήματα που μπορούμε να λύσουμε αποτελεσματικά με κάποια ακολουθία βημάτων, για παράδειγμα να βρούμε το μέγιστο από 10 αριθμούς. Το NP περιέχει όλα εκείνα τα προβλήματα τα οποία δεν μπορούμε να λύσουμε σε πολύ καλό χρόνο γιατί οι καλύτεροι αλγόριθμοι που έχουμε λύνουν αυτά τα προβλήματα ερευνώντας όλες τις περιπτώσεις μέχρι να φτάσουν στη σωστή. Παρόλαυτα αν με κάποιον μαγικό τρόπο έχουμε μια λύση ενός NP προβλήματος, τότε μπορούμε εύκολα να δούμε αν είναι όντως λύση του. Τα P προβλήματα δηλαδή είναι "easy to solve" ενώ τα NP "easy to check" κατά κάποιο τρόπο.  

Όποτε τι τρέχει με την απόδειξη; Είναι η σωστή;

Δεν πέρασαν μέρες αφού ανακοινώθηκε και ήδη κάποιοι αρκετά γνωστοί ιστολόγοι στον χώρο τον μαθηματικών (οι περισσότεροι είναι καθηγητές σε πανεπιστήμια) βρήκαν τρύπες στη διάσημη απόδειξη των εκατό σελίδων, τις οποίες θα πρέπει τώρα ο Vinay Deolalikar, ερευνητής στα HPlabs, να διορθώσει, εφόσον αυτό γίνεται.

Σε άλλα μαθηματικά blogs, υπάρχουν ανακοινώσεις σχετικά με νέα λάθη, που είναι μεν φυσιολογικό να υπάρχουν σε μια τόσο πρόσφατη εργασία αλλά δεν ξέρουμε αν είναι και θεραπεύσιμα! Μπορούμε να είμαστε αισιόδοξοι (αν και το αποτέλεσμα προσωπικά δεν μου αρέσει καθόλου) αλλά δεν μπορούμε να ενθουσιαστούμε και πάρα πολύ.

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

Η απόδειξη ότι P ≠ NP σημαίνει ότι δεν υπάρχει και δεν θα υπάρξει ικανοποιητικός αλγόριθμος που να βρίσκει γρήγορα αυτούς τους αριθμούς (τους πρώτους που αναφέραμε). Οπότε πως ακριβώς απειλούνται οι διαδικτυακές επικοινωνίες;

11/08/2010 - enet.gr / mathcom.gr