Хипотеза за експоненциалното време (ETH)

Някои задачи умеем да решаваме само като пробваме почти всички възможности. Хипотезата за експоненциалното време, на английски Exponential Time Hypothesis и съкратено ETH, е залог на информатиците, че при една конкретна задача иначе няма да стане, колкото и хитри да сме. По-бързи методи съществуват, но дори най-добрите от тях ще изискват брой стъпки, който с размера на задачата расте експоненциално.

ETH е тясно свързана с проблема P срещу NP, на който имаме отделна статия. Ако още не си я чел, погледни първо там, защото ще се опираме на нея. Най-вече на това какво е сложност на алгоритъм и защо между n² и 2ⁿ има такава пропаст.

Кого да поканим на купона

Организираш купон и искаш да поканиш четирима приятели: Тодор, Йордан, Калина и Димитър. Уловката е, че между тях има различни отношения, а ти искаш всички да са доволни. След дълго разпитване излизат шест условия:

Ще дойде Тодор или Калина (може и двамата).
Йордан и Калина не се понасят, така че няма да дойдат и двамата.
Димитър ще дойде само ако дойде и Йордан.
Ако дойде Тодор, трябва да дойде и Калина или Димитър.
Ако дойдат и Тодор, и Калина, трябва да дойде и Йордан.
Ще дойде поне един от тройката Тодор, Йордан, Димитър.

Кого да поканим, за да са изпълнени всички условия едновременно? Опитай се да го измислиш сам, решението го пазим за края на статията.

Информатиците биха преписали задачата на езика на съждителната логика. Всеки приятел получава по една буква. За удобство вземаме латинските начални букви на имената: T като Тодор, K като Калина, D като Димитър, а Йордан е J, както в Jordan. Буквата е или истинна (Тодор ще дойде), или лъжлива (Тодор няма да дойде). Символът ∨ четем „или“, а ¬ четем „не“. Първото условие тогава изглежда така:

$T \lor K$

Второто условие казва, че Йордан няма да дойде или Калина няма да дойде:

$\neg J \lor \neg K$

При третото условие лесно се бърка. „Димитър ще дойде само ако дойде и Йордан“ означава, че не може да се случи Димитър да дойде, а Йордан да не дойде. Тоест или Димитър няма да дойде, или ще дойде Йордан:

$\neg D \lor J$

По същия начин преписваме и останалите. Цялата задача изглежда така:

$\begin{array}{rcl} 1. & T \lor K \\ 2. & \neg J \lor \neg K \\ 3. & \neg D \lor J \\ 4. & \neg T \lor K \lor D \\ 5. & \neg T \lor \neg K \lor J \\ 6. & T \lor J \lor 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ⁿ?

Може. Да пробваме абсолютно всичко е излишно. Достатъчно е например да забележим, че Тодор няма да дойде: от първото условие тогава веднага следва, че трябва да дойде Калина. Всички възможности, при които не би дошъл нито един от двамата, веднага зачеркваме. Хитрите алгоритми комбинират цял куп такива трикове. Най-добрите известни днес изискват приблизително

${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	n³	$2^{\sqrt{n}}$	1,307ⁿ	2ⁿ
20	8000	22	212	1 048 576
100	10⁶	1024	4,2 · 10¹¹	1,3 · 10³⁰
1000	10⁹	3,3 · 10⁹	1,9 · 10¹¹⁶	1,1 · 10³⁰¹

При n = 1000 функцията $2^{\sqrt{n}}$ е в същата категория като n³, докато двете показателни функции са избягали към числа, за които нямаме дори имена. Функциите като $2^{\sqrt{n}}$ , които растат по-бавно от cⁿ за всяка основа c, по-голяма от едно, се наричат субекспоненциални.

Същото показва и графиката. Вертикалната ос е логаритмична: всяко деление нагоре означава сто хиляди пъти по-голямо число. Иначе на чертежа нищо освен 2ⁿ нямаше да се побере.

$Растеж на функциите 2^n (в червено), 1{,}307^n (в оранжево), 2^{\sqrt{n}} (в синьо) и n^3 (в зелено) с логаритмична вертикална ос$

Показателните функции на такава графика са прави, които непрекъснато се изкачват. Червената 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: полиномиална (в зелено), субекспоненциална (в синьо) и експоненциална (в червено)

Зелена ивица, полиномиална. 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 възможности. Във всяка колонка има по една възможност: пълното кръгче означава, че приятелят ще дойде, празното – че няма да дойде. Червеното число под колонката показва първото условие, което не е изпълнено. Единствената възможност, при която са изпълнени всички условия, е обрамчена в зелено.

Всичките 16 възможности кого да поканим. Редовете отговарят на приятелите T, J, K, D, пълното кръгче означава, че ще дойде.

И точно това е грубата сила, която ETH смята за почти непреодолима: за четирима приятели шестнайсет колонки, за сто приятели повече колонки, отколкото са атомите в нашето тяло.

Виж също

« Предишна: Най-големият проблем в информатиката: P срещу NP

Следваща: Метод на Трахтенберг за бързо събиране »