Гіпотеза експоненційного часу (ETH)

Деякі задачі ми вміємо розв'язувати лише так, що перебираємо майже всі можливості. Гіпотеза експоненційного часу, англійською Exponential Time Hypothesis, скорочено ETH, — це ставка інформатиків на те, що в одній конкретній задачі інакше не вийде, хоч які хитрі ми були б. Швидші методи існують, проте навіть найкращі з них потребуватимуть кількості кроків, яка зі збільшенням розміру задачі зростає експоненційно.

ETH тісно пов'язана з проблемою P проти NP, якій ми присвятили окрему статтю. Якщо вона тобі ще не трапилася, зазирни туди спершу, бо ми на ній будуватимемо. Передусім на тому, що таке складність алгоритму і чому між n² та 2ⁿ така прірва.

Кого запросити на вечірку

Ти готуєш вечірку і хочеш запросити чотирьох друзів: Тараса, Йосипа, Катю та Данила. Біда в тому, що між ними склалися різні стосунки, а ти хочеш, щоб усі були задоволені. Після довгих розпитувань виходить шість умов:

1. Прийде Тарас або Катя (може, й обоє).
2. Йосип і Катя не зносять одне одного, тож удвох вони не прийдуть.
3. Данило прийде лише тоді, коли прийде й Йосип.
4. Якщо прийде Тарас, мусить прийти й Катя або Данило.
5. Якщо прийдуть і Тарас, і Катя, мусить прийти й Йосип.
6. Прийде принаймні один із трійки Тарас, Йосип, Данило.

Кого запросити, щоб усі умови виконувалися одночасно? Спробуй розв'язати це самостійно, розв'язок ми ховаємо наприкінці статті.

Інформатики переписали б задачу мовою логіки висловлень. Кожен друг отримує одну літеру, а ми для зручності беремо латинські початкові літери їхніх імен: T як Тарас, K як Катя, D як Данило, а Йосип — це J, як у Joseph. Літера або істинна (Тарас прийде), або хибна (Тарас не прийде). Символ ∨ читаємо «або», а ¬ читаємо «не». Перша умова тоді виглядає так:

$$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 році її сформулювали Рассел Імпальяццо та Рамамохан Патурі:

Існує число 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 дає нам лазівку: замість «задача X важка» ми доводимо «задача X важка, якщо виконується ETH».

Як? Показуємо, що якби задачу X можна було розв'язати швидко, швидко можна було б розв'язати й 3-SAT. Візьмімо, наприклад, таку: є n людей, і про деякі пари відомо, що вони не зносять одне одного. Треба розселити їх у три кімнати так, щоб жодна така пара не опинилася в одній кімнаті. Інформатики називають це розфарбуванням графа трьома кольорами. З кожної задачі 3-SAT її можна побудувати так, що кількість людей виходить лише в кілька разів більшою за кількість літер. Тож якби людей можна було розселити по кімнатах підекспоненційно, підекспоненційно розв'язувалася б і 3-SAT, а ETH впала б.

Таких умовних результатів сьогодні сотні. Уся галузь, що досліджує, наскільки саме важкі окремі задачі, стоїть на ETH, як будинок на фундаменті.

ETH має й сильнішу сестру, сильну гіпотезу експоненційного часу (SETH). Вона стосується задач, де умови можуть мати більше ніж три літери, скажімо десять чи сто. SETH стверджує: що довші умови ми дозволимо, то ближче найкраща можлива основа підходить до двійки. Для довгих умов не вдалося б зекономити майже нічого порівняно з дурним перебором усіх 2ⁿ можливостей.

Чому про ETH зараз говорять

Компанія OpenAI, яку ти знаєш передусім завдяки ChatGPT, оприлюднила в жовтні 2026 року препринт, тобто статтю, що ще не пройшла рецензування. Вона називається 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: найбільша загадка інформатики
• Логіка висловлень
• Показникова функція
• Експоненційне зростання