Είναι ένα δύσκολο πρόβλημα…εύκολο ή πώς να κερδίσετε ένα εκατομμύριο δολάρια αποδεικνύοντας το προφανές.P=NP?

     Δεν μπορούσα να αποφασίσω.Ήταν ο καλύτερος ή ο χειρότερος μαθητής που είχα ποτέ;Είχε για κάθε λύση ένα πρόβλημα!

                                                                      Ανώνυμος μαθηματικός                                                                                                                     

    Εντάξει.Ίσως δεν είναι και τόσο προφανές.Ο τίτλος αναφέρεται σε ένα από τα  επικηρυγμένα προβλήματα του ινστιτούτου μαθηματικών Κλει (Clay mathematics Institute),όποιος κατορθώσει να  το αποδείξει θα φορτώσει το τραπεζικό του λογαριασμό με ένα εκατομμύριο δολάρια...Είναι γνωστό ως P=NP,το όποιο αν θέλετε την γνώμη μου είναι ηλίθιο όνομα όμως η ουσία του προβλήματος είναι πολύ σημαντική.Πόσο αποδοτικοί μπορούν να είναι οι υπολογιστές σε σχέση με το χρόνο που απαιτείται για να λυθεί ένα πρόβλημα.

   Ας τα πάρουμε από την αρχή. Λύνουμε προβλήματα χρησιμοποιώντας υπολογιστές  και το κάνουμε τρέχοντας  κατάλληλα πρόγραμματα ,τα οποία δεν είναι τίποτα άλλο από λίστες με οδηγίες. Μια λίστα οδηγιών  η οποία υλοποιείται από  υπολογιστή και οδηγεί στην λύση ενός προβλήματος  ονομάζεται αλγόριθμος.Το όνομα προέρχεται από τον πέρση μαθηματικό Abu jafar Muhammad ibn Musa al Khawarismi  όποιος έζησε το 800 μ.Χ στο σημερινό Ιράκ.

 Ο αλγόριθμος είναι μια μέθοδος για την λύση ενός συγκεκριμένου προβλήματος,αλλά είναι άχρηστος στην πράξη αν δεν μας δίνει αποτέλεσμα σε εύλογο χρονικό διάστημα.Η ουσία στο συγκεκριμένο πρόβλημα δεν είναι πόσο γρήγορος είναι ο υπολογιστής αλλά πόσους υπολογισμούς θα εκτελέσει ο αλγόριθμος.Ακόμα και για απλά στην διατύπωση και στην λύση τους προβλήματα.Όπως για παράδειγμα,το πρόβλημα του περιοδεύοντος πωλητή. Ένας πωλητής θέλει να επισκεφτεί ένα ορισμένο πλήθος πόλεων και καλείται να βρει την συντομότερη διαδρομή.Όσο περισσότερες πόλεις πρέπει να επισκεφτεί, τόσο περισσότερους υπολογισμούς πρέπει να εκτελέσει ο υπολογιστής για να βρει την συντομότερη διαδρομή.(http://mathhmagic.blogspot.com/2012/07/blog-post_14.html)

Φτάνουμε λοιπόν στο συμπέρασμα ότι η αποδοτικότητα ενός αλγορίθμου εξαρτάται από τo πλήθος των υπολογιστικών βημάτων που πρέπει να εκτελεστούν προκειμένου να επιλυθεί  κάποιο πρόβλημα.Χωρίζουμε τα προβλήματα σε δυο κατηγορίες, αυτά στα οποία το πλήθος των υπολογισμών που απαιτούνται για να επιλυθούν ισούται με μια σταθερή δύναμη, τα «εύκολα» προβλήματα (easy to solve) και τα «δύσκολα» όπου το πλήθος των  υπολογιστικών βημάτων που απαιτούνται αυξάνεται εκθετικά.           

  Για παράδειγμα, αν θέλουμε να πολλαπλασιάσουμε δυο  ν–ψηφιους αριθμούς  χρησιμοποιώντας τον πατροπαράδοτο κλασσικό πολλαπλασιασμό θα χρειαστεί να κάνουμε περίπου ν² υπολογιστικά βήματα.Όμως για να αναλύσουμε ένα  ν-ψηφιο αριθμό  σε γινόμενο πρώτων παραγόντων να βρούμε δηλαδή όλους τους πρώτους διαιρέτες του  θα κάνουμε το πολυ 3^ν  βήματα δοκιμάζοντας όλους τους αριθμούς μέχρι την τετραγωνική ρίζα του ν, αυτή η διαδικασία είναι ένα δύσκολο πρόβλημα.Ο πρώτος αλγόριθμος -ο εύκολος- τρέχει σε πολυωνιμικό χρόνο (class P) και ο δεύτερος  σε μη πολυωνιμικo χρόνο.(not P)

 Το να ελέγξουμε αν ένας αλγόριθμος  είναι αρκετά γρήγορος είναι σχετικά απλό.Τα  πράγματα αλλάζουν όταν  πρέπει να εξετάσουμε αν υπάρχει πιο γρήγορος αλγόριθμος. Και το πιο δύσκολο από όλα είναι να αποδείξουμε ότι ο αλγόριθμος που διαθέτουμε για την επίλυση ενός προβλήματος είναι ο πιο γρήγορος και ο πιο αποδοτικός από οποιοδήποτε άλλο.Έτσι προβλήματα τα όποια έχουμε καταχωρίσει ως δύσκολα μπορεί να αποδειχθούν εύκολα αν βρούμε μια καλύτερη μέθοδο επίλυσης έναν αποδοτικότερο αλγόριθμο,εδώ είναι που έρχεται το ερώτημα του ενός εκατομμυρίου δολαρίων.Τα χρήματα θα τα πάρει όποιος  κατορθώσει να αποδείξει  κάποια συγκεκριμένα προβλήματα είναι αναμφίβολα δύσκολα δηλαδή ότι δεν υπάρχει αλγόριθμος που να τα επιλύει σε πολυωνιμικό χρόνο  ή το αντίθετο. Δηλαδή ότι δεν υπάρχουν δύσκολα προβλήματα αλλά όλα καταλήγουν στην εύρεση του σωστού αλγορίθμου που θα τα επιλύει  σε πολυωνιμικό χρόνο.

   Η δυσκολία ενός προβλήματος  έγκειται  κυρίως στο μέγεθος του αποτελέσματος.Για παράδειγμα  όλοι οι πιθανοί τρόποι με τους όποιους  μπορούμε να διατάξουμε  τους πρώτους ν αριθμούς. Όσο γρήγορος και να είναι ο αλγόριθμος προκύπτουν ν!  αποτελέσματα (ν!=1*2*3*4*…..*(ν-1)*ν). Τέτοιου είδους προβλήματα για τα οποία δεν υπάρχει αμφισβήτηση για την «δυσκολία τους» ονομάζονται  προβλήματα μη αιτιοκρατικού  πολυωνιμικού χρόνου NP .

Άλλο παράδειγμα NP προβλήματος  είναι τα γνωστά μας πάζλ όπου συνενώνουμε κομμάτια και φτιάχνουμε μια συγκεκριμένη εικόνα. Είναι δύσκολο να  φτιάξει κάποιος ένα πάζλ 2000 κομματιών αλλά ο καθένας μπορεί να καταλάβει  αν έχει συναρμολογηθεί σωστά μόλις το δει.

   Αγαπημένο παράδειγμα και πιστεύω οικείο σε όσους έχουν το λειτουργικό της Microsoft  είναι το παιχνίδι Ναρκαλιευτής (Minesweeper) 

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

   Ο αριθμός 1 υποδηλώνει ότι μόνο ένα από τα άθικτα τετράγωνα περιέχει νάρκη,ενώ ο αριθμός 2 υποδηλώνει ότι και τα δυο  περιέχουν νάρκες.Τι έχετε όμως να πείτε για την παρακάτω εικόνα. Άραγε θα μπορούσε να προέρχεται από ένα πραγματικό παιχνίδι;

 

   Υπάρχει τρόπος να τοποθετήσουμε τις νάρκες  έτσι ώστε να αληθεύουν οι αριθμοί που φαίνονται στο σχήμα; 'H μήπως αποκλείεται να προέρχεται η εικόνα από πραγματικό παιχνίδι;Μπορεί να επινοηθεί ένας αποτελεσματικός αλγόριθμος που θα εξακριβώνει  αν οποιαδήποτε στιγμιότυπο ναρκαλιευτή και να σας δώσουν αν προέρχεται ή όχι από πραγματικό παιχνίδι.Το ερωτηματικό στην ισότητα P=NP, μπορούμε με τον κατάλληλο αλγόριθμο να μετατρέψουμε ένα δύσκολο πρόβλημα σε εύκολο;
Το ερώτημα δεν έχει μόνο ακαδημαϊκό ενδιαφέρον,αφού διάφορες σημαντικές τεχνολογίες στηρίζονται ακριβώς στην μη επιλυσιμοτητα των προβλημάτων NP.Οι περισσότεροι αλγόριθμοι κρυπτογράφησης στηρίζονται  στην παραδοχή ότι η παραγοντοποίηση πολύ μεγάλων αριθμών είναι  δύσκολη,δηλ ένα NP πρόβλημα.Αν κάποιος  βρει ένα τρόπο να την μετατρέψει σε P πρόβλημα τότε οι τραπεζικοί σας λογαριασμοί θα κινδύνευαν.

 

Τελικά κάθε δύσκολο πρόβλημα είναι..εύκολο.