Υπάρχει μια ιδανική διάταξη συνδαιτυμόνων;
Υποθέστε ότι πρέπει να κάνετε μια λίστα για το πώς θα καθί-σουν οι καλεσμένοι σε ένα μεγάλο εορταστικό δείπνο. Έχετε 400 άτομα στον κατάλογο σας, αλλά πρέπει να επιλέξετε μόνο 100 από αυτούς, καθώς δεν υπάρχει χώρος για περισσότερους. Επίσης, έχετε άλλη μια λίστα από ζεύγη αυτών των ανθρώπων, κι έτσι κανένα από αυτά τα ζευγάρια δεν πρέπει να εμφανιστεί στον τελικό κατάλογο των καλεσμένων που θα καθίσουν στο τραπέζι.
Το πρόβλημα αυτό είναι ένα παράδειγμα από αυτά που η πλη-ροφορική αποκαλεί ΝΡ προβλήματα. Είναι εύκολο να ελέγξουμε αν μια συγκεκριμένη λίστα 100 ατόμων από τους 400 ικανοποιεί το κριτήριό μας να μην υπάρχουν ασύμβατα μεταξύ τους ζευγά-ρια στο τραπέζι.
Το να δημιουργήσουμε όμως εμείς μια τέτοια λίστα από τους 400 είναι τόσο δύσκολο που μοιάζει να μην είναι πρακτικά δυνατόν. Μάλιστα, ο αριθμός των εναλλακτικών τρό-πων που μπορούμε να πάρουμε 100 καλεσμένους από τους 400 είναι μεγαλύτερος από το σύνολο των ατόμων που υπάρχουν στο σύμπαν, γι' αυτό και το πρόβλημα δε θα μπορούσε να λυθεί ούτε καν με τη βοήθεια του ισχυρότερου υπερυπολογιστή στον κόσμο.
Μπορεί όμως η δυσκολία αυτή να δείχνει απλά ότι προσεγγί-ζουμε προγραμματιστικά το πρόβλημα με λάθος μέθοδο. Υπάρχει άραγε ένας έξυπνος τρόπος να λυθεί το πρόβλημα; Το πρόβλημα αυτού του τύπου, «Ρ versus ΝΡ» -όπως λέγεται- εμφανίστηκε τη δεκαετία του 1970. Οι Stephen Cook και Leonid Levin διατύπωσαν αυτό το πρόβλημα όπου το Ρ σημαίνει εύκολο να βρεθεί λύση και το ΝΡ σημαίνει εύκολο να ελεγχθεί, ανεξάρτητα ο ένας από τον άλλο κατά το 1971. Γενικά, έχει να κάνει με το αν όντως υπάρχουν προβλήματα τα οποία είναι εύκολο να ελεγχθούν αλλά πρακτικά αδύνατο να λυθούν με άμεσες αλγοριθμικές διαδικασίες.
Για προβλήματα όπως το παραπάνω, κανείς μέχρι σήμερα δεν έχει καταφέρει να δείξει ότι η λύση τους δεν είναι εφικτή με κατάλληλη προγραμματιστική μέθοδο.
Το πρόβλημα «Ρ versus NP» είναι θεμελιώδες για την ασφάλεια των υπολογιστών. Κι αυτό γιατί, όταν κρυπτογραφούνται ψηφιακά οι χρηματικές συναλλαγές, χρησιμοποιούνται αλγό-ριθμοι των οποίων η λύση ελέγχεται εύκολα αλλά δύσκολα βρίσκεται - μεταξύ άλλων, με κλειδιά κρυπτογράφησης που περιέχουν πρώτους αριθμούς. Αν αποδειχθεί ότι ένας ικανός προγραμματιστής μπορεί να βρει ένα σύντομο δρόμο για τη λύση τους, τότε το «σπάσιμο» της κρυπτογράφησης των πλη-ρωμών με πιστωτικές κάρτες ίσως καταστεί εφικτό.
Υποθέστε ότι πρέπει να κάνετε μια λίστα για το πώς θα καθί-σουν οι καλεσμένοι σε ένα μεγάλο εορταστικό δείπνο. Έχετε 400 άτομα στον κατάλογο σας, αλλά πρέπει να επιλέξετε μόνο 100 από αυτούς, καθώς δεν υπάρχει χώρος για περισσότερους. Επίσης, έχετε άλλη μια λίστα από ζεύγη αυτών των ανθρώπων, κι έτσι κανένα από αυτά τα ζευγάρια δεν πρέπει να εμφανιστεί στον τελικό κατάλογο των καλεσμένων που θα καθίσουν στο τραπέζι.
Το να δημιουργήσουμε όμως εμείς μια τέτοια λίστα από τους 400 είναι τόσο δύσκολο που μοιάζει να μην είναι πρακτικά δυνατόν. Μάλιστα, ο αριθμός των εναλλακτικών τρό-πων που μπορούμε να πάρουμε 100 καλεσμένους από τους 400 είναι μεγαλύτερος από το σύνολο των ατόμων που υπάρχουν στο σύμπαν, γι' αυτό και το πρόβλημα δε θα μπορούσε να λυθεί ούτε καν με τη βοήθεια του ισχυρότερου υπερυπολογιστή στον κόσμο.
Μπορεί όμως η δυσκολία αυτή να δείχνει απλά ότι προσεγγί-ζουμε προγραμματιστικά το πρόβλημα με λάθος μέθοδο. Υπάρχει άραγε ένας έξυπνος τρόπος να λυθεί το πρόβλημα; Το πρόβλημα αυτού του τύπου, «Ρ versus ΝΡ» -όπως λέγεται- εμφανίστηκε τη δεκαετία του 1970. Οι Stephen Cook και Leonid Levin διατύπωσαν αυτό το πρόβλημα όπου το Ρ σημαίνει εύκολο να βρεθεί λύση και το ΝΡ σημαίνει εύκολο να ελεγχθεί, ανεξάρτητα ο ένας από τον άλλο κατά το 1971. Γενικά, έχει να κάνει με το αν όντως υπάρχουν προβλήματα τα οποία είναι εύκολο να ελεγχθούν αλλά πρακτικά αδύνατο να λυθούν με άμεσες αλγοριθμικές διαδικασίες.
Για προβλήματα όπως το παραπάνω, κανείς μέχρι σήμερα δεν έχει καταφέρει να δείξει ότι η λύση τους δεν είναι εφικτή με κατάλληλη προγραμματιστική μέθοδο.
Το πρόβλημα «Ρ versus NP» είναι θεμελιώδες για την ασφάλεια των υπολογιστών. Κι αυτό γιατί, όταν κρυπτογραφούνται ψηφιακά οι χρηματικές συναλλαγές, χρησιμοποιούνται αλγό-ριθμοι των οποίων η λύση ελέγχεται εύκολα αλλά δύσκολα βρίσκεται - μεταξύ άλλων, με κλειδιά κρυπτογράφησης που περιέχουν πρώτους αριθμούς. Αν αποδειχθεί ότι ένας ικανός προγραμματιστής μπορεί να βρει ένα σύντομο δρόμο για τη λύση τους, τότε το «σπάσιμο» της κρυπτογράφησης των πλη-ρωμών με πιστωτικές κάρτες ίσως καταστεί εφικτό.
Το πρόβλημα παραμένει άλυτο 30 χρόνια.
Πηγή: http://www.physics4u.gr
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου