Πώς μια ριζοσπαστική ιδέα του Paul Erdős άλλαξε για πάντα τα μαθηματικά, την επιστήμη των υπολογιστών και τον τρόπο με τον οποίο αντιλαμβανόμαστε την έννοια της ύπαρξης.

Υπάρχουν στιγμές στην ιστορία των επιστημών όπου μια νέα ιδέα δεν λύνει απλώς ένα απομονωμένο πρόβλημα, αλλά ανατρέπει ριζικά τον ίδιο τον τρόπο σκέψης μας. Μια τέτοια κομβική στιγμή σημειώθηκε το 1947, όταν ο πρωτοπόρος Ούγγρος μαθηματικός Paul Erdős παρουσίασε μια μέθοδο που αρχικά φάνηκε σχεδόν παράδοξη, αν όχι προκλητική: απέδειξε ότι ένα μαθηματικό αντικείμενο υπάρχει, χωρίς να το κατασκευάσει ποτέ και χωρίς να γνωρίζει πώς μοιάζει. Η προσέγγιση αυτή, γνωστή σήμερα ως πιθανοτική μέθοδος (Probabilistic Method), αποτελεί πλέον ένα από τα κομψότερα και ισχυρότερα εργαλεία στα σύγχρονα διακριτά μαθηματικά, τη συνδυαστική και τη θεωρητική επιστήμη των υπολογιστών.

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

Ο Erdős επέλεξε μια εντελώς διαφορετική, ανατρεπτική διαδρομή. Αντί να αναζητήσει το ένα και μοναδικό αντικείμενο, πρότεινε το εξής:

1. Εξετάζουμε το πλήρες σύνολο όλων των πιθανών αντικειμένων ενός συγκεκριμένου τύπου.
2. Υποθέτουμε ότι επιλέγουμε ένα από αυτά εντελώς τυχαία.
3. Υπολογίζουμε την πιθανότητα το τυχαίο αυτό αντικείμενο να διαθέτει την επιθυμητή ιδιότητα.

Εάν αποδείξουμε ότι η πιθανότητα αυτή είναι μεγαλύτερη από το μηδέν (έστω και κατά ένα απειροελάχιστο ποσοστό), τότε το λογικό συμπέρασμα είναι αναπόφευκτο: Υπάρχει τουλάχιστον ένα τέτοιο αντικείμενο.

• Δεν γνωρίζουμε ποιο είναι.
• Δεν έχουμε ιδέα πώς να το κατασκευάσουμε ντετερμινιστικά.
• Αλλά γνωρίζουμε, με απόλυτη μαθηματική αυστηρότητα, ότι είναι αδύνατο να μην υπάρχει.

Για να γίνει κατανοητή αυτή η βαθιά ιδέα, ας επιστρατεύσουμε μια απλή αναλογία. Φανταστείτε μια τεράστια, σκοτεινή σακούλα που περιέχει εκατομμύρια μπάλες. Δεν μπορούμε να δούμε το εσωτερικό της. Μας ενδιαφέρει να μάθουμε αν μέσα στη σακούλα υπάρχει έστω και μία κόκκινη μπάλα.

Ο κλασικός τρόπος θα απαιτούσε να αδειάσουμε τη σακούλα και να ψάξουμε μία – μία τις μπάλες μέχρι να βρούμε μια κόκκινη. Ωστόσο, η πιθανοτική μέθοδος λειτουργεί διαφορετικά: χρησιμοποιώντας έμμεσες μαθηματικές ιδιότητες του συνόλου, αποδεικνύει ότι αν επιλέξουμε τυχαία μια μπάλα, η πιθανότητα να είναι κόκκινη είναι, για παράδειγμα, 2%. Από τη στιγμή που το 2% είναι μεγαλύτερο από το μηδέν, κλειδώνουμε το συμπέρασμα: η σακούλα κρύβει οπωσδήποτε τουλάχιστον μία κόκκινη μπάλα, ακόμη κι αν δεν την έχουμε αγγίξει ποτέ.

Η πρώτη ιστορική εφαρμογή της μεθόδου από τον Erdős έγινε στη Θεωρία Γραφημάτων (Graph Theory), έναν κλάδο των μαθηματικών που μελετά δίκτυα αποτελούμενα από κορυφές (κόμβους) και ακμές (γραμμές που τους συνδέουν). Ο Erdős ασχολήθηκε με τα λεγόμενα προβλήματα Ramsey, τα οποία συχνά περιγράφονται με το εξής απλό παράδειγμα: Πόσους ανθρώπους πρέπει να καλέσουμε σε ένα πάρτι ώστε να είμαστε σίγουροι ότι υπάρχουν είτε 3 γνωστοί μεταξύ τους είτε 3 εντελώς ξένοι; (Η απάντηση είναι 6).

Όταν όμως οι αριθμοί μεγαλώνουν, η εύρεση των ακριβών ορίων γίνεται εφιαλτικά δύσκολη. Ο Erdős, αντί να προσπαθήσει να σχεδιάσει περίπλοκα γραφήματα που να αποφεύγουν αυτές τις ομαδοποιήσεις, “πέταξε ένα νόμισμα” για κάθε πιθανή σύνδεση μεταξύ των κόμβων, δημιουργώντας ένα τυχαίο γράφημα. Υπολογίζοντας τις προσδοκώμενες τιμές, απέδειξε ότι για συγκεκριμένα μεγέθη, η πιθανότητα να πετύχει ένα γράφημα με εξαιρετικά σπάνιες ιδιότητες ήταν θετική.

Για τους μαθηματικούς της δεκαετίας του 1940, το να αποδεικνύεται η δομή ενός δικτύου μέσω της απόλυτης τυχαιότητας έμοιαζε με καθαρή μαγεία.

Αν και ξεκίνησε ως ένα εργαλείο των θεωρητικών μαθηματικών, η πιθανοτική μέθοδος αποτελεί σήμερα τη ραχοκοκαλιά της σύγχρονης τεχνολογίας.

• Κρυπτογραφία και Πρώτοι Αριθμοί: Η ασφάλεια των διαδικτυακών μας συναλλαγών βασίζεται σε τεράστιους πρώτους αριθμούς. Οι αλγόριθμοι που χρησιμοποιούμε για να τους εντοπίσουμε (όπως ο έλεγχος Miller – Rabin) είναι πιθανοτικοί. Ελέγχουν αν ένας αριθμός είναι πρώτος με ελάχιστα υπολογιστικά βήματα, προσφέροντας μια απειροελάχιστη πιθανότητα σφάλματος που στην πράξη είναι μικρότερη από την πιθανότητα να χτυπηθεί ο υπολογιστής από μετεωρίτη.
• Σχεδιασμός Δικτύων: Από τη δρομολόγηση των δεδομένων στο διαδίκτυο μέχρι τη διάταξη των τρανζίστορ στους μικροεπεξεργαστές, οι μηχανικοί χρησιμοποιούν πιθανοτικές τεχνικές για να εξασφαλίσουν ότι τα συστήματα δεν θα καταρρεύσουν από “κυκλοφοριακή συμφόρηση”.
• Τεχνητή Νοημοσύνη και Machine Learning: Τα μεγάλα γλωσσικά μοντέλα και οι αλγόριθμοι βαθιάς μάθησης βασίζονται σε στοχαστικές (τυχαίες) διαδικασίες. Κατά την εκπαίδευσή τους, ξεκινούν από μια εντελώς τυχαία κατάσταση και, μέσω πιθανοτικών προσεγγίσεων, συγκλίνουν σε εξαιρετικά ακριβείς λύσεις.
• Διαχείριση Big Data: Όταν καλούμαστε να αναλύσουμε petabytes δεδομένων, είναι αδύνατο να εξετάσουμε κάθε εγγραφή ξεχωριστά. Η τυχαία δειγματοληψία, θωρακισμένη από την πιθανοτική θεωρία, μας επιτρέπει να εξάγουμε ασφαλή συμπεράσματα για το σύνολο του πληθυσμού χωρίς συστηματικά σφάλματα.

Η κληρονομιά του Paul Erdős, ο οποίος υπήρξε ένας από τους πιο παραγωγικούς μαθηματικούς στην ιστορία με πάνω από 1.500 δημοσιεύσεις, μας αναγκάζει να επανεξετάσουμε μια βαθιά φιλοσοφική θέση: Τι σημαίνει “γνωρίζω”;

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

—

Προτεινόμενη Βιβλιογραφία

• Alon, N., & Spencer, J. H. (2016). The Probabilistic Method (4th ed.). Wiley
• Erdős, P. (1947). Some remarks on the theory of graphs. Bulletin of the American Mathematical Society, 53(4), 292–294
• American Mathematical Society. (n.d.). History of the probabilistic method