OpenAI και Claude λένε ότι κατέρριψαν την Υπόθεση Εκθετικού Χρόνου (ETH): τι σημαίνει και γιατί δεν κινδυνεύει η κρυπτογραφία
Η OpenAI και, λίγες ώρες μετά, η Anthropic δημοσίευσαν αποδείξεις ότι η Υπόθεση Εκθετικού Χρόνου είναι λάθος. Τι ακριβώς ισχυρίζονται, ποιος τις ελέγχει και γιατί η κρυπτογραφία μένει ασφαλής.
Με μια ματιά
- Στις 26 Οκτωβρίου η OpenAI και λίγες ώρες μετά η Anthropic δημοσίευσαν υποεκθετικούς αλγόριθμους για το 3-SAT, που αν ισχύουν διαψεύδουν την ETH του 1999.
- Οι αποδείξεις περνούν τον έλεγχο του Lean, αλλά οι ερευνητές που εξετάζουν το αποτέλεσμα της OpenAI λένε ότι αυτό δεν είναι πιστοποίηση.
- Ο αλγόριθμος κερδίζει μόνο σε αδιανόητα μεγάλα προβλήματα· η κρυπτογραφία και το ερώτημα P = NP δεν επηρεάζονται.
Η OpenAI ανακοίνωσε στις 26 Οκτωβρίου ότι ένα εσωτερικό της μοντέλο έδειξε πως η Υπόθεση Εκθετικού Χρόνου (ETH) είναι λάθος. Περίπου έξι ώρες μετά, η Anthropic ανέβασε δική της, ανεξάρτητη εργασία από το Claude με το ίδιο συμπέρασμα. Αν οι αποδείξεις αντέξουν τον έλεγχο, θα είναι ένα από τα μεγαλύτερα αποτελέσματα στη θεωρητική πληροφορική των τελευταίων ετών.
Μην περιμένετε, όμως, αλλαγές στην καθημερινή τεχνολογία. Το αποτέλεσμα είναι καθαρά θεωρητικό.
Τι λέει η Υπόθεση Εκθετικού Χρόνου
Την ETH διατύπωσαν το 1999 οι Russell Impagliazzo και Ramamohan Paturi. Αφορά το πρόβλημα 3-SAT, όπου ψάχνουμε αν μια σειρά από λογικούς όρους μπορεί να ισχύει όλη μαζί. Η υπόθεση λέει ότι καμία μέθοδος δεν είναι ουσιαστικά πιο γρήγορη από το να δοκιμάζεις σχεδόν όλους τους συνδυασμούς. Σύμφωνα με την OpenAI, εκατοντάδες εργασίες στηρίζουν τα συμπεράσματά τους σε αυτή την παραδοχή.
Τι ανακοίνωσαν η OpenAI και η Anthropic
- OpenAI: αλγόριθμος για το 3-SAT λίγο πιο γρήγορος από εκθετικό χρόνο, που αρκεί για να «πέσει» η ETH·
- Anthropic: εργασία του Claude με τίτλο «A 2^o(n) Time Algorithm for 3-SAT», δηλαδή επίσης υποεκθετικός αλγόριθμος·
- Έλεγχος με Lean: και οι δύο αποδείξεις περνούν από το Lean, λογισμικό που ελέγχει μια απόδειξη γραμμή προς γραμμή·
- Ανεξάρτητη εξέταση: οι Impagliazzo και Paturi, μαζί με τον Ryan Williams του MIT, εξετάζουν το αποτέλεσμα της OpenAI.
Ωστόσο, οι τρεις ερευνητές γράφουν ότι η συμμετοχή τους δεν αποτελεί πιστοποίηση. Επίσης, το Lean ελέγχει την απόδειξη μόνο απέναντι στη διατύπωση που του δίνεις, όπως σημειώνει το ToKnow.ai. Δεν ελέγχει αν αυτή η διατύπωση ταιριάζει ακριβώς με το κείμενο της εργασίας. Πάντως, ο Impagliazzo χαρακτήρισε το αποτέλεσμα «πολύ σοκαριστικό».
Το Scientific American σημειώνει ότι οι εταιρείες δεν έχουν δημοσιεύσει τα prompts, τον χρόνο υπολογισμού ούτε τη «σκέψη» των μοντέλων. Επιπλέον, μια ομάδα μαθηματικών για την AI, η AGMAI, επέκρινε τον τρόπο που η OpenAI ανακοίνωσε τα αποτελέσματα.
Γιατί η Υπόθεση Εκθετικού Χρόνου δεν αγγίζει την κρυπτογραφία
Ο νέος αλγόριθμος κερδίζει μόνο σε απίστευτα μεγάλα προβλήματα. Σύμφωνα με υπολογισμό των Fabio Dias και Yvens Lima, η μέθοδος της OpenAI περνά σε ταχύτητα τη δοκιμή όλων των συνδυασμών μόνο πάνω από 2 στη δισεκατομμυριοστή μεταβλητές. Είναι ένας αριθμός με περίπου 300 εκατομμύρια ψηφία. Κανένα πραγματικό πρόβλημα δεν έχει τέτοιο μέγεθος.
Γι’ αυτό, οι τράπεζες και η κρυπτογράφηση στο κινητό σας δεν αλλάζουν. Η ίδια η Anthropic γράφει ότι το αποτέλεσμα δεν λέει τίποτα για την επίλυση προβλημάτων στην πράξη. Ακόμη, δεν απαντά στο μεγάλο ερώτημα αν P = NP.
Το θέμα αγγίζει και τη συζήτηση για τους μαθηματικούς απέναντι στις εταιρείες AI. Περισσότερες αναλύσεις θα βρείτε στην ενότητα Αναλύσεις.



