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

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

 

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

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

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

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

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

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

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

   Το ερωτηματικό στην ισότητα P=NP? , μπορούμε με τον κατάλληλο αλγόριθμο να μετατρέψουμε ένα δύσκολο πρόβλημα σε εύκολο;

Αφορμή για την  ανάρτηση , η  δήλωση ενός Ινδού μαθηματικού που εργάζεται για τη HP o Vinay Deolalikar  ,  ο οποίος σε μια απόδειξη  100 σελίδων η  οποία ακόμα ελέγχεται  ισχυρίζεται ότι P = NP. Ο χρόνος θα δείξει.

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