φροντιστήριο

  • 09:15:00 am on April 17, 2007 | 0

    Πηγή : physics4u (θα βρείτε και άλλα άλυτα προβλήματα εκτός από τα δικά σας)

    Υποθέστε ότι πρέπει να κάνετε μια λίστα για το πώς θα καθίσουν οι καλεσμένοι σε ένα μεγάλο εορταστικό δείπνο. Έχετε 400 άτομα στον κατάλογο σας, αλλά πρέπει να επιλέξετε μόνο 100 από αυτούς, καθώς δεν υπάρχει χώρος για περισσότερους. Επίσης, έχετε άλλη μια λίστα από ζεύγη αυτών των ανθρώπων, κι έτσι κανένα από αυτά τα ζευγάρια δεν πρέπει να εμφανιστεί στον τελικό κατάλογο των καλεσμένων που θα καθίσουν στο τραπέζι.

    Το πρόβλημα αυτό είναι ένα παράδειγμα από αυτά που η πληροφορική αποκαλεί ΝΡ προβλήματα. Είναι εύκολο να ελέγξουμε αν μια συγκεκριμένη λίστα 100 ατόμων από τους 400 ικανοποιεί το κριτήριό μας να μην υπάρχουν ασύμβατα μεταξύ τους ζευγάρια στο τραπέζι. Το να δημιουργήσουμε όμως εμείς μια τέτοια λίστα από τους 400 είναι τόσο δύσκολο που μοιάζει να μην είναι πρακτικά δυνατόν. Μάλιστα, ο αριθμός των εναλλακτικών τρόπων που μπορούμε να πάρουμε 100 καλεσμένους από τους 400 είναι μεγαλύτερος από το σύνολο των ατόμων που υπάρχουν στο σύμπαν, γι’ αυτό και το πρόβλημα δε θα μπορούσε να λυθεί ούτε καν με τη βοήθεια του ισχυρότερου υπερυπολογιστή στον κόσμο.

    Μπορεί όμως η δυσκολία αυτή να δείχνει απλά ότι προσεγγίζουμε προγραμματιστικά το πρόβλημα με λάθος μέθοδο. Υπάρχει άραγε ένας έξυπνος τρόπος να λυθεί το πρόβλημα; Το πρόβλημα αυτού του τύπου, «Ρ versus ΝΡ» -όπως λέγεται- εμφανίστηκε τη δεκαετία του 1970. Οι Stephen Cook και Leonid Levin διατύπωσαν αυτό το πρόβλημα ανεξάρτητα ο ένας από τον άλλο κατά το 1971. Tο Ρ σημαίνει εύκολο να βρεθεί λύση και το ΝΡ σημαίνει εύκολο να ελεγχθεί,. Γενικά, έχει να κάνει με το αν όντως υπάρχουν προβλήματα τα οποία είναι εύκολο να ελεγχθούν αλλά πρακτικά αδύνατο να λυθούν με άμεσες αλγοριθμικές διαδικασίες.

    Για προβλήματα όπως το παραπάνω, κανείς μέχρι σήμερα δεν έχει καταφέρει να δείξει ότι η λύση τους δεν είναι εφικτή με κατάλληλη προγραμματιστική μέθοδο.
    Το πρόβλημα «Ρ versus NP» είναι θεμελιώδες για την ασφάλεια των υπολογιστών. Κι αυτό γιατί, όταν κρυπτογραφούνται ψηφιακά οι χρηματικές συναλλαγές, χρησιμοποιούνται αλγόριθμοι των οποίων η λύση ελέγχεται εύκολα αλλά δύσκολα βρίσκεται – μεταξύ άλλων, με κλειδιά κρυπτογράφησης που περιέχουν πρώτους αριθμούς. Αν αποδειχθεί ότι ένας ικανός προγραμματιστής μπορεί να βρει ένα σύντομο δρόμο για τη λύση τους, τότε το «σπάσιμο» της κρυπτογράφησης των πληρωμών με πιστωτικές κάρτες ίσως καταστεί εφικτό.

    back

    Advertisements
     

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: