Υπόθεση εκθετικού χρόνου (ETH)

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

Η ETH συνδέεται στενά με το πρόβλημα P εναντίον NP, για το οποίο έχουμε ξεχωριστό άρθρο. Αν δεν το έχεις διαβάσει, ρίξε πρώτα μια ματιά εκεί, γιατί θα στηριχτούμε πάνω του. Κυρίως στο τι είναι η πολυπλοκότητα ενός αλγορίθμου και γιατί ανάμεσα στο n² και στο 2ⁿ υπάρχει τέτοιο χάσμα.

Ποιον να καλέσουμε στο πάρτι

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

1. Θα έρθει ο Τάσος ή η Κατερίνα (ίσως και οι δύο).
2. Ο Ιάσονας και η Κατερίνα δεν αντέχουν ο ένας τον άλλον, οπότε δεν θα έρθουν και οι δύο.
3. Ο Δημήτρης θα έρθει μόνο αν έρθει και ο Ιάσονας.
4. Αν έρθει ο Τάσος, πρέπει να έρθει και η Κατερίνα ή ο Δημήτρης.
5. Αν έρθουν και ο Τάσος και η Κατερίνα, πρέπει να έρθει και ο Ιάσονας.
6. Θα έρθει τουλάχιστον ένας από την τριάδα Τάσος, Ιάσονας, Δημήτρης.

Ποιους να καλέσεις, ώστε να ισχύουν όλες οι συνθήκες ταυτόχρονα; Δοκίμασε να το βρεις μόνος σου, τη λύση την κρύβουμε στο τέλος του άρθρου.

Οι πληροφορικοί θα μετέφραζαν το πρόβλημα στη γλώσσα του προτασιακού λογισμού. Κάθε φίλος παίρνει ένα γράμμα. Για ευκολία παίρνουμε τα λατινικά αρχικά των ονομάτων: T για τον Τάσο, K για την Κατερίνα, D για τον Δημήτρη, ενώ ο Ιάσονας είναι J, όπως στο αγγλικό Jason. Το γράμμα είναι είτε αληθές (ο Τάσος θα έρθει) είτε ψευδές (ο Τάσος δεν θα έρθει). Το σύμβολο ∨ το διαβάζουμε «ή» και το ¬ το διαβάζουμε «όχι». Η πρώτη συνθήκη μοιάζει τότε έτσι:

$$T\vee K$$

Η δεύτερη συνθήκη λέει ότι ο Ιάσονας δεν θα έρθει ή η Κατερίνα δεν θα έρθει:

$$\mathrm{\neg }J\vee \mathrm{\neg }K$$

Στην τρίτη συνθήκη εύκολα μπερδεύεται κανείς. Το «Ο Δημήτρης θα έρθει μόνο αν έρθει και ο Ιάσονας» σημαίνει ότι δεν επιτρέπεται να έρθει ο Δημήτρης χωρίς τον Ιάσονα. Δηλαδή είτε ο Δημήτρης δεν θα έρθει είτε θα έρθει ο Ιάσονας:

$$\mathrm{\neg }D\vee J$$

Με τον ίδιο τρόπο γράφουμε και τις υπόλοιπες. Ολόκληρο το πρόβλημα μοιάζει τότε έτσι:

$$\begin{array}{rcl}1.& & T\vee K\\ 2.& & \mathrm{\neg }J\vee \mathrm{\neg }K\\ 3.& & \mathrm{\neg }D\vee J\\ 4.& & \mathrm{\neg }T\vee K\vee D\\ 5.& & \mathrm{\neg }T\vee \mathrm{\neg }K\vee J\\ 6.& & T\vee J\vee D\end{array}$$

Δες πόσο μοιάζουν οι συνθήκες μεταξύ τους: μερικά γράμματα, κάποια με το σύμβολο ¬, ενωμένα με τη λέξη «ή». Και καμία δεν έχει περισσότερα από τρία γράμματα. Το πρόβλημα όπου έχουμε τέτοιες συνθήκες και ψάχνουμε πώς να δώσουμε στα γράμματα αλήθεια και ψέμα, ώστε να ισχύουν όλες μαζί, λέγεται 3-SAT. Το τρία σημαίνει ότι η συνθήκη έχει το πολύ τρία γράμματα, και το SAT είναι συντομογραφία της αγγλικής λέξης satisfiability, δηλαδή ικανοποιησιμότητα.

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

Πόσες δυνατότητες πρέπει να δοκιμάσουμε;

Ο πιο απλός τρόπος είναι να δοκιμάσουμε τα πάντα. Ο Τάσος θα έρθει ή δεν θα έρθει, αυτές είναι δύο δυνατότητες. Για καθεμία από αυτές ο Ιάσονας θα έρθει ή όχι, αυτές είναι ήδη τέσσερις δυνατότητες. Για τέσσερις φίλους είναι

$$2\cdot 2\cdot 2\cdot 2=2^4=16.$$

Με τον ίδιο τρόπο σκεφτήκαμε για τα δυαδικά διανύσματα στο άρθρο για το P εναντίον NP. Αν έχουμε n γράμματα, μπορούμε να τους δώσουμε αλήθεια και ψέμα με 2ⁿ τρόπους. Για 4 φίλους είναι 16 δυνατότητες, που τις περνάς σε λίγα λεπτά. Για 100 γράμματα είναι

$$2^{100}\approx 1,27\cdot {10}^{30}$$

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

Αντίστροφα όμως είναι εύκολο: όταν κάποιος σου πει «κάλεσε αυτούς τους τρεις», το ελέγχεις αμέσως. Αρκεί να περάσεις τις έξι συνθήκες και σε καθεμία να δεις αν ισχύει. Να βρεις λύση είναι δύσκολο, να την ελέγξεις είναι εύκολο. Ακριβώς τέτοια προβλήματα κατατάξαμε στο άρθρο για το P εναντίον NP στην κλάση NP.

Μόνο που το 3-SAT δεν είναι στην NP ένα τυχαίο πρόβλημα: το 1971 αποδείχτηκε ότι στο 3-SAT μπορεί να μεταφραστεί κάθε πρόβλημα της NP. Όποιος λοιπόν μπορούσε να λύνει γρήγορα το 3-SAT, θα μπορούσε να λύνει γρήγορα απολύτως τα πάντα όσα ελέγχονται γρήγορα. Τα προβλήματα με αυτή την ιδιότητα λέγονται NP-πλήρη και το 3-SAT είναι ο πιο διάσημος εκπρόσωπός τους.

Γίνεται πιο γρήγορα από 2ⁿ;

Γίνεται. Να δοκιμάζουμε απολύτως τα πάντα είναι περιττό. Αρκεί, για παράδειγμα, να προσέξουμε ότι ο Τάσος δεν θα έρθει: από την πρώτη συνθήκη τότε προκύπτει αμέσως ότι πρέπει να έρθει η Κατερίνα. Όλες τις δυνατότητες όπου δεν θα ερχόταν κανείς από τους δύο τις διαγράφουμε αμέσως. Οι έξυπνοι αλγόριθμοι συνδυάζουν πολλά τέτοια κόλπα. Οι καλύτεροι που γνωρίζουμε σήμερα χρειάζονται περίπου

$${\mathrm{1,307}}^n$$

βήματα. Αυτό είναι τεράστιο άλμα. Για n = 100 αντί για 10³⁰ βγαίνουν περίπου 4,2 · 10¹¹ βήματα, που ο υπολογιστής τα κάνει σε λίγα λεπτά.

Αλλά προσοχή, κρύβεται παγίδα. Το 1,307ⁿ είναι ακόμη εκθετική συνάρτηση. Μικρύναμε τη βάση από το δύο στο 1,307, όμως η μεταβλητή n έμεινε στον εκθέτη. Όταν το n συνεχίσει να μεγαλώνει, στο τέλος θα μας συντρίψει έτσι κι αλλιώς. Για n = 1000 ακόμη και το 1,307ⁿ είναι αριθμός με 117 ψηφία.

Και πώς θα έμοιαζε ένας αλγόριθμος που δεν είναι εκθετικός; Για παράδειγμα ένας που τα βγάζει πέρα με n³ βήματα. Θα ήταν πολυωνυμικός και το 3-SAT θα ανήκε τότε στην κλάση P. Ανάμεσα στα πολυώνυμα και στις εκθετικές συναρτήσεις υπάρχει όμως μια γκρίζα ζώνη: συναρτήσεις που αυξάνονται ταχύτερα από κάθε πολυώνυμο και παρ' όλα αυτά πιο αργά από κάθε εκθετική. Για παράδειγμα

$$2^{\sqrt{n}}.$$

Εδώ στον εκθέτη υπάρχει μόνο η τετραγωνική ρίζα του n. Ας συγκρίνουμε και τις τέσσερις συναρτήσεις σε έναν πίνακα:

Για n = 1000 το $2^{\sqrt{n}}$ είναι στην ίδια κατηγορία με το n³, ενώ οι δύο εκθετικές έχουν ξεφύγει σε αριθμούς για τους οποίους δεν έχουμε ούτε ονόματα. Συναρτήσεις όπως το $2^{\sqrt{n}}$, που αυξάνονται πιο αργά από το cⁿ για οποιαδήποτε βάση c μεγαλύτερη από το ένα, λέγονται υποεκθετικές.

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

Οι εκθετικές συναρτήσεις σε ένα τέτοιο γράφημα είναι ευθείες που ανεβαίνουν συνεχώς. Η κόκκινη 2ⁿ είναι πιο απότομη από την πορτοκαλί 1,307ⁿ, αλλά και οι δύο είναι ευθείες. Το ενδιαφέρον είναι ότι η πορτοκαλί στην αρχή βρίσκεται ακόμη και κάτω από την πράσινη n³. Την ξεπερνά μόλις γύρω στο n = 42, αλλά μετά οριστικά. Η μπλε $2^{\sqrt{n}}$ αντίθετα καμπυλώνει και μένει χαμηλά κοντά στην πράσινη.

Τι ακριβώς ισχυρίζεται η ETH

Τώρα μπορούμε να διατυπώσουμε την υπόθεση. Το 1999 τη διατύπωσαν ο Russell Impagliazzo και ο Ramamohan Paturi:

Υπάρχει αριθμός c μεγαλύτερος από το ένα τέτοιος ώστε κανένας αλγόριθμος να μην μπορεί να λύσει το 3-SAT με n γράμματα πιο γρήγορα από περίπου cⁿ βήματα.

Και με απλά λόγια; Τη βάση της εκθετικής συνάρτησης ξέρουμε να τη μικραίνουμε με έξυπνα κόλπα, από το δύο στο 1,5, στο 1,307, ίσως κάποτε στο 1,2. Ποτέ όμως δεν θα τη συμπιέσουμε όσο κοντά θέλουμε στο ένα. Κάπου υπάρχει ένα όριο, κάτω από το οποίο δεν γίνεται. Αλγόριθμος με πολυπλοκότητα $2^{\sqrt{n}}$ δεν θα έπρεπε λοιπόν, σύμφωνα με την ETH, να υπάρχει.

Γιατί υπόθεση; Επειδή κανείς δεν ξέρει να την αποδείξει. Η ETH είναι μια υπόθεση εργασίας, όπως και στο άρθρο για το P εναντίον NP δεχόμαστε ότι P ≠ NP. Οι περισσότεροι πληροφορικοί την πιστεύουν, επειδή δεκαετίες προσπαθειών έφεραν μόνο το ότι η βάση γλιστράει αργά προς τα κάτω από το δύο. Απόδειξη όμως κανείς δεν έχει στα χέρια του.

Η ETH και το P εναντίον NP

Πώς συνδέονται αυτά τα δύο ερωτήματα; Φαντάσου ότι το 3-SAT έχει μια «πραγματική» δυσκολία, τον ταχύτερο δυνατό αλγόριθμο. Αυτός μπορεί να βρίσκεται σε τρεις ζώνες:

• Πράσινη ζώνη, πολυωνυμική. Το 3-SAT μπορεί να λυθεί, ας πούμε, σε n³ βήματα. Επειδή το 3-SAT είναι NP-πλήρες, θα ίσχυε τότε P = NP και η ETH φυσικά δεν θα ίσχυε.
• Μπλε ζώνη, υποεκθετική. Το 3-SAT μπορεί να λυθεί σε $2^{\sqrt{n}}$ βήματα ή κάτι παρόμοιο. Πολυωνυμικά όχι, άρα ισχύει P ≠ NP. Αλλά η ETH δεν θα ίσχυε.
• Κόκκινη ζώνη, εκθετική. Καλύτερα από cⁿ δεν γίνεται. Η ETH ισχύει και επομένως ισχύει και P ≠ NP.

Από το σχήμα φαίνεται ότι η ETH είναι ισχυρότερος ισχυρισμός από το P ≠ NP. Λέει όχι μόνο ότι το 3-SAT δεν λύνεται πολυωνυμικά, αλλά ότι δεν λύνεται ούτε υποεκθετικά. Όποιος αποδείκνυε την ETH, θα απέδειχνε έτσι και το P ≠ NP και θα έπαιρνε ένα εκατομμύριο δολάρια.

Και αντίστροφα: όποιος διέψευδε την ETH, δεν θα είχε απαραίτητα αποδείξει με αυτό το P = NP. Του αρκεί ένας αλγόριθμος από τη μπλε ζώνη. Θυμήσου το αυτό, σε λίγο θα το αξιοποιήσουμε.

Σε τι χρησιμεύει η ETH

Να αποδείξεις ότι ένα πρόβλημα δεν λύνεται γρήγορα είναι στην πληροφορική απίστευτα δύσκολο. Σχεδόν τίποτα τέτοιο δεν ξέρουμε να κάνουμε. Η ETH μας δίνει μια πίσω πόρτα: αντί για «το πρόβλημα Χ είναι δύσκολο» αποδεικνύουμε «το πρόβλημα Χ είναι δύσκολο, αν ισχύει η ETH».

Πώς; Δείχνουμε ότι αν το πρόβλημα Χ λυνόταν γρήγορα, θα λυνόταν γρήγορα και το 3-SAT. Ας πάρουμε για παράδειγμα το εξής: έχουμε n ανθρώπους και για κάποια ζευγάρια ξέρουμε ότι δεν αντέχουν ο ένας τον άλλον. Θέλουμε να τους μοιράσουμε σε τρία δωμάτια, ώστε κανένα τέτοιο ζευγάρι να μην καταλήξει στο ίδιο δωμάτιο. Οι πληροφορικοί το λένε χρωματισμό γραφήματος με τρία χρώματα. Από κάθε πρόβλημα 3-SAT μπορεί να κατασκευαστεί ένα τέτοιο πρόβλημα έτσι ώστε ο αριθμός των ανθρώπων να βγαίνει μόνο λίγες φορές μεγαλύτερος από τον αριθμό των γραμμάτων. Αν λοιπόν οι άνθρωποι μπορούσαν να μοιραστούν στα δωμάτια υποεκθετικά, θα λυνόταν υποεκθετικά και το 3-SAT και η ETH θα έπεφτε.

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

Η ETH έχει και μια ισχυρότερη αδελφή, την ισχυρή υπόθεση εκθετικού χρόνου (SETH). Αφορά προβλήματα όπου οι συνθήκες μπορούν να έχουν περισσότερα από τρία γράμματα, ας πούμε δέκα ή εκατό. Η SETH ισχυρίζεται ότι όσο μακρύτερες συνθήκες επιτρέψουμε, τόσο περισσότερο η καλύτερη δυνατή βάση πλησιάζει το δύο. Για μακριές συνθήκες δεν θα μπορούσαμε λοιπόν να εξοικονομήσουμε σχεδόν τίποτα σε σύγκριση με την ανόητη δοκιμή και των 2ⁿ δυνατοτήτων.

Γιατί γίνεται τώρα λόγος για την ETH

Η εταιρεία OpenAI, που την ξέρεις κυρίως από το ChatGPT, δημοσίευσε τον Οκτώβριο του 2026 ένα preprint, δηλαδή ένα άρθρο που δεν έχει ακόμη αξιολογηθεί από κριτές. Έχει τον τίτλο The Exponential Time Hypothesis is False, στα ελληνικά «Η υπόθεση εκθετικού χρόνου δεν ισχύει». Σε αυτό η εταιρεία ισχυρίζεται ότι βρήκε αλγόριθμο που λύνει το 3-SAT περίπου σε

$$2^{\frac{n}{\sqrt{\ln n}}}$$

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

Αν αυτό ίσχυε, ο αλγόριθμος της OpenAI θα έπεφτε στη μπλε ζώνη του σχήματος παραπάνω. Και τι θα σήμαινε αυτό;

• Η ETH θα έπεφτε και μαζί της η SETH και εκατοντάδες υπό συνθήκη αποτελέσματα που στηρίζονταν πάνω τους. Οι πληροφορικοί θα έπρεπε να πετάξουν ή να ξαναγράψουν πολλά «αν ισχύει η ETH, τότε…».
• Το πρόβλημα P εναντίον NP δεν θα το έλυνε. Ο αλγόριθμος εξακολουθεί να μην είναι πολυωνυμικός.
• Στην πράξη σχεδόν τίποτα δεν θα άλλαζε. Στον τύπο κρύβονται σταθερές που δεν τις γνωρίζουμε. Αν ήταν ίσες με ένα, για n = 1000 βγαίνει $\sqrt{\ln n}$ περίπου 2,6 και θα παίρναμε περίπου 2³⁸⁰ βήματα. Αυτό είναι σχεδόν το ίδιο με το 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ των σημερινών καλύτερων αλγορίθμων. Τους σημερινούς αλγορίθμους ο νέος θα τους ξεπερνούσε αισθητά μόνο για ακόμη μεγαλύτερα n, και κατά πόσο εξαρτάται ακριβώς από τις άγνωστες σταθερές. Έχει λοιπόν κυρίως θεωρητική σημασία. Την κρυπτογράφηση και τις τράπεζες δεν τις αφορά.

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

Λύση του προβλήματος με το πάρτι

Πρέπει να καλέσεις τον Τάσο, τον Ιάσονα και τον Δημήτρη, την Κατερίνα όχι. Στο σχήμα είναι και οι 16 δυνατότητες. Σε κάθε στήλη υπάρχει μία δυνατότητα: ο γεμάτος κύκλος σημαίνει ότι ο φίλος θα έρθει, ο κενός ότι δεν θα έρθει. Ο κόκκινος αριθμός κάτω από τη στήλη δείχνει την πρώτη συνθήκη που δεν ισχύει. Η μοναδική δυνατότητα στην οποία ισχύουν όλες οι συνθήκες πλαισιώνεται με πράσινο.

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

Δες επίσης

• Το μεγαλύτερο πρόβλημα της πληροφορικής: P εναντίον NP
• Προτασιακός λογισμός
• Εκθετική συνάρτηση
• Εκθετική αύξηση