Η Πολυπλοκότητα των Προβλημάτων

Γράφει ο Βαγγέλης Τσούκας

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

βημάτων της λύσης του, ο οποίος ονομάζεται πολυπλοκότητα και καθορίζει την ταχύτητα εκτέλεσης αυτής. Τα προβλήματα χωρίζονται γενικά σε τρεις κατηγορίες ανάλογα με την ταχύτητα επίλυσής τους: τα "εύκολα" που χαρακτηρίζονται με το γράμμα P επειδή απαιτούν πολυωνυμικό χρόνο επίλυσης, τα "δύσκολα" που ονομάζονται EXP και απαιτούν εκθετικό χρόνο και τα "ενδιάμεσα" που ονομάζονται ΝP. Για να δώσουμε ένα παράδειγμα τάξης μεγέθους, αν ένα εύκολο πρόβλημα λύνεται σε μία ώρα, το αντίστοιχο ενδιάμεσο απαιτεί ένα μήνα και το δύσκολο τον αστρονομικό χρόνο των 1000 ετών.

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

Η απόδειξη ότι οι δύο κατηγορίες προβλημάτων διαφέρουν δεν αναμένεται να προκαλέσει ιδιαίτερη εντύπωση. Η ανθρωπότητα έχει προεξοφλήσει ότι τα ενδιάμεσα προβλήματα είναι τελικά δύσκολα και πάνω σε αυτό έχει βασίσει κρίσιμους τομείς της λειτουργίας της. Αν αντίθετα κάποια διάνοια καταφέρει να αποδείξει την ισότητα των δύο κατηγοριών τότε η κοινωνία όπως τη γνωρίζουμε σήμερα αναμένεται να αλλάξει. Η πιο άμεση συνέπεια μιας τέτοιας ανακάλυψης είναι ότι θα καταρρεύσει η ασφάλεια οποιασδήποτε κρυπτογραφημένης πληροφορίας στα ψηφιακά δίκτυα υπολογιστών: οι τραπεζικοί λογαριασμοί, τα διπλωματικά μυνήματα και όλο το Διαδίκτυο θα ανοίξουν σε κοινή θέα μέσα σε λίγες ώρες. Μια θετική εξέλιξη θα είναι η αποκάλυψη νέων οδών επίλυσης δύσκολων προβλημάτων που αναμένεται να δώσει στην επιστήμη και την τεχνολογία τη μεγαλύτερη ώθηση του τελευταίου αιώνα και για αυτό πιστεύεται ότι ο κόσμος που προκύψει θα είναι καλύτερος. Ο Scott Aaronson του ΜΙΤ φιλοσοφικά δήλωσε ότι σε μια τέτοια περίπτωση "δε θα έχουν αξία τα δημιουργικά άλματα αφού δε θα υπάρχει διαφορά ανάμεσα στην εύρεση της λύσης ενός προβλήματος και την επιβεβαιώση μιας ήδη υπάρχουσας. Όποιος θα άκουγε μία συμφωνία θα γινόταν Mozart, όποιος θα ακολουθούσε έναν αλγόριθμο θα γινόταν Gauss".

ΣΣ. Ο ορισμός των "ενδιάμεσων" προβλημάτων είναι σύνθετος. Τα προβλήματα αυτά έχουν το χαρακτηριστικό ότι ενώ η επαλήθευση της λύσης τους είναι εύκολη, η ανεύρεσή αυτής παραμένει δύσκολη. Κάτι αντίστοιχο συμβαίνει όταν, ενώ δεν μπορούμε να θυμηθούμε ένα όνομα, αν το ακούσουμε είμαστε σε θέση να επιβεβαιώσουμε την ορθότητά του.