Στις 26 Οκτωβρίου 2026 η OpenAI ανακοίνωσε ότι ένα εσωτερικό της μοντέλο απέδειξε πως η Υπόθεση Εκθετικού Χρόνου (Exponential Time Hypothesis, ETH) είναι λάθος. Πρόκειται για μια υπόθεση του 1999, πάνω στην οποία έχουν στηριχτεί εκατοντάδες επιστημονικές εργασίες. Μέσα σε λίγες ώρες, όλο το X ρωτούσε το ίδιο πράγμα: μήπως πλησιάζουμε στο P = NP;
Παρακάτω εξηγούμε με απλά λόγια τι ακριβώς ισχυρίζεται η OpenAI, τι δεν ισχυρίζεται, γιατί έχει σημασία και τι σχέση έχει με το πιο διάσημο ανοιχτό πρόβλημα της πληροφορικής.
Τι ανακοινώθηκε
Η OpenAI δημοσίευσε τρία αποτελέσματα που, όπως λέει, παρήγαγαν τα εσωτερικά της μοντέλα: ένα στα μαθηματικά (local smoothing και εικασία Kakeya), ένα στη φυσική (ύπαρξη θεωριών Yang-Mills και QCD) και ένα στην πληροφορική, την ανατροπή του ETH. Εδώ μας απασχολεί το τρίτο.
- 16 Οκτωβρίου: το μοντέλο έγραψε την απόδειξη σε φυσική γλώσσα.
- 17 Οκτωβρίου: η απόδειξη γράφτηκε και ελέγχθηκε στο Lean, ένα εργαλείο όπου ο υπολογιστής επαληθεύει κάθε βήμα μιας μαθηματικής απόδειξης.
- 26 Οκτωβρίου: το άρθρο «The Exponential Time Hypothesis is False» και η απόδειξη σε Lean δημοσιεύτηκαν στο GitHub της OpenAI. Ως συγγραφέας αναγράφεται μόνο «OPENAI».
Την ανεξάρτητη εξέταση οργανώνουν ο Russell Impagliazzo και ο Ramamohan Paturi (UC San Diego), δηλαδή δύο από τους ανθρώπους που διατύπωσαν το ETH, μαζί με τον Ryan Williams του MIT. Στη δημόσια επιστολή τους γράφουν ότι η συμμετοχή τους δεν πρέπει να θεωρηθεί πιστοποίηση του αποτελέσματος. Με άλλα λόγια, ο ισχυρισμός είναι σοβαρός, αλλά δεν έχει ακόμη περάσει από την κρίση της επιστημονικής κοινότητας.
Το παζλ με τους διακόπτες
Για να καταλάβουμε τι ανατράπηκε, ξεκινάμε από ένα παζλ. Έχετε μερικούς διακόπτες. Ο καθένας είναι ανοιχτός ή κλειστός. Έχετε επίσης κανόνες, για παράδειγμα «τουλάχιστον ένας από τους Α, Β ή όχι Γ πρέπει να ισχύει». Το ερώτημα είναι αν υπάρχει τρόπος να ρυθμίσετε τους διακόπτες ώστε να ισχύουν όλοι οι κανόνες μαζί.
Στην πληροφορική αυτό λέγεται πρόβλημα ικανοποιησιμότητας, SAT. Όταν κάθε κανόνας έχει το πολύ τρεις διακόπτες, λέγεται 3-SAT. Ακούγεται σαν σπαζοκεφαλιά, όμως σε τέτοια μορφή μεταφράζονται πάρα πολλά πραγματικά προβλήματα: προγράμματα βαρδιών, δρομολόγια, έλεγχος κυκλωμάτων, συνδυασμοί ρυθμίσεων.
Ο προφανής τρόπος είναι να δοκιμάσετε όλους τους συνδυασμούς. Το πρόβλημα είναι ότι κάθε νέος διακόπτης διπλασιάζει τη δουλειά.
| Διακόπτες | Συνδυασμοί | Για να το φανταστείτε |
|---|---|---|
| 10 | 1.024 | τους ελέγχει ένα κινητό αμέσως |
| 30 | περίπου 1 δισεκατομμύριο | λίγα δευτερόλεπτα σε υπολογιστή |
| 60 | περίπου 1018 | δεκαετίες, με ένα δισεκατομμύριο ελέγχους το δευτερόλεπτο |
| 100 | περίπου 1030 | περισσότεροι από τους κόκκους άμμου όλης της Γης |
Τι έλεγε η Υπόθεση Εκθετικού Χρόνου
Οι ερευνητές βρήκαν με τα χρόνια έξυπνους αλγορίθμους που κάνουν το 3-SAT πιο γρήγορα από το «δοκίμασε τα όλα». Όλοι όμως είχαν κάτι κοινό: η ανάπτυξη παρέμενε εκθετική. Μπορούσες να μικρύνεις τον αριθμό στον εκθέτη, όχι να ξεφύγεις από τον εκθέτη.
Το 1999 ο Impagliazzo και ο Paturi το διατύπωσαν ως υπόθεση: για το 3-SAT, κανένας αλγόριθμος, όσο έξυπνος κι αν είναι, δεν μπορεί να ξεφύγει από χρόνο της μορφής 2c·n, για κάποια σταθερά c μεγαλύτερη από το μηδέν. Αυτό είναι το ETH.
Κανείς δεν το είχε αποδείξει. Όμως σχεδόν όλοι το πίστευαν, και έγινε εργαλείο. Πολλά αποτελέσματα γράφτηκαν με τη λογική «αν ισχύει το ETH, τότε αυτό το πρόβλημα δεν λύνεται πιο γρήγορα από τόσο». Σύμφωνα με την OpenAI, το ETH έχει χρησιμοποιηθεί σε εκατοντάδες εργασίες, σε θεωρία γράφων, υπολογιστική βιολογία, βάσεις δεδομένων και υπολογιστική γεωμετρία.
Το ETH λειτουργούσε σαν θεμέλιο. Δεν ήταν αποδεδειγμένο, αλλά πάνω του χτίστηκε ένα μεγάλο κομμάτι του τι θεωρούμε «αδύνατο» στους υπολογισμούς.
Τι ακριβώς ισχυρίζεται ότι απέδειξε η OpenAI
Το άρθρο περιγράφει έναν ντετερμινιστικό αλγόριθμο, δηλαδή χωρίς τύχη, που δεν απαντά απλώς «υπάρχει λύση ή όχι». Μετράει ακριβώς πόσες λύσεις έχει το παζλ. Αυτό είναι συνήθως πιο δύσκολο από το απλό ναι ή όχι. Αν οι λύσεις είναι πάνω από μηδέν, έχετε και την απάντηση στο SAT.
Ο χρόνος που χρειάζεται είναι, χοντρικά, 2n / √log n, με n τον αριθμό των διακοπτών. Η διαφορά από το 2c·n φαίνεται μικρή, αλλά είναι ουσιαστική: ο εκθέτης διαιρείται με κάτι που μεγαλώνει, όσο μεγαλώνει το πρόβλημα. Άρα για αρκετά μεγάλα προβλήματα ο αλγόριθμος κερδίζει κάθε εκθετικό χρόνο, όσο μικρή κι αν είναι η σταθερά c. Αυτό ακριβώς έλεγε το ETH ότι δεν γίνεται. Επιπλέον, ο αλγόριθμος χρειάζεται λίγη μνήμη, πολυωνυμική όπως λένε οι ειδικοί.
Πώς το καταφέρνει; Σε πολύ απλή εικόνα, δεν ψάχνει πιο έξυπνα ανάμεσα στους συνδυασμούς. Μετατρέπει το μέτρημα των λύσεων σε άλγεβρα με πολυώνυμα, «παραμορφώνει» το πρόβλημα ώστε οι διακόπτες να χωριστούν σε μικρές, σχεδόν ανεξάρτητες ομάδες, λύνει τις ομάδες και μετά αναιρεί μαθηματικά την παραμόρφωση για να πάρει το σωστό αποτέλεσμα. Οι λεπτομέρειες απλώνονται σε περίπου εξήντα σελίδες.
Το Lean ελέγχει ότι η απόδειξη είναι λογικά σωστή βήμα βήμα. Δεν ελέγχει μόνο του ότι η διατύπωση στο Lean αποτυπώνει πιστά αυτό που εννοούν οι άνθρωποι με το ETH. Γι' αυτό έχει σημασία η εξέταση από τους ειδικούς.
Γιατί είναι τόσο σημαντικό
Πρώτον, γιατί ανατρέπει κάτι που σχεδόν όλοι θεωρούσαν σίγουρο. Δεν πρόκειται για βελτίωση ενός αλγορίθμου κατά μερικά τοις εκατό. Πρόκειται για απόδειξη ότι ένα όριο που θεωρούσαμε τείχος δεν υπάρχει.
Δεύτερον, γιατί πολλά συμπεράσματα της τελευταίας εικοσαετίας ξεκινούσαν από το ETH. Αν το ETH πέσει, αυτά τα «δεν γίνεται πιο γρήγορα» χάνουν τη βάση τους και κάποια προβλήματα που είχαν γραφτεί ως χαμένη υπόθεση ανοίγουν ξανά για έρευνα. Το ίδιο το άρθρο δίνει ήδη γρηγορότερους αλγορίθμους για το μέτρημα χρωματισμών γράφων και τελείων ταιριασμάτων. Το ίδιο θεώρημα, κατά το άρθρο, ανατρέπει και ισχυρότερες παραλλαγές της υπόθεσης, όπως το Strong ETH.
Τρίτον, γιατί το έκανε μοντέλο τεχνητής νοημοσύνης. Αν επιβεβαιωθεί, θα είναι από τις πρώτες φορές που ένα AI ανατρέπει μόνο του μια κεντρική, ευρέως αποδεκτή υπόθεση σε ένα πεδίο. Ο Ryan Williams το συνόψισε στο X ως «claimed refutation», δηλαδή ισχυριζόμενη ανατροπή, και η ομάδα του γράφει ότι, αν ισχύει, θα αλλάξει ένα σημαντικό κομμάτι της θεωρητικής πληροφορικής.
Και τι σχέση έχει το P = NP;
Εδώ ξεκίνησε η φωτιά στα social. Ας το πάρουμε απλά.
- P είναι τα προβλήματα που λύνονται γρήγορα. «Γρήγορα» στη γλώσσα της επιστήμης σημαίνει σε πολυωνυμικό χρόνο, όπως n2 ή n3 βήματα.
- NP είναι τα προβλήματα όπου, αν κάποιος σας δώσει μια λύση, την ελέγχετε γρήγορα. Ένα Sudoku είναι δύσκολο να λυθεί, αλλά ένα συμπληρωμένο Sudoku το ελέγχετε σε λίγα δευτερόλεπτα.
Το μεγάλο ερώτημα είναι αν αυτά τα δύο είναι τελικά το ίδιο: αν ό,τι ελέγχεται εύκολα, λύνεται και εύκολα. Είναι ένα από τα επτά Προβλήματα της Χιλιετίας του Ινστιτούτου Clay, με βραβείο ένα εκατομμύριο δολάρια. Το 3-SAT είναι το πιο κλασικό πρόβλημα της κατηγορίας NP. Αν λυνόταν σε πολυωνυμικό χρόνο, θα ίσχυε P = NP.
| Αν... | Τότε... |
|---|---|
| ίσχυε το ETH | θα ίσχυε και P ≠ NP, γιατί το 3-SAT θα ήθελε πάντα εκθετικό χρόνο |
| το ETH είναι λάθος (ο νέος ισχυρισμός) | το 3-SAT λύνεται σε «υποεκθετικό» χρόνο, αλλά το P vs NP μένει ανοιχτό |
| ίσχυε P = NP με πρακτικό αλγόριθμο | θα άλλαζαν η κρυπτογράφηση, η βελτιστοποίηση και η ίδια η έρευνα |
Τι γράφτηκε στο X
Ο Eric S. Raymond, γνωστός προγραμματιστής του open source, έγραψε ότι όποιος ξέρει κάτι από υπολογιστική πολυπλοκότητα αναρωτιόταν εκείνο το βράδυ αν αυτός είναι ο τρόπος του σύμπαντος να «ψιθυρίσει» ότι P = NP. Πρόσθεσε ότι εξακολουθεί να θεωρεί πιο πιθανό το P ≠ NP, αλλά ότι οι πιθανότητές του άλλαξαν δραματικά μέσα σε τέσσερις ώρες (ανάρτηση).
Ο Phoenix Yin, σε ανάρτηση στα κινέζικα, περιέγραψε τι θα σήμαινε ένα πρακτικό P = NP: τράπεζες, HTTPS και κρυπτονομίσματα θα έπρεπε να ξαναχτιστούν από την αρχή, προβλήματα όπως βάρδιες, logistics και σχεδιασμός chips θα λύνονταν βέλτιστα, και η απόσταση ανάμεσα στο να αναγνωρίζεις μια καλή λύση και στο να τη βρίσκεις θα εξαφανιζόταν. «Η δημιουργικότητα μπορεί να μηχανοποιηθεί», έγραψε, και αμέσως μετά: «ελπίζω να είναι απλώς ευσεβής πόθος» (ανάρτηση). Σε προηγούμενη ανάρτηση το χαρακτήρισε τη μεγαλύτερη επιστημονική είδηση της χρονιάς (ανάρτηση).
Η Jen Zhu έγραψε ότι το P = NP θα είναι το απόλυτο τεστ για την τεχνητή νοημοσύνη, γιατί απαιτεί σκέψη για τα όρια των υπολογισμών και όχι απλώς υπολογισμό (ανάρτηση). Ο Ryan Orhan σημείωσε ότι το ETH ήταν θεμελιώδης υπόθεση της θεωρητικής πληροφορικής για δεκαετίες και ότι εκατοντάδες εργασίες στηρίχτηκαν σε αυτό (ανάρτηση).
Ο Gergely Orosz ρώτησε τι θα σήμαινε ένα P = NP με απόδειξη τόσο μεγάλη και περίπλοκη που μόνο μηχανή μπορεί να την ελέγξει (ανάρτηση). Λίγο αργότερα αναδημοσίευσε την απάντηση του Vladimir Prus ως «καλή υπενθύμιση»: «υποεκθετικό» δεν σημαίνει «πολυωνυμικό», και δεν φαίνεται να αποκτήσαμε αλγόριθμο που θα μπει σε πρακτικούς SAT solvers.
Η πιο ψύχραιμη ανάγνωση: πιο γρήγορο από εκθετικό δεν σημαίνει γρήγορο. Το P = NP δεν αποδείχτηκε. Απλώς ένα από τα επιχειρήματα που μας έκαναν να το θεωρούμε σχεδόν αδύνατο μόλις έπεσε.
Τι θα άλλαζε αν αποδειχθεί P = NP
Ας κάνουμε το πείραμα σκέψης μέχρι το τέλος. Ας πούμε ότι κάποια μέρα αποδεικνύεται ότι P = NP, και μάλιστα με αλγόριθμο που δουλεύει στην πράξη, όχι μόνο στη θεωρία. Τι αλλάζει;
- Κρυπτογράφηση. Μεγάλο μέρος της ασφάλειας στο διαδίκτυο στηρίζεται στο ότι κάτι ελέγχεται εύκολα αλλά «σπάει» δύσκολα. Αν ό,τι ελέγχεται εύκολα λύνεται και εύκολα, η κρυπτογράφηση που προστατεύει τράπεζες, κωδικούς και κρυπτονομίσματα θα έπρεπε να ξαναγραφτεί.
- Βελτιστοποίηση. Βάρδιες, δρομολόγια, σχεδιασμός chips, φόρτωση φορτηγών. Σήμερα για τέτοια προβλήματα βρίσκουμε μια καλή λύση. Με πρακτικό P = NP θα βρίσκαμε την καλύτερη δυνατή.
- Μαθηματικά και έρευνα. Μια απόδειξη ελέγχεται σχετικά εύκολα. Αν ό,τι ελέγχεται εύκολα βρίσκεται κι εύκολα, τότε και οι αποδείξεις, τουλάχιστον όσες έχουν λογικό μήκος, θα μπορούσαν να βρίσκονται αυτόματα.
- Δημιουργικότητα. Θεωρούμε δεδομένο ότι το να αναγνωρίζεις κάτι καλό είναι πιο εύκολο από το να το φτιάξεις. Το P = NP θα έλεγε ότι, για μια μεγάλη κατηγορία προβλημάτων, αυτή η απόσταση δεν υπάρχει. Η δημιουργικότητα θα γινόταν, κατά κάποιον τρόπο, μηχανική.
Γι' αυτό το P = NP θεωρείται τόσο μεγάλο ερώτημα, και γι' αυτό οι περισσότεροι ειδικοί εξακολουθούν να ποντάρουν ότι P ≠ NP. Ακόμη και ένα θεωρητικό P = NP θα μπορούσε να μην αλλάξει τίποτα στην πράξη, αν ο αλγόριθμος ήταν πολυωνυμικός αλλά με τεράστιο εκθέτη, όπως n100.
Τι δεν σημαίνει
- Δεν αποδείχτηκε ότι P = NP. Ούτε η OpenAI το ισχυρίζεται. Το άρθρο της λέει ρητά ότι το αποτέλεσμα δεν σημαίνει πως όλα τα προβλήματα NP λύνονται σε υποεκθετικό χρόνο.
- Η κρυπτογράφηση δεν έσπασε. Η τράπεζά σας, το HTTPS και οι κωδικοί σας δεν επηρεάζονται από αυτό το αποτέλεσμα.
- Οι πρακτικοί SAT solvers δεν αλλάζουν. Το πλεονέκτημα φαίνεται μόνο σε τεράστια μεγέθη. Η ίδια η OpenAI γράφει ότι η μετατροπή της θεωρίας σε πρακτικούς αλγορίθμους θα χρειαστεί πολλή ακόμη έρευνα.
- Δεν είναι ακόμη επιβεβαιωμένο. Υπάρχει έλεγχος σε Lean, αλλά η επιστημονική κοινότητα μόλις ξεκίνησε να το εξετάζει.
Τι κρατάμε εμείς, ως επιχειρήσεις
Η είδηση δεν αλλάζει κάτι στη δουλειά σας αύριο το πρωί. Δείχνει όμως πού πηγαίνει η τεχνητή νοημοσύνη. Μέχρι πρόσφατα τη χρησιμοποιούσαμε για να γράφει κείμενα και κώδικα. Αν αυτό το αποτέλεσμα επιβεβαιωθεί, η AI αρχίζει να ανακαλύπτει νέους αλγορίθμους, πράγμα που μέχρι τώρα έκαναν μόνο κορυφαίοι ερευνητές.
Τα «δύσκολα» προβλήματα του άρθρου υπάρχουν ήδη σε κάθε επιχείρηση, σε πιο ήπια μορφή: ποιος δουλεύει ποια βάρδια, ποιο ραντεβού χωράει πού, ποια διαδρομή κάνει το φορτηγό, ποιο απόθεμα παραγγέλνεται πότε. Σήμερα αυτά λύνονται καλά, με πρακτικούς αλγορίθμους που βρίσκουν μια πολύ καλή λύση χωρίς να ψάχνουν όλους τους συνδυασμούς. Η διαφορά ανάμεσα στο «Excel και φωνές» και σε ένα σύστημα που το κάνει αυτόματα μετριέται σε ώρες κάθε εβδομάδα.
Στην HigherHighLabs χτίζουμε custom εφαρμογές για τέτοια προβλήματα: προγράμματα και βάρδιες, συστήματα ραντεβού, αυτοματισμούς με AI. Χρησιμοποιούμε τα νέα εργαλεία AI στην καθημερινή μας δουλειά, αλλά κρατάμε τα πόδια στη γη: ό,τι παραδίδουμε το ελέγχουμε σε πραγματικά δεδομένα.
Πηγές
- OpenAI: Working with academic communities to build scientific understanding (26/10/2026)
- OpenAI: The Exponential Time Hypothesis is False (preprint, αναθεώρηση 25/10/2026)
- Ryan Williams στο X για την εξέταση του ισχυρισμού
- The Next Web: OpenAI says its AI model has disproved the Exponential Time Hypothesis