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

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

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

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

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

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

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

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

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

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

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

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

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

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

enet.gr

12-08-2010